What is the solution to Euler's totient function for a given value of n?

[Chris L T521]

Thanks to those who participated in last week's POTW! Here's this week's problem!

-----

Problem: Determine all $n$ for which $\varphi(n)=n-2$, where $\varphi(n)$ denotes Euler's totient function.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Chris L T521]

This week's problem was correctly answered by Bacterius, chisigma, and magneto.

You can find Bacterius' solution below.

[sp]Lemma 1: Euler's totient function $\varphi(n)$ is even for all $n > 2$.

Proof: If $n$ is a power of two, then $n = 2^k$ with $k > 1$ (since $n > 2$), and therefore $\varphi(n) = 2^{k - 1} > 1$ is even. If $n$ is not a power of two, then $n$ has at least one odd prime power factor, call it $p^k$ with $k \geq 1$, so $p^k \mid n$. Then $\varphi(p^k) \mid \varphi(n)$, that is, $(p - 1) p^{k - 1} \mid \varphi(n)$. Note $p - 1$ is even. $\blacksquare$

Lemma 2: For all even $n \geq 2$, Euler's totient function satisfies $1 \leq \varphi(n) \leq \frac{n}{2}$.

Proof: Since $n$ is even, rewrite it as $n = 2^k m$ with $k \geq 1$ and odd $m$. Then $1 \leq \varphi(2^k m) = \varphi(2^k) \varphi(m) = 2^{k - 1} \varphi(m) = \frac{1}{2} 2^k \varphi(m) \leq \frac{n}{2}$ by observing that $1 \leq \varphi(m) \leq m$ by definition. The upper bound is attained whenever $n$ is a power of two. $\blacksquare$

Theorem: The only solution to the equation $\varphi(n) = n - 2$ is $n = 4$.

Proof: We first dispose of the special case $n = 1$ by verifying that it is not a solution. We can then eliminate all odd $n$ as solutions in light of Lemma 1, as $\varphi(n) = n - 2$ must be even. We then deduce from Lemma 2 that any (even) solution to the equation for $n \geq 2$ must satisfy $1 \leq n - 2 \leq \frac{n}{2}$, that is, $3 \leq n \leq 4$. It remains to check whether or not $n = 4$ is a solution, and indeed $\varphi(4) = 2$. $\blacksquare$[/sp]

I also liked magneto's solution, so you can see it below as well.

[sp]For an integer $n$ to satisfy $\phi(n) = n-2$,
it means there are two integers $\leq n$ that are not coprime with $n$ --- one of which
we know is $n$. Suppose the other is $m < n$ where $\gcd(m,n) = c > 1$. Then
we know there is an integer $1 < a < n$ where $ac = n$.

If $a \neq c$, since $a,c$ both divide $n$, $\gcd(a,n) \neq 1 \neq \gcd(c,n)$,
implying $\phi(n) < n-2$. Therefore, $a = c$, implying the necessary condition
is that $n$ is a square. We can quickly check that $n=4$ holds: $\phi(4) = 2$,
as $1$ and $3$ are the only two integers $\leq 4$ coprime with $4$.

However, for $k > 2$, we have that $2k < k^2$. So, there are at least three
integers $\leq k^2$ not coprime with $k^2$, namely, $k$, $2k$ and $k^2$,
hence, $\phi(k^2) < k^2 - 2$ for $k > 2$.

$\therefore$ The only $n$ where $\phi(n) = n-2$ is $n=4$.[/sp]