# prove that $\lim_{n\rightarrow\infty} \phi(n) = \infty$

prove that $\lim_{n\rightarrow\infty} \phi(n) = \infty$

I don't seem to understand where to start. I know of course that

$\phi(n) = n\cdot\Pi_{p|n} (1-\frac{1}{p})$.

If i can find a lower bound i can probably solve this, but i don't know how to evaluate the right term.

? $< \Pi_{p|n} (1-\frac{1}{p})$.

Any hints on tackling this question?

Kees

• you may show that $\phi(n) \geq \sqrt{\frac{n}{2}}$. – M.U. Sep 17 '15 at 17:23
• hmmmm i saw that on a few sites indeed, don't see how to do this though – Kees Til Sep 17 '15 at 17:26
• Good idea, but a fair bit of detail has to be filled in, since there is no positive lower bound for the product part. But it takes awfully big $n$ with many prime factors to make the product small. – André Nicolas Sep 17 '15 at 17:26
• – lhf Sep 17 '15 at 17:33
• One way is to use $\phi(n) \geqslant \pi(n) - \omega(n)$. Heavy machinery, though. – Daniel Fischer Sep 17 '15 at 17:35

## 1 Answer

A sketch to show $\phi(n) \geq \sqrt{\frac{n}{2}}$:

We use the fact that for $n = \prod p_i^{a_i}$ we have $$\phi(n) = \prod \phi(p_i^{a_i}) = \prod p_i^{a_i - 1}(p_i - 1).$$

The following inequality holds if and only if (*) $p_i \neq ?$ and $a_i \neq ?$ (think about it it's not very hard) $$p_i^{a_i - 1}(p_i - 1) \geq p_i^{a_i/2}.$$

Taking this into account you can prove that $\phi(n) \geq \sqrt{n}$, if $n$ is such that the condition (*) is satisfied.

Using that $\phi(n)$ is multiplicative you will get the assertion $\phi(n) \geq \sqrt{\frac{n}{2}}$ for all $n$.

• i thought of $a_i = 1$ and $p_i>2$, but we need it to work for 2 as well right? Kees – Kees Til Sep 17 '15 at 17:49
• you should obtain that this inequality is true if and only if $p_i \neq 2$ and $a_i \neq 1$. Suppose $p_i =2$ and $a_i =1$ you immediately get that the inequality is wrong. Suppose now that $a_i \geq 2$, then $a_i / 2 \leq a_i - 1$, thus the inequality. The last case is if $a_i = 1$ and $p_i \geq 3$. Then you have to show that $\sqrt{p_i} \leq p_i - 1$. – M.U. Sep 18 '15 at 5:45