# Prove that there is no integer $n$ such that $\phi(n) = 2p$

Let $p$ be a prime number greater than $3$ such that $2p + 1$ is not prime. Prove that there is no integer $n$ such that $\phi(n) = 2p$.

-
Is this homework? What are your thoughts? What possible relevant things about the totient function do you know? –  Henning Makholm Mar 27 '13 at 23:54
By definition, $$\varphi(n)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right).$$ Can you use this definition (rather than the 'number of primes less than $n$' definition) to help what you've already done? –  Ian Coley Mar 27 '13 at 23:55

Let $n=2^ap_1^{a_1}p_2^{a_2} \cdots p_k^{a_k}$.

Case $1$: Let $a>0,k>0$, then $$\phi(n) = 2^{a-1}p_1^{a_1-1}p_2^{a_2-1} \cdots p_k^{a_k-1}(p_1-1)(p_2-1) \cdots(p_k-1)$$ This means $$2^{a+k-1} \vert \phi(n)$$ In your case, this means $a+k-1 = 1 \implies a+k=2 \implies a=k=1$. Hence, $n=2p_1$. This means $$\phi(n) = p_1-1 = 2p \implies p_1 = 2p+1$$ But we are given that $2p+1$ is not a prime. Hence this case is ruled out.

Case $2$: $a = 0$, then $$\phi(n) = p_1^{a_1-1}p_2^{a_2-1} \cdots p_k^{a_k-1}(p_1-1)(p_2-1) \cdots(p_k-1)$$ This means $$2^{k} \vert \phi(n)$$ In your case, this means $k=1$. Hence, $n=p_1$. This means $$\phi(n) = p_1-1 = 2p \implies p_1 = 2p+1$$ But we are given that $2p+1$ is not a prime. Hence this case is ruled out.

Case $3$: $k=0$, then $$\phi(n) = 2^{a-1}$$ In your case, this means $p \vert 2^{a-1}$, which is again not possible.

-

Hint: Assume by contradiction that $\phi(n)=2p$.

Let $q$ be any prime dividing $n$. Then $q-1|\phi(n)=2p$. Which are the divisors of $2p$?

We only have few choices for $q$ and it is easy to reach a contradiction...

Since there is already a complete solution, here is how you can get a fast solution with the above hint.

Assume by contradiction that $\phi(n)=2p$ for some $n$.

Let $q$ be any prime dividing $n$. Then $q-1|\phi(n)=2p$ and hence $q-1 \in \{ 1, 2, p,2p \}$. But $q-1=p$ or $q-1=2p$ is not possible.

This shows that $q=2$ pr $q=3$.

We proved that the only prime numbers dividing $n$ can only be $2$ or $3$. Thus $n=2^a3^b$ for some $a,b \geq 0$. But then $\phi(n)$ is only divisible by $2-1, 2, 3-1$ and $3$, contradiction....

-