14
$\begingroup$

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

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

2 Answers 2

28
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ This is a very helpful answer, thanks so much! I understand this concept much better now $\endgroup$
    – Freeman
    Commented Apr 23, 2012 at 13:29
  • $\begingroup$ 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? $\endgroup$ Commented Apr 23, 2012 at 13:35
  • $\begingroup$ Ah. Well I'm very grateful to m.k. As well. Hope they read this! $\endgroup$
    – Freeman
    Commented Apr 23, 2012 at 14:03
  • 2
    $\begingroup$ @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. $\endgroup$ Commented Apr 23, 2012 at 19:40
  • $\begingroup$ 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. $\endgroup$ Commented Nov 3, 2019 at 0:17
-2
$\begingroup$

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;
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .