I want to prove the following:

Let $n \in \mathbb{N}$. Then, if

$$2\varphi(n) + 2 = n$$

holds, there exists an odd prime $p$ such that $n=2p$.

My guess is that one can use the multiplicative property of the totient function. For coprime numbers $m,n$

$$\varphi(m * n) = \varphi(m) \varphi(n)$$

In our case: $\varphi(2p) = \varphi(2) \varphi(p) = \varphi(p)$

  • $\begingroup$ Would it help to factor out a $2$? $\endgroup$ – Mike Aug 26 '16 at 9:39

The LHS is divisible by $2$, therefore RHS is divisible by $2$. Assume $n=2k$ with $k\in{\mathbb{Z}}$. In that case the equation becomes $$ 2\varphi(2k)+2=2k $$ which is equivalent to $$ \varphi(2k)+1=k. $$ If $k$ is odd, this yields $\varphi(k)=k-1$ by multiplicative property and therefore $k$ is prime and we are done. We like to show that this is the only possibility. Assume $k$ is even, write $k=2^m l$ with maximal $m$. Therefore $$ \varphi(2^{m+1}l)+1=2^ml. $$ Again using the multiplicative property of $\varphi$ this gives us $$ (2^{m+1}-2^m)\varphi(l)+1=2^ml $$ Here the RHS is divisible by $2$, but the LHS is not, which is a contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.