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.$
 
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...
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...
I'm interested to know whether the equation $$1 = 2 - \frac{1}{2 - \frac{1}{2 - \cdots}}$$ is true or not. It can be shown easily that if the continued fraction converges, it cannot converge to anything else than 1. It seems that if the continued fraction converges, the convergence is very slow. The apparent slowness of the convergence makes it difficult to estimate the presence of true convergence numerically. At the moment I don't know whether this converges or not.
Back
Top