Why Does Only n=4 Satisfy the Equation g(n)=n-2 in Euler's Totient Function?

[Poirot1]

I am having difficulty with the following question. Show that only n=4 satisfies g(n)=n-2, where g is the euler totient function. Well,firstly g(4)=2=4-2.

Supposing that g(n)=n-2 for some n, we see that n is not 1 or 2, so that g(n) is even.

Therefore n=g(n)+2 is even. If we suppose that n has no odd prime divisors, then we find

that g(n)=n-2 implies n=4. So it remains to consider the case where n does have odd

prime divisors, and derive a contradiction. Can anyone furnish this elusive contradiction?

Thanks

 

[Nono713]

Re: another totient function problem.

Hmm, interesting problem. I believe I have a proof for when $n$ has at least one odd factor and is a multiple of $2^k$ for $k > 1$, but the missing case for $n = 2r$ with odd $r$ eludes me at this time. Also, $n$ must be even, since $\varphi{(n)}$ is always even for $n > 2$.​

 

[Poirot1]

Re: another totient function problem.

Hmm, interesting problem. I believe I have a proof for when $n$ has at least one odd factor and is a multiple of $2^k$ for $k > 1$, but the missing case for $n = 2r$ with odd $r$ eludes me at this time. Also, $n$ must be even, since $\varphi{(n)}$ is always even for $n > 2$.​

This question (and the similar questions I have been posting) are from past exams , and they should be of moderate difficulty. While I have no doubt your proofs are fine Bacterius, your arguments seem slighty too involved. I noted that Chisigma seemed to get the answer quickly on this thread http://www.mathhelpboards.com/f27/find-all-positive-integers-4526/, but he did not explain his reasoning.

 

[Nono713]

Re: another totient function problem.

This question (and the similar questions I have been posting) are from past exams , and they should be of moderate difficulty. While I have no doubt your proofs are fine Bacterius, your arguments seem slighty too involved. I noted that Chisigma seemed to get the answer quickly on this thread http://www.mathhelpboards.com/f27/find-all-positive-integers-4526/, but he did not explain his reasoning.

Actually the semi-proof I have in mind for this one is simple (it's a parity argument). But as it is now, it doesn't prove every case, unfortunately. If you mean the other thread, yes, my reasoning was a little long-winded on that one ​

 

[Nono713]

Here it is, anyway. You've shown that $n$ must be even, and except for $n = 4$, it has at least one odd factor. Rewrite:

$$n = 2^k \cdot r ~ ~ \text{for some odd} ~ r > 2 ~ \text{and some} ~ k > 1$$
Then we have:

$$n - 2 = 2 \left ( 2^{k - 1} \cdot r - 1 \right ) ~ ~ \text{and} ~ ~ \varphi{(n)} = 2^{k - 1} \cdot \varphi{(r)}$$
Now recall $\varphi{(r)}$ is even since $r > 2$ and therefore we can let:

$$n - 2 = \varphi{(n)} ~ ~ \implies ~ ~ 2 \left ( 2^{k - 1} \cdot r - 1 \right ) = 2^{k - 1} \cdot \varphi{(r)} ~ ~ \implies ~ ~ 2^{k - 1} \cdot r - 1 = 2^{k - 1} \frac{\varphi{(r)}}{2}$$
Since $k > 1$, the LHS is odd, the RHS is even, and we have a contradiction.

---

So we are left with the case $k = 1$, that is, $2$ divides $n$ only once. I am stuck here There must be some simple trick though, since you said the problems are easy, so perhaps I am just missing something trivial. It would be enough that $\varphi{(r)}$ be divisible by $4$, I believe, so this would leave the case $n = 2p$ for some prime $p$ such that $p \equiv 3 \pmod{4}$ (perhaps consider the equation modulo $4$? I need to sleep now, though)

​

 

[Opalg]

I am having difficulty with the following question. Show that only n=4 satisfies g(n)=n-2, where g is the euler totient function. Well,firstly g(4)=2=4-2.

Supposing that g(n)=n-2 for some n, we see that n is not 1 or 2, so that g(n) is even.

Therefore n=g(n)+2 is even. If we suppose that n has no odd prime divisors, then we find

that g(n)=n-2 implies n=4. So it remains to consider the case where n does have odd

prime divisors, and derive a contradiction. Can anyone furnish this elusive contradiction?

I have not read through all the replies, so I am not sure if this has already been done. You have shown that the prime factorisation of $n$ must be of the form $n = 2^k\prod_\alpha p_\alpha^{k_\alpha}$, where $k>0$ and the $p_\alpha$ are the odd prime factors of $n$, if any. Then $g(n) = 2^{k-1}\prod_\alpha p_\alpha^{k_\alpha-1}(p_\alpha - 1)$. But $\prod_\alpha p_\alpha^{k_\alpha-1}(p_\alpha - 1) \leqslant \prod_\alpha p_\alpha^{k_\alpha}$ (with equality occurring only when the product is empty!). Therefore $g(n) \leqslant \frac12n$ and hence $n-2 \leqslant \frac12n$, which only occurs when $n\leqslant 4.$