Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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