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

## Comments

Sort by:

TopNewestNot quite sure about this, correct me if I make a mistake somewhere.

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\). – Zk Lin · 1 year, 5 months ago

Log in to reply

Log in to reply

– Zk Lin · 1 year, 5 months ago

Done.Log in to reply

@ZK LIn – Chinmay Sangawadekar · 1 year, 5 months ago

Nicely done ! I don't think that there will be any mistake...Log in to reply

– Zk Lin · 1 year, 5 months ago

Thanks! Glad to know that.Log in to reply

– Chinmay Sangawadekar · 1 year, 5 months ago

Can't it be true for arbitary numbers ?Log in to reply

– Zk Lin · 1 year, 5 months ago

The inequality holds true for all numbers. What I meant was conditions for equality cases.Log in to reply

– Chinmay Sangawadekar · 1 year, 5 months ago

Oh , initially I proved this inequality for arbitary primes , Can this inequality have significance in problem solving or in any theorem proofs ?Log in to reply

– Zk Lin · 1 year, 5 months 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.Log in to reply

@Otto Bretscher What is your opinion ? – Chinmay Sangawadekar · 1 year, 5 months ago

Log in to reply

first batch already, question 2?

Didn't we do this inequality in theIt is good to know the equation \(\phi(n^k)=n^{k-1}\phi(n)\); this inequality is an immediate consequence. – Otto Bretscher · 1 year, 5 months ago

Log in to reply

Log in to reply

– Otto Bretscher · 1 year, 5 months ago

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).Log in to reply

@Otto Bretscher – Chinmay Sangawadekar · 1 year, 5 months ago

Do you think that such inequalities will be useful for ay theorem proofs or problems ?Log in to reply

Log in to reply

– Zk Lin · 1 year, 5 months ago

Sure, why not?Log in to reply

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. – Julian Poon · 1 year, 5 months ago

Log in to reply

– Chinmay Sangawadekar · 1 year, 5 months ago

Exactly ! :)Log in to reply

Log in to reply

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

(I mean modular arithmetic) – Harsh Shrivastava · 1 year, 5 months ago

Log in to reply

@Harsh Shrivastava – Chinmay Sangawadekar · 1 year, 5 months 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..Log in to reply

– Harsh Shrivastava · 1 year, 5 months ago

I will try this in a few days,sorry a bit busy with board stuffs.Log in to reply

Log in to reply

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

Please suggest us how to become good at inequalities ?

Thnx! – Harsh Shrivastava · 1 year, 5 months ago

Log in to reply

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. – Zk Lin · 1 year, 5 months ago

Log in to reply

– Ms Ht · 1 year, 5 months ago

I'm not good as you think.Because I'm not better than many people in my school or my social...Log in to reply

Here – Mehul Arora · 1 year, 5 months ago

Log in to reply

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! – Harsh Shrivastava · 1 year, 5 months ago

Log in to reply

– Mehul Arora · 1 year, 5 months ago

I like your sense of sarcasm :3 Preserve it, not many have that.Log in to reply

– Nihar Mahajan · 1 year, 5 months ago

LOL! :3 :3 :3Log in to reply