How can we prove that there are no other integers with $\phi(n)=2$ besides 3,4,6?

Question

Where $\phi(n)$ is Euler's phi function that counts the number of relatively prime integers less than or equal to n.

I've been able to compute that 3,4,6 all have only 2 relatively prime integers less than or equal to them, however I'm unsure how to prove that there are indeed no others. While I am certain that this is the case, how can this be proved rigorously?

Answer 1

The trickiest thing about this proof is figuring out how to organize the casework. Here's one way to do it:

If $n = 2^k$ is a power of two then $\varphi(n) = 2^{k-1}$ so we see that we can only have $k = 2$, so $n = \boxed{4}$.

Otherwise, $n$ has some odd prime power factor $p^k$, and then $\varphi(n)$ must be divisible by $\varphi(p^k) = (p-1) p^{k-1}$. Since $p$ is odd, $2 \mid (p-1)$, so $\varphi(p^k)$ will be strictly larger than $2$ unless $p = 3, k = 1$. So now we must have $n = 2^k \cdot 3$, which gives $\varphi(n) = 2^k$ for $k \ge 1$, hence $k = 1$, so $n = \boxed{6}$, or $\varphi(3) = 2$ for $k = 0$, so $n = \boxed{3}$.

Exercise. Generalize this argument to show that for any $m$ there are finitely many $n$ such that $\varphi(n) = m$. Can you compute which $n$ these are for other small values of $m$, say $m = 4$ or $m = 6$? (Hint: prove it in two stages. First prove that there are only finitely many possible prime factors for $n$. Second prove that the exponent of each of these prime factors is bounded. Working through the small cases $m = 4$ and $m = 6$ first would be a good idea as a warmup.)

Answer 2

First prove that if $n = \prod p_i^{k_i}$ is the unique prime factorization of $n$ then $\phi(n) = \prod p_i^{k_i - 1} \prod (p_i - 1)$. You should have already proven this. The statement is totally equivalent to: 1) if $\gcd(a,b)= 1$ then $\phi(ab) = \phi(a)\phi (b)$ and $\phi(p^k)=p^{k-1}(p-1)$ if $p$ is prime and 2) $\phi( n )= n\prod_{p|n}(1-\frac 1p)$.

Then we have $2 = \prod p_i^{k_i -1} \prod (p_i-1)$. The only way that can happen is if either i) $\prod p^{k_i-1} = 2$ and $\prod (p_i-1) = 1$ or if ii) $\prod p_i^{k_i-1} = 1$ and $\prod (p_i-1) = 2$.

If i) then $\prod (p_i-1) = 1$ imples $\{p_i\} = \{2\}$ and $\prod p^{k_i-1} = 2^1$ implies $\{p_i\} = 2$ and $k_i = 2$ so $n = 2^2 = 4$.

if ii) then $\prod p_i^{k_i-1} = 1$ implies $k_i =1$ of all the $p_i$ and $n = \prod p_i$, a square-free number. Then $\prod (p_i - 1) =2$ implies that one of the $p_i-1 = 2$ and all the other $p_j$ (if any) are $p_j -1 = 1$. One of the prime factors is $3$ and if there is any other prime factor it can only be $2$. but there need not be any other prime factor. So we could have $n=3$ or $n=2\cdot 3 = 6$.

....

If that was too hand-wavy, here is a coffin with a few dozen nails:

Suppose $p> 3$ is a prime divisor of $n=\prod p_i^{k_i}$. Then $\phi(n) = \prod p_i^{k_i - 1} \prod (p_i - 1)$ so $p-1|\phi(n)$. But $p-1 > 2$ so $\phi(n) > 2$. So if $\phi(n) = 2$ then $n$ has no prime divisors greater than $3$.

So $n = 2^a$ or $n = 3^b$ or $n=2^a3^b$ or $n = 1$.

If $n = 2^a$ then $\phi(n) = 2^{a-1}(2-1) = 2^{a-1}=2$. So $a-1 =1$ and $a=2$ and $n = 2^2 = 4$.

If $n=3^b$ then $\phi(n) = 3^{b-1}(3-1) = 2\cdot 3^{b-1} =2$. So $b-1 =0$ and $b=1$ and $n = 3^1=3$.

If $n = 2^a3^b$ then $\phi(n) = 2^{a-1}3^{b-1}(2-1)(3-1) = 2\cdot 2^{a-1}3^{b-1} = 2^a3^{b-1} =2$. So $a =1$ and $b-1 =0$ and $b=1$ and $n = 2^1\cdot 3^1 = 6$.

And of course if $n= 1$ then $\phi(n)=\phi(1) =1\ne 2$

So $4,3,6$ are the only three options for $\phi(n) =2$.