Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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$.

share|improve this answer
    
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$.

share|improve this answer
1  
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
1  
@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$?

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.