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.
$\endgroup$ 44 Answers
$\begingroup$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$.
$\endgroup$ 3 $\begingroup$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$.
$\endgroup$ $\begingroup$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.
$\endgroup$ 9 $\begingroup$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.
$\endgroup$ 1
