1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Chris K Nov 30 '13 at 2:44
  • 1
    $\begingroup$ Given the two posted hints, there are two $23$ and $46$. $\endgroup$ – Amzoti Nov 30 '13 at 2:48
  • $\begingroup$ I need a rigorous proof that 23 is the only solution. $\endgroup$ – leo Nov 30 '13 at 2:56
  • $\begingroup$ Similar questions (with different numbers): math.stackexchange.com/questions/101566/… and math.stackexchange.com/questions/127998/… $\endgroup$ – Martin Sleziak Dec 1 '13 at 17:14
9
$\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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I need a rigorous proof that 23 is the only solution $\endgroup$ – leo Nov 30 '13 at 2:56
  • 3
    $\begingroup$ @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. $\endgroup$ – user61527 Nov 30 '13 at 2:59
  • 4
    $\begingroup$ @leo 23 is NOT the only solution. $\endgroup$ – N. S. Nov 30 '13 at 15:18
5
$\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$.

|cite|improve this answer
$\endgroup$
4
$\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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ can you please help me show how to use this formula to show that 23 is the only solution. thanks! $\endgroup$ – leo Nov 30 '13 at 2:57
  • 1
    $\begingroup$ @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. $\endgroup$ – Ahaan S. Rungta Nov 30 '13 at 3:01
  • $\begingroup$ @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. $\endgroup$ – Ahaan S. Rungta Nov 30 '13 at 3:02
  • 1
    $\begingroup$ @leo It's fine, I understand. At least we can see now that you're trying. So hint: there are only 4 divisors. $\endgroup$ – Ahaan S. Rungta Nov 30 '13 at 3:18
  • 6
    $\begingroup$ 23 is NOT the only solution. $\endgroup$ – N. S. Nov 30 '13 at 15:17
2
$\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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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