Solving $\phi(n)=22$

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.

Answer 4

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