0
$\begingroup$

This question already has an answer here:

Find all positive integers n such that $\phi(n)=10$.

I have found 2 positive integers: $11$ and $22$.

Is there any more?

Thanks!

$\endgroup$

marked as duplicate by Dietrich Burde, kingW3, GNUSupporter 8964民主女神 地下教會, Leucippus, Namaste Dec 20 '17 at 0:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

Write $n=p_1^{a_1}p_2^{a_2}\dots p_i^{a_i}$, where $p_1,p_2,\dots,p_i$ are distinct primes. $\phi(n)=\phi(p_1^{a_1}p_2^{a_2}\dots p_i^{a_i})=(p_1^{a_1}-p_1^{a_1-1})(p_2^{a_2}-p_2^{a_2-1})\dots(p_i^{a_i}-p_i^{a_i-1})=10$

if, say, $p_1^{a_1}-p_1^{a_1-1}=1$, then $p_1=2$ and $a_1=1$. If $p_1^{a_1}-p_1^{a_1-1}=10$, what can you say about $p_1$ and $a_1$?

Now, $10=2\times5$ is the only nontrivial factorization of $10$.

So in this case either $n=p_1^{a_1}p_2^{a_2}p_3^{a_3}$ where $p_1^{a_1}-p_1^{a_1-1}=1, p_2^{a_2}-p_2^{a_2-1}=2, p_3^{a_3}-p_3^{a_3-1}=5$, or $n=p_1^{a_1}p_2^{a_2}$ where $p_1^{a_1}-p_1^{a_1-1}=2, p_2^{a_2}-p_2^{a_2-1}=5$. There is no such $n$ which satisfies either of these.

Conclude that $n=11,22$ are the only solutions.

$\endgroup$
0
$\begingroup$

Hint: Let $p$ be a prime.

  • If $p$ divides $n$, then $p-1$ divides $\phi(n)$.

  • If $p^2$ divides $n$, then $p$ divides $\phi(n)$.

You can also use that $\phi(n) \geq \frac{\sqrt{n}}{\sqrt{2}}$ (see this question) and so limit a brute force search to $n\le 200$.

$\endgroup$

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