How can I show this?

Obviously as $n$ approaches infinity it will have infinitely many prime factorizations, so the product series approaches infinity as well. How can I formally prove this?

  • 1
    $\begingroup$ @DietrichBurde That's a fairly weak interpretation of "approaches infinity". It's actually true that $\phi(n) \to \infty$, not just $\limsup \phi(n) = \infty$. $\endgroup$ – Erick Wong Feb 27 '14 at 16:51
  • $\begingroup$ @Dietrich: Not to be overly critical, but: what it means for a function $f: \{1,2,3,\ldots\} \rightarrow \mathbb{R}$ to approach infinity as $n$ approaches infinity is not ambiguous in any way: it is the standard freshman calculus concept with the domain restricted to the positive integers. $\endgroup$ – Pete L. Clark Feb 27 '14 at 20:24

The cheapest way is $$ \phi(n) \geq \sqrt {\frac{n}{2}}, $$ with equality at $2$ only.

There is a slightly weaker result that is sometimes given as a question here, maybe something along the lines of $(1/2) \sqrt n,$ which does not require the full procedure... anyway, see Is the Euler phi function bounded below? where the setting is Ramanujan's, the same proofs as for Colossally Abundant Numbers and Superior Highly Composite Numbers. We get an infinite sequence of inequalities, where the overall shape is the Rosser and Schoenfeld thing, but these are easier to calculate and better for small $n.$ Anyway, after the square root, the next sensible one is $$ \phi(n) \geq 2 \left( \frac{n}{6} \right)^{2/3}, $$ with equality at $6$ only.


You can use part of Theorem 15 of Rosser and Shoenfeld's paper http://www.math.wvu.edu/~mays/745/Rosser-Schoenfeld%20(euclid.ijm.1255631807).pdf which states that $$ \frac{n}{\phi(n)} < e^c \log \log n + \frac{5}{2 \log\log n} $$ where $c=0.57721566...$ is Euler's constant, for all $n>223092870$.

Added: Or, see Tenenbaum's Introduction to Analytic and Probabilistic Number Theory, page 84, Theorem 4, wherein he proves that $\phi(n)$ has minimal order $$ e^{-\gamma} \frac{ n } {\log \log n}$$ where $\gamma$ is Euler's constant.

Added #2: More basically, we have $$ \phi(n) = n \prod_{p^{\alpha} || n} \left( 1-\frac{1}{p} \right) \ge n \left(1-\frac{1}{2} \right)\left(1-\frac{1}{3}\right)^{\omega(n)-1} \\ \ge n \left( \frac{1}{2} \right) \left( \frac{2}{3} \right)^{\frac{\log n}{\log 2} -1 } \\ = \frac{3}{4} n ^{2 - (\log 3)/(\log 2)} $$ and the last expression tends to $\infty$ as $n$ does.


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.