In honour of Euler

Relevant wiki: Euler's Totient Function

We can use a formula for $\phi (n)$ .

Suppose that the canonical factorization of n is:

$n=\displaystyle\prod_{i=1}^{k}p_{i}^{\alpha_{i}}$

Then

$\phi(n) = n\displaystyle\prod_{i=1}^{k}\left(1-\frac{1}{p_{i}}\right)$

Thus:

$\frac{n}{\phi (n)}=\frac{1}{\displaystyle\prod_{i=1}^{k}\left(1-\frac{1}{p_{i}}\right)}=\frac{1}{\displaystyle\prod_{i=1}^{k}\left(\frac{p_{i}-1}{p_{i}}\right)}$

$\frac{n}{\phi (n)}=\frac{p_{1}.p_{2}... p_{k}}{(p_{1}-1)(p_{2}-1)...(p_{k}-1)}$

From this expression is easy to see that if two or more prime factors of $n$ are odd, then $\frac{n}{\phi (n)}$ cannot be an integer because on the denominator of the fraction we would get two or more even numbers that together are a multiple of 4 that cannot be simplified with any prime number on the numerator. For similar reasons, the odd prime number cannot be larger than 3 and has to be multiplied by 2 on the numerator.

Therefore the only possible values for $\frac{n}{\phi (n)}$ are: $\frac{n}{\phi (n)}=\frac{1}{1}=1, \frac{n}{\phi (n)}=\frac{2}{(2-1)}=2\ or\, \frac{n}{\phi (n)}=\frac{2.3}{(2-1)(3-1)}=3$

And the product of these three values is $1.2.3=6$

If $n=1$ then $\phi(n) = 1$ , and so $\frac{n}{\phi(n)} = 1$ . Suppose now that $n \ge 2$ , and write $n \; = \; p_1^{a(1)}p_2^{a(2)} \cdots p_N^{a(N)}$ as a product of primes, where $p_1,p_2,...,p_N$ are distinct primes and $a(1),a(2),...,a(N)$ are positive integers. Then $\phi(n) \; = \; (p_1 - 1)(p_2-1)\cdots(p_N-1) p_1^{a(1)-1}p_2^{a(2)-1} \cdots p_N^{a(N)-1}$ and hence we have that $(p_1-1)(p_2-1)\cdots(p_N-1)$ divides $p_1p_2\cdots p_N$ . Since $p_1p_2\cdots p_N$ can only have one factor of $2$ at most, and since $p-1$ is even whenever $p$ is an odd prime, we deduce that $n$ can only have at most one odd prime factor.

• If $n$ has no odd prime factor, then $n = 2^a$ for some positive integer $a$ , so that $\phi(n) = 2^{a-1}$ , and so $\frac{n}{\phi(n)} = 2$ .
• If $n$ has one odd prime factor $p$ , then since $p-1$ is an even factor of $\phi(n)$ , we deduce that $n$ is even, and hence $n = 2^ap^b$ for some positive integers $a,b$ . But then we must have $p-1$ dividing $2p$ , and hence $p-1$ must divide $2$ . This implies that $p=3$ , and hence $\frac{n}{\phi(n)} = 3$ .

Thus the possible values of $\frac{\phi(n)}{n}$ are $1,2,3$ , and hence the product of the possible values is $\boxed{6}$ .

Guesswork solution: it won't grow forever. So it must be something like one. Nope. There must've been some edge cases. Include 2 and 3. Et voilà!