×

First CS's inequality

Prove/Disprove the following inequality.

$\sum_{cyc}\sum_{k=1}^{M}\phi(a_1^k)\geq\sum_{cyc}\sum_{k=1}^{M} \phi (a_1)^k$

For all $$0\leq a_1 , a_2 , a_3 , ....., a_n \leq M$$ and $$M$$ is any natural number.

I have made the inequality more generalized.

Notation: $$\phi(\cdot)$$ denotes the Euler's totient function.

You may also see Second CS's inequality

1 year, 1 month ago

Sort by:

Let $$p$$ denotes an arbitrary prime number and let $$k,b \geq 1 \in \mathbb{N}$$

$$p^{k-1} \geq (p-1)^{k-1}$$

$$p^{-1} \geq p^{-k}(p-1)^{k-1}$$

$$p^{kb-1}(p-1) \geq p^{kb-k}(p-1)^{k}$$

$$p^{kb}-p^{kb-1} \geq {(p^{b}-p^{b-1})}^{k}$$

$$\phi(p^{kb}) \geq {\phi(p^{b})}^{k}$$, noting that $$\phi(p^{n})=p^{n}-p^{n-1}$$

Let $$a={p_{1}}^{k_{1}}{p_{2}}^{k_{2}}\cdots{p_{n}}^{k_{n}}$$.

From the result above, we have

$$\phi({p_{1}}^{kb_{1}})\phi({p_{2}}^{kb_{2}})\cdots\phi({p_{n}}^{kb_{n}}) \geq \phi{({p_{1}}^{b_{1}})}^{k}\phi{({p_{2}}^{b_{2}})}^{k}\cdots\phi{({p_{n}}^{b_{n}})}^{k}$$

$$\phi(a^{k}) \geq {\phi(a)}^{k}$$

Therefore, the inequality holds true, with equality holds only when $$a,b,c \in \{0,1\}$$ or $$M=1$$. · 1 year, 1 month ago

Comment deleted Mar 04, 2016

Done. · 1 year, 1 month ago

Nicely done ! I don't think that there will be any mistake...@ZK LIn · 1 year, 1 month ago

Thanks! Glad to know that. · 1 year, 1 month ago

Can't it be true for arbitary numbers ? · 1 year, 1 month ago

The inequality holds true for all numbers. What I meant was conditions for equality cases. · 1 year, 1 month ago

Oh , initially I proved this inequality for arbitary primes , Can this inequality have significance in problem solving or in any theorem proofs ? · 1 year, 1 month ago

Number theoretic inequalities are quite rare in math olympiads, so I guess it won't be that helpful? However, this is a nice result. I can imagine it being useful in theorem proofs, but I have not encountered enough number theory literature to see an application of this result yet. · 1 year, 1 month ago

@Otto Bretscher What is your opinion ? · 1 year, 1 month ago

Didn't we do this inequality in the first batch already, question 2?

It is good to know the equation $$\phi(n^k)=n^{k-1}\phi(n)$$; this inequality is an immediate consequence. · 1 year, 1 month ago

Comment deleted Mar 04, 2016

As you know, there is a big difference between Olympiad problems and "real mathematics". In hundreds of seminar talks I have attended at many universities, where people present their research papers, I have never heard anybody talk about number theoretical inequalities (or inequalities in general). · 1 year, 1 month ago

So you mean this is something new ? @Otto Bretscher · 1 year, 1 month ago

Do you think that such inequalities will be useful for ay theorem proofs or problems ? @Otto Bretscher · 1 year, 1 month ago

Comment deleted Mar 04, 2016

Sure, why not? · 1 year, 1 month ago

For $$k>1$$,

$\phi(a^k)=a^{k-1}\phi(a)$

Since

$\phi(a)<a$

$\phi(a)^k<a^{k-1} \phi(a)=\phi(a^k)$

For k=1, the result $$\phi(a^k)=\phi(a)$$ is trivial.

The result above follows. · 1 year, 1 month ago

Exactly ! :) · 1 year, 1 month ago

Comment deleted Mar 02, 2016

Bro, I see that you have studied all these awesome stuffs!

Can you please suggest me resources for studying them?Thanks!

(I mean modular arithmetic) · 1 year, 1 month ago

You can see that the inequality is proved , I had proved this only for arbitary peimes , and I am searching a more general proof , as you xan see the generalized inequality ... I will be glad to hear your opinions related to this new NT inequality.. @Harsh Shrivastava · 1 year, 1 month ago

I will try this in a few days,sorry a bit busy with board stuffs. · 1 year, 1 month ago

You may start up with Elementary Number Theory by David Burton , and for advanced , you may refer Advanced Number Theory .... How can I become good at inequalities ? Please suggest ..... · 1 year, 1 month ago

I am not good in inequalities.

People like @ZK LIn @MS HT @gurido cuong are real inequality gods.

Please suggest us how to become good at inequalities ?

Thnx! · 1 year, 1 month ago

You are too generous with your compliment. I am definitely nowhere near the levels of @MS HT and @Gurido Cuong. They post new inequality problems at a rate faster than I can solve them, and I am nowhere near the level of a 'god' either.

However, since you ask for advice, I will do my best to provide them.The "advice" below comes from my personal experience and might not work for everyone, so take it with a pinch of salt.

I initially start studying inequalities seriously from the excellent note Mildorf "Olympiad Inequalities", which I believe is available somewhere on the web (AoPS maybe?). You might find that helpful.

A more elementary version of this is Siamin Riasat "Basics in Olympiad Inequalities". When I am a complete newbie, I rely on it heavily and tried (unsuccessfully) to solve all the problems. Easy as the questions are, they provide a good chance for you to apply the inequalities introduced. · 1 year, 1 month ago

I'm not good as you think.Because I'm not better than many people in my school or my social... · 1 year, 1 month ago

Here · 1 year, 1 month ago

I can't help but notice that i am a member of that site.

BTW your joke was awesome.I am rolling over floor laughing.I appreciate efforts that you put in making this joke.You must consider a career as a stand-up comedian.Hats off to you! · 1 year, 1 month ago

I like your sense of sarcasm :3 Preserve it, not many have that. · 1 year, 1 month ago