# $p \geq 5$ prime. $2p+1$ not a prime. Then $\phi(n)=2p$ has no solution.

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

• Very well spotted! – 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).$$