# How do you find all $n$ such that $\phi(n)|n$

Where $\phi(n)$ is the Euler phi function, how do you find all $n$ such that $\phi(n)|n$?

• Commented Apr 23, 2012 at 12:24
• Use the formula for the totient function in terms of the prime factors of n. Commented Apr 23, 2012 at 12:32
• @dayo Adeyemi: I do this and find all the prime factors must be consecutative, therefore can only be $2$ or $3$? Commented Apr 23, 2012 at 12:35
• @LHS think about it. Can $n$ be prime? or Can $n$ be odd? Commented Apr 23, 2012 at 12:42
• @Kv Raman: n can't be prime, unless it equals the totient function, however I'm assuming it can't be odd either? Commented Apr 23, 2012 at 12:47

Notice that $$\varphi(1) = \varphi(2) = 1$$, so $$\varphi(1) \mid 1$$ and $$\varphi(2) \mid 2$$.

If $$n > 2$$, assume that the prime factorization of $$n$$ is

$$n = p_1^{a_1} \ldots p_k^{a_k}$$

Then the formula for the totient function gives

$$\varphi(n) = (p_1 - 1)p_1^{a_1-1}\ldots (p_k - 1)p_k^{a_k-1}.$$

Since $$n>2$$, this is always an even number, so $$p_1=2$$ must appear as a factor. We next observe that $$n$$ cannot have two odd prime factors. If $$a_2>0$$ and $$a_3>0$$, then both $$p_2-1$$ and $$p_3-1$$ are even, so $$2^{a_1+1}\mid \varphi(n)$$, which is a contradiction.

So $$n=2^{a_1}p^{a_2}$$ for some prime $$p>2$$. Here $$p-1\mid\varphi(n)\mid n$$, so $$p-1$$ must be a power of two, say $$p-1=2^\ell$$. Then $$2^{a_1-1+\ell}\mid\varphi(n)$$, so we must have $$\ell=1$$ and $$p=3$$.

In the end we can verify that $$n=1$$ or $$n=2^a3^b$$, with $$a>0$$, $$b\ge0$$.

• This is a very helpful answer, thanks so much! I understand this concept much better now Commented Apr 23, 2012 at 13:29
• I feel a bit bad about this. This was meant to address the point left open in m.k.'s answer. But while I was typing, that was deleted. I guess there is a lesson to be learned here? Commented Apr 23, 2012 at 13:35
• Ah. Well I'm very grateful to m.k. As well. Hope they read this! Commented Apr 23, 2012 at 14:03
• @LHS There are at least a couple prior questions on this topic, so you might find some other prior answers also of interest. Please link them into this question if you find them. Commented Apr 23, 2012 at 19:40
• This may not be all solutions for $n$. We assume the existence of a prime factorization but $n=1$ has none. This value of $n$ must be considered separately to assess whether $\phi(1)|1$. Please edit to include this case. Commented Nov 3, 2019 at 0:17

Quasi-brute-force approach using Maple :

with(numtheory):
for n from 1 to 100 do
if n mod phi(n) = 0 then
print(n);
end if;
end do;