# Show that the only solution to $\phi(n) =n-2$ is $n=4$

Came across this question in Number Theory.

Let $\phi$ denote Euler's totient function; Show that the only solution to $\phi(n) =n-2$ is $n=4$

My workings so far have included, firstly proving that $4$ is indeed a solution, I have also noted that the solution cannot be prime because $\phi(p)=p-1$.

From here, could I note that my solution must be composite, and the only way in which it could have only 2 numbers which are not coprime would be if n is a square number?

Not sure how to prove this completely though.

Also, could I incorporate the fact that $\phi(p^k)=p^{k-1}(p-1)$ in any way?

All help greatly appreciated. Thanks.

-

The equation $\phi(n) = n - 2$ means that there are $n - 2$ numbers in $\{1, 2, \dots, n\}$ that are relatively prime to $n$. In other words, there are exactly two numbers in $\{1, 2, \dots, n\}$ that are not relatively prime to $n$. One of them of course is $n$ itself. So there is exactly one other number, in $\{2, \dots, n-1\}$, which shares any factors in common with $n$.

Now as you observed, $n$ cannot be prime (because then there would be none). So $n$ is composite, and therefore has some prime factor $p$. This is one number with which $n$ shares a common factor, and if $n > 2p$, then $2p$ is another such number. So $n = 2p$. We now know that $n$ is even, i.e., $2$ is a prime factor $p$ of $n$, and from $n = 2p$, we get $n = 2\times2 = 4$.

-
Thanks! This what I was trying to get at but couldn't quite formulate. Great. –  Olivia77989 May 16 '13 at 16:27
Actually, a simpler argument: if $n$ is composite, say $n = ab$ with $a, b > 1$, then $a, 2a$ are two numbers not relatively prime to $n$, so $b = 2$, similarly $a = 2$, and therefore $n = 4$. This argument can be extended to prove that $\phi(n) = n - k$ has only finitely many solutions, for any $k$. If $n = ab$, then considering the numbers $a, 2a, \dots, ba$ gives $b \le k$, similarly $a \le k$, so $n \le k^2$. –  ShreevatsaR May 16 '13 at 16:56

$\varphi(n)$ is even for every $n \ge 3$, so you would need $n$ to be even as well. However, if you write $n = 2^k m$, $m$ odd, then $$n - 2 = \varphi(n) = \varphi(2^k) \varphi(m) = 2^{k-1} \varphi(m) \le 2^{k-1} m = \frac{n}{2}$$ which severely limits the possibilities for $n$.

-
NB $\varphi(n)$ is even by Lagrange's theorem because there is a subgroup $\{\pm 1\}$ of order $2$ in $Z/nZ ^\times$ –  user78070 May 16 '13 at 11:49
Unfortunately, I don't follow –  Olivia77989 May 16 '13 at 12:08
@user77989 The units of a ring form a group. Since $\Bbb Z/ n\Bbb Z$ is a ring and $\left|\left(\Bbb Z/ n\Bbb Z\right)^{\times}\right| = \phi(n)$, and as long as $n\neq 2$ $1\neq -1$, $\{\pm 1\}$ is a subgroup of order $2$ in $\left(\Bbb Z/ n\Bbb Z\right)^{\times}$. Then by Lagrange's theorem, $2$ divides $\left|\left(\Bbb Z/ n\Bbb Z\right)^{\times}\right| = \phi(n)$, so $\phi(n)$ is even. –  Stahl May 16 '13 at 13:04

Hint: We know that $(n,n-1)=1$ and $(1,n)=1$. For $n >4$, can you use primes to come up with a further coprime integer less than $n$?

-
This idea is a bit backwards: you have listed two integers which are counted in $\phi(n)$, and suggesting finding one more, which will prove that $\phi(n) > 2$, rather than $\phi(n) < n - 2$. –  ShreevatsaR May 16 '13 at 12:07