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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## 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\).

Log in to reply

Comment deleted Mar 04, 2016

Log in to reply

Done.

Log in to reply

Nicely done ! I don't think that there will be any mistake...@ZK LIn

Log in to reply

Thanks! Glad to know that.

Log in to reply

Log in to reply

Log in to reply

Log in to reply

Log in to reply

@Otto Bretscher What is your opinion ?

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.

Log in to reply

Comment deleted Mar 04, 2016

Log in to reply

Log in to reply

@Otto Bretscher

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

Comment deleted Mar 04, 2016

Log in to reply

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.

Log in to reply

Exactly ! :)

Log in to reply

Comment deleted Mar 02, 2016

Log in to reply

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)

Log in to reply

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

Log in to reply

Log in to reply

Comment deleted 12 months ago

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!

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.

Log in to reply

Log in to reply

Here

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!

Log in to reply

Log in to reply

Log in to reply