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

  • Thread starter Thread starter Poirot1
  • Start date Start date
  • Tags Tags
    Function
Poirot1
Messages
243
Reaction score
0
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
 
Mathematics news on Phys.org
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$.​
 
Re: another totient function problem.

Bacterius said:
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.
 
Re: another totient function problem.

Poirot said:
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 :confused:
 
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 :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)

 
Last edited:
Poirot said:
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.$
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
Back
Top