# Euler's Totient Function

• Jun 7th 2010, 04:26 PM
chiph588@
Euler's Totient Function
Show there exists $C>0$ such that $n^{1-\epsilon}<\varphi(n) \;\; \forall \; n>2$, where $\epsilon = C\log\log n/\log n$.
• Jul 12th 2010, 10:14 AM
PaulRS
Does that work for n = 2 ? .... (Wondering)

Remember that $\tfrac{n}{\phi(n)}<\zeta(2)\cdot \left(\tfrac{\sigma(n)}{n}\right)$ ( see here )

Now $\tfrac{\sigma(n)}{n} = \sum_{d|n}\left(\tfrac{1}{d}\right) \leq H_n = 1 + \tfrac{1}{2} + ... + \tfrac{1}{n} \leq \log(n) + 1$

Thus $\tfrac{n}{\phi(n)}<\zeta(2)\cdot \left(\log(n) + 1\right) < \left(\log(3)\right)^{k-1} \cdot \log( n) \leq \left( \log( n) \right)^k$ if we pick k large enough (since $\log( 3) > 1$ )

Then we'd have $\tfrac{n}{\phi(n)} < \left( \log( n) \right)^k = n^{k\cdot \left(\tfrac{\log\log n}{\log n}\right)}$ for n > 2
• Jul 12th 2010, 10:41 AM
chiph588@
Quote:

Originally Posted by PaulRS
Does that work for n = 2 ? .... (Wondering)

Remember that $\tfrac{n}{\phi(n)}<\zeta(2)\cdot \left(\tfrac{\sigma(n)}{n}\right)$ ( see here )

Now $\tfrac{\sigma(n)}{n} = \sum_{d|n}\left(\tfrac{1}{d}\right) \leq H_n = 1 + \tfrac{1}{2} + ... + \tfrac{1}{n} \leq \log(n) + 1$

Thus $\tfrac{n}{\phi(n)}<\zeta(2)\cdot \left(\log(n) + 1\right) < \left(\log(3)\right)^{k-1} \cdot \log( n) \leq \left( \log( n) \right)^k$ if we pick k large enough (since $\log( 3) > 1$ )

Then we'd have $\tfrac{n}{\phi(n)} < \left( \log( n) \right)^k = n^{k\cdot \left(\tfrac{\log\log n}{\log n}\right)}$ for n > 2

You're correct, I should've said $n>2$ as $\log\log2<0$.