# Math Help - Euler's Totient Function

1. ## 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$.

2. Does that work for n = 2 ? ....

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

3. Originally Posted by PaulRS
Does that work for n = 2 ? ....

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$.