2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ you may show that $\phi(n) \geq \sqrt{\frac{n}{2}}$. $\endgroup$ – M.U. Sep 17 '15 at 17:23
  • $\begingroup$ hmmmm i saw that on a few sites indeed, don't see how to do this though $\endgroup$ – Kees Til Sep 17 '15 at 17:26
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Sep 17 '15 at 17:26
  • $\begingroup$ See math.stackexchange.com/questions/301837/…. $\endgroup$ – lhf Sep 17 '15 at 17:33
  • $\begingroup$ One way is to use $\phi(n) \geqslant \pi(n) - \omega(n)$. Heavy machinery, though. $\endgroup$ – Daniel Fischer Sep 17 '15 at 17:35
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ i thought of $a_i = 1$ and $p_i>2$, but we need it to work for 2 as well right? Kees $\endgroup$ – Kees Til Sep 17 '15 at 17:49
  • 1
    $\begingroup$ 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$. $\endgroup$ – M.U. Sep 18 '15 at 5:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.