Euler's Totient Function

**chiph588@** · June 7th 2010, 03:26 PM

Show there exists $C>0$ such that $n^{1-\epsilon}<\varphi(n) \;\; \forall \; n>2$ , where $\epsilon = C\log\log n/\log n$ .

**PaulRS** · July 12th 2010, 09:14 AM

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

**chiph588@** · July 12th 2010, 09:41 AM

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

Thread: Euler's Totient Function

LinkBack

Thread Tools

Display

Euler's Totient Function

Similar Math Help Forum Discussions

Euler Totient Function

Euler totient function

Euler's totient function

Euler's Totient Function

Euler totient function

Search Tags