The prime-factor formula for the <Euler totient function> is
$$
\frac n{\varphi(n)}
=\prod_{p\mid n}\left(1-\frac1p\right)^{-1}.
$$
Let
$$
y=\frac{\log n}{\sqrt{\log\log n}}.
$$
The factors with $p\leq y$ contribute at most
$$
\prod_{p\leq y}\left(1-\frac1p\right)^{-1}
=C\log y+O(1)
=(C+o(1))\log\log n
$$
by the <Mertens third theorem>. For $p>y$, the number of distinct prime divisors of $n$ is at most $\log n/\log y$, and hence
$$
\begin{aligned}
\log\prod_{\substack{p\mid n\\p>y}}\left(1-\frac1p\right)^{-1}
&\ll\sum_{\substack{p\mid n\\p>y}}\frac1p\\
&\leq\frac{\log n}{y\log y}
=O\left(\frac1{\sqrt{\log\log n}}\right).
\end{aligned}
$$
Thus the large-prime product is $1+o(1)$, and
$$
\frac n{\varphi(n)}\leq(C+o(1))\log\log n.
$$
Taking reciprocals gives, uniformly as $n\to\infty$,
$$
\boxed{\varphi(n)\geq\left(C^{-1}+o(1)\right)
\frac n{\log\log n}.}
$$

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 150 / 1 / e / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/iii/paper-150/1/e/solution