Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
mathforum.org/kb/… and oeis.org/A007694 –  Beni Bogosel Apr 23 '12 at 12:24
2  
Use the formula for the totient function in terms of the prime factors of n. –  Dayo Adeyemi Apr 23 '12 at 12:32
    
@dayo Adeyemi: I do this and find all the prime factors must be consecutative, therefore can only be $2$ or $3$? –  Freeman Apr 23 '12 at 12:35
1  
@LHS think about it. Can $n$ be prime? or Can $n$ be odd? –  Kirthi Raman Apr 23 '12 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? –  Freeman Apr 23 '12 at 12:47

2 Answers 2

up vote 8 down vote accepted

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

If $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=2^a3^b$, with $a>0$, $b\ge0$ is a solution.

share|improve this answer
    
This is a very helpful answer, thanks so much! I understand this concept much better now –  Freeman Apr 23 '12 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? –  Jyrki Lahtonen Apr 23 '12 at 13:35
    
Ah. Well I'm very grateful to m.k. As well. Hope they read this! –  Freeman Apr 23 '12 at 14:03
1  
@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. –  Bill Dubuque Apr 23 '12 at 19:40

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;
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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