# Solving $\phi(n)=22$

Find all positive integers n such that $\phi(n) = 22$ and prove that there are no others. Here $\phi$ denotes the Euler $\phi$-function.

• I think the fact that if $n=\prod p_{i}^{a_{i}}$, then $\phi(n) = \prod p_{i}^{a_{i}-1}\cdot (p_{i}-1)$ will help. – Chris K Nov 30 '13 at 2:44
• Given the two posted hints, there are two $23$ and $46$. – Amzoti Nov 30 '13 at 2:48
• I need a rigorous proof that 23 is the only solution. – leo Nov 30 '13 at 2:56
• Similar questions (with different numbers): math.stackexchange.com/questions/101566/… and math.stackexchange.com/questions/127998/… – Martin Sleziak Dec 1 '13 at 17:14

Hint: Suppose that $\varphi(n) = 22$. Then if we factor $n = p_1^{\alpha_1} \cdots p_k^{\alpha_k}$ then

$$22 = p_1^{\alpha_1} \cdots p_k^{\alpha_k} \left(1 - \frac{1}{p_1}\right) \cdots \left(1 - \frac{1}{p_k}\right) = (p_1^{\alpha_1} - p_1^{\alpha_1 - 1}) \cdots (p_k^{\alpha_k} - p_k^{\alpha_k - 1})$$

Now use the fact that the only divisors of $22$ are $1, 2, 11, 22$.

• I need a rigorous proof that 23 is the only solution – leo Nov 30 '13 at 2:56
• @leo Which is why I've marked my answer as a hint - it's not too hard given that there's only a few ways to factor $22$; consider the problem for a while. – user61527 Nov 30 '13 at 2:59
• @leo 23 is NOT the only solution. – N. S. Nov 30 '13 at 15:18

Observe that $n$ cannot be a power of $2$, since in that case $\phi(n)$ would also be a power of two.

This means that $n$ is divisible by an odd prime.

If $p$ and $q$ are two distinct odd primes dividing $n$, then $\phi(n)$ is divisible by $(p-1)(q-1)$ which is a multiple of $4$. But this is not possible.

Thus $n$ is divisible by exactly 1 odd prime. Then, it must have the form

$$n=2^ap^b \, 0 \leq a, 1 \leq b \,.$$

Now, $p-1 |\phi(n)=22$ thus $p-1 \in \{1,2,11, 22 \}$. As $p-1$ is even, the only possibilities are $p-1=2$ or $p-1=22$.

This reduces the problem to two cases.

If $p=3$ then $n=2^a3^b$ with $b >0$ and $a \geq 0$. It is easy to argue there is no solution here.

If $p=23$ then $n=2^a23^b$ with $b >0$ and $a \geq 0$. Then, you need to argue that $b=1$, in which case $n=2^a23$. Then

$$22 =\phi(2^a)\phi(23)=22 \phi(2^a) \Rightarrow \phi(2^a)=1$$

This has two solutions $a=0$ and $a=1$, which yield $n=23$ and $n=46$.

Hints: Note that $23$ is prime and $\phi(p)=p-1$ for all primes $p$, since all positive integers less than $p$ are relatively prime to $p$. Thus, $n=23$ is a solution. To find out if there are other solutions, consider Formula for Euler's Totient Function. Since you haven't elaborated on your solution, I'll leave it there for now.

• can you please help me show how to use this formula to show that 23 is the only solution. thanks! – leo Nov 30 '13 at 2:57
• @leo I hesitate because you haven't shown any work. As per the rules of StackExchange, you should show us that you have made an attempt before we can help you. Sorry. – Ahaan S. Rungta Nov 30 '13 at 3:01
• @leo I'll give you another hint just because I feel like I'm being mean. Try factorizing $22$ and match it up with the formula. – Ahaan S. Rungta Nov 30 '13 at 3:02
• @leo It's fine, I understand. At least we can see now that you're trying. So hint: there are only 4 divisors. – Ahaan S. Rungta Nov 30 '13 at 3:18
• 23 is NOT the only solution. – N. S. Nov 30 '13 at 15:17

In fact, there are two solutions, namely $23$ and $46$. Also, there is a more general result, namely: If $p$ is a prime number with $p>3$ and $2p+1$ is prime, then there are exactly two numbers $n$ such that $\phi (n) = 2p$, namely $2p+1$ and $4p+2$. Also, there is the Carmichael conjecture (still open, as far as I know) which says that there is no number in the image of phi having a unique antecedent. In my article "Some remarks on Euler's totient function", I discuss these questions and others.

• Please use $\LaTeX$. Done for you this time. +1 for a good answer. :) – Ahaan S. Rungta Nov 30 '13 at 15:25