Prove/disprove the following inequalities.

If \(M\) and \(k\) are natural numbers, then

\[1) \sum_{n=1}^{M} \phi(n) \geq \frac{1}{\sum_{n=1}^{M} \phi (n)}\]

\[2)\sum_{n=1}^{M} \phi(n) \geq \sum_{n=1}^{M} \phi(\phi(n))\]

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

Stay updated with my new inequality notes !!!

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:

TopNewestLemma:\(\phi(n^k)≥\phi(n)^k\)

proof:\(\phi(n^k)=n^{k-1}\phi(n)≥\phi^k(n)\to n^{k-1}≥\phi^{k-1}(n)\to n≥\phi(n)\) which we know is true. the result follows

3.\(n≥\phi(n)\) let \(n=\phi(x)\) the \(\phi(x)≥\phi(\phi(x))\) and the result follows.

Log in to reply

right, exactly. The only non-trivial one is \(\phi(n^k)=n^{k-1}\phi(n)\)

Log in to reply

Darn I worked so hard to type the whole solution.

Thank god I started from the bottom, otherwise I would've worked harder, only to receive nothing :P

Log in to reply

I thought about them during my morning shower, and they all appear to be true. Want any proofs? They are all one liners...

Log in to reply

Morning shower is the best place to think abt maths , ;) , Actually I thought abt them and their proofs , in my morning shower

Log in to reply

Q3. We will prove that \(\phi (n) > \phi (\phi (n))\)

\(\phi (n) = n \times (1- \dfrac {1}{a_1}) \times (1- \dfrac {1}{a_2}) \times \cdots \times \dfrac {1}{a_k}\) where \(n = a_1 ^{p_1} a_2 ^{p_2}\cdots a_k ^{p_k}\) where \(a_1,a_2...., a_k\) are prime numbers, and \(p_1,p_2..., p_k\) are positive integers.

Now, \(\phi (\phi (n)) = \phi (n \times (1- \dfrac {1}{a_1}) \times (1- \dfrac {1}{a_2}) \times \cdots \times \dfrac {1}{a_k}))\)

We observe that \(\phi (n) < n\) , because it is multiplied by fractions less than 1.

Thus , we show that \(\phi (\phi (n)) \leq \phi (n)\) , thus the inequality holds true.

Log in to reply

Small correction : \(\phi(n)\leq n\) since you have equality for \(n=1\)

Log in to reply

Oops yeah, thanks :D

Log in to reply

Nicely done Mehul !

Log in to reply

Thanks Chinmay! :D

I was about to write the other proofs as well, but Aareyan beat me ;)

Log in to reply