I am studying for my number theory final by doing past exams. The question is

Let $p \geq 5$ be a prime. Prove that if $2p+1$ not a prime. Then $\phi(n)=2p$ has no solution. ($\phi$ is Euler Totient function). In the case where $2p+1$ is prime, find all solutions to $\phi(n)=2p$.

I managed to 'prove' the first part, however without using the $2p+1$ not prime assumption. I spot if $2p+1$ is prime then $\phi(2p+1)=2p$, assuming the first part this shows that $\phi(n)=2p$ has solutions $\iff 2p+1$ is prime. But how to find all solutions? So clearly the $2p+1$ not prime assumption is needed. So my proof is wrong but I can't see where it fails (edit: as pointed out I just missed a case, the proof itself is not wrong). Can someone show me where it fails, and or provide an alternative. My proof:

Let $n=2^a\prod_{i=1}^tp_i^{\alpha_i}$ be the prime factorisation of $n$ with $a\geq 0$, and $p_i$ odd primes. Assume that $\phi(n)=2p$. Know that $$\phi(n)=\phi(2^a)\prod_{i=1}^t\phi(p_i^{\alpha_i})=2p.$$ If $t\geq 2$, then $4 \mid 2p$, since $\phi(p_i^{\alpha_i})$ is even. Hence we must have $t < 2$. If $t=0$ then $\phi(n)=2^{a-1} \neq 2p$. So we must have that $t=1$ and so we have $$n=2^ap_1^{\alpha_1}.$$ If $a>2$ then $ 4 \mid \phi(2^a) \mid 2p$, which is a contradiction. So we must have $a \leq 2$. If $a=0$ or $a=1$, then $\phi(2^a)=1$ and we have $\phi(n)=p_1^{\alpha_1-1}(p_1-1)=2p$. Hence $p_1-1=2$ and $p=p_1^{\alpha_1-1}$, which leads to $p_1=p=3$, which is a contradiction.

Hence we must have $a=2$, i.e $n=4p_1^{\alpha_1}$. Then $\phi(n)=2p_1^{\alpha_1-1}(p_1-1)=2p$. Which implies $p_1^{\alpha_1-1}(p_1-1)=p$. So either $p_1-1=p$ , in which case they are consecutive primes, contradiction as $p\geq 5$. Or $p_1^{\alpha_1-1}=p$ and $p_1-1=1$, which leads to $p_1=p=2$, also a contradiction. So all cases lead to a contradiction.


In the case that $a=0,1$, you have used that $2p+1$ is not prime when you said that $\phi(n) = p_1^{\alpha_1 -1}(p_1 -1) = 2p$ gives $p_1-1 = 2$ and $p = p_1^{\alpha_1 - 1}$. Indeed we could instead have $p_1-1 = 2p$, and $\alpha_1 = 1$. But this is ruled out since then $p_1 = 2p+1$ is not prime.

You should also note that we could, a priori, have $p_1 - 1=p$, but then $p_1$ is not prime since $p\neq 2$.

  • $\begingroup$ Very well spotted! $\endgroup$ – pureundergrad May 15 at 10:49

Suppose $\phi(n)=2p.$ Then $n\ge \phi(n)>1$ so $n>1$ so $n$ has at least one prime divisor $q$, and $(q-1) | \phi(n)=2p.$ But the only divisors of $2p$ are $1,2, p,2p$ because $p$ is prime.

So $q-1\in\{1,2,p,2p\}$ so $q\in \{2,3,p+1,2p+1\}.$ But $p+1$ is even and $>2,$ hence not prime, and $2p+1$ is not prime. So $q\in \{2,3\}.$

And $3^2\not| \,n, $ else $3|\phi(n)=2p,$ implying $3\in \{1,2,p,2p\}$ with $p\ge 5,$ which is impossible.

So $n=2^A$ or $n=2^A\cdot 3$ for some $A\in \Bbb N,$ or $n=3.$ But for each of these possible values, $\phi(n)$ is a power of $2.$


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.