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 '19 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.$


First note that the condition $2p+1$ is not prime is necessary to prove that $phi(n)=2p$ has no solution, since $\phi(2p+1)=2p$ if $2p+1$ is prime.

Next note that if $n$ has $k$ distinct odd prime divisors $q_1,\ldots,q_k$, then $2^k \mid \phi(n)$ since $(q_1-1) \cdots (q_k-1) \mid \phi(n)$. So for $\phi(n)=2p$ to hold, $n$ can have at most one odd prime divisor. The presence of $p$ is $\phi(n)$ ensures that $n$ can't be a power of $2$. So $n$ must have exactly one odd prime divisor. This already contributes $2$ to $\phi(n)=2p$, so the power of $2$ in $n$ is at most $1$.

Thus, $n=2^e q^{\alpha}$, where $e \in \{0,1\}$ and $\alpha \ge 1$. From

$$ 2p = \phi(n) = q^{\alpha-1} (q-1) $$

we have $p \mid q$ or $p \mid (q-1)$. In the latter case, $2p \mid (q-1)$, which can only happen when $q=2p+1$. Since $2p+1$ isn't prime by assumption, the first case applies, and $q=p$. Hence, $2p=p^{\alpha-1} (p-1)$, which is only possible if $\alpha=2$ and $p-1=2$. This case is ruled out because then $2p+1=7$ is prime, and also because we assumed $p \ge 5$.

Now suppose we wish to find all $n$ such that $\phi(n)=2p$, where $2p+1$ is prime. As before, we have $2p=q^{\alpha-1} (q-1)$, and there is no solution when $p \mid q$.

So the only possibility is $p \mid (q-1)$, and in this case we must have $q=2p+1$, as seen above. We must also have $\alpha=1$. Together with $e \in \{0,1\}$, we have

$$ \phi(n) = 2p \Longleftrightarrow n = 2p+1 \:\text{or}\: 2(2p+1). $$


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.