[< ] [^ ] | [> ]
Problem 69: Totient Maximum From the definition of Euler's totient function
$$
\begin{align}
\phi(n) & = n \prod_{p|n}(1 - \frac{1}{p}) \\
& = n \prod_{i=1}^{r} \frac{p_{i} - 1}{p_{i}}
\end{align}
$$
where $p_{i}$ are the distinct prime numbers dividing $n$ .
From the above equation
$$
\begin{align}
\frac{n}{\phi(n)} & = \frac{n}{n \frac{p_{1} - 1}{p_{1}} \frac{p_{2} - 1}{p_{2}} \cdots \frac{p_{r} - 1}{p_{r}}} \\
& = \frac{p_{1} \ p_{2} \cdots p_{r}}{(p_{1} - 1) (p_{2} - 1) \cdots (p_{r} - 1)} \\
& = \frac{p_{1}}{p_{1} - 1} \ \frac{p_{2}}{p_{2} - 1} \cdots \frac{p_{r}}{p_{r} - 1}
\end{align}
$$
The above equation shows that $\displaystyle \frac{n}{\phi(n)}$ depends on the prime factors of $n$ .
Assume that $m, n \in \mathbb{Z} : m > 0, \ n > 0, m > n$ ,
$$1 < \frac{m}{m-1} < \frac{n}{n-1}$$
Therefore, finding maximum $\displaystyle \frac{n}{\phi(n)}$ is equivalent to find maximum $k$
which satisfies the following inequality.
$$
p_{1} \ p_{2} \cdots p_{k-1} \ p_{k} \le 1000000
$$
where $p_{i}$ is $i$ -th prime number ($p_{1} = 2, \ p_{2} = 3, \ p_{3} = 5, \ \dots)$ .