Welcome to our community

Be a part of something great, join today!

Number Theory Totient Function Equation

  • Thread starter
  • Banned
  • #1

Poirot

Banned
Feb 15, 2012
250
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
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
Re: another totient function problem.

[JUSTIFY]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$.[/JUSTIFY]
 
  • Thread starter
  • Banned
  • #3

Poirot

Banned
Feb 15, 2012
250
Re: another totient function problem.

[JUSTIFY]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$.[/JUSTIFY]
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.
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
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.
[JUSTIFY]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 :confused:[/JUSTIFY]
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
[JUSTIFY]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.

[HR][/HR]

So we are left with the case $k = 1$, that is, $2$ divides $n$ only once. I am stuck here :confused: 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}$ :rolleyes: (perhaps consider the equation modulo $4$? I need to sleep now, though)

[/JUSTIFY]
 
Last edited:

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,707
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.$