Thread: Euler Phi function

Find all n such that phi(n) = 6. Prove there are no more.

I know phi(7), phi(9), phi(14), phi(18) = 6 and those are the only ones. However, I don't know how to show there are no others. Any advice is appreciated... Thanks.

factor n into distinct prime powers. since φ(p^k) = (p -1)(p^(k-1)) n cannot have a prime factor larger than 7.

if n has 7 as a prime factor, it can only be a single power of 7, since 7 > 6 (if k > 1, k - 1 > 1, so 7^(k-1) > 7 > 6).

if n has 5 as a prime factor, then φ(n) has (5-1)(5^(k-1)) = 4(5^(k-1)), so φ(n) has 4 as a factor, but 4 does not divide 6.

if n has 3 as a prime factor, it could either be a single power or squared power of 3, if k > 2, φ(3^k) = (2)(3^(k-1)) > 6.

if n has 2 as a prime factor, it could only be a single or double power of 2, because φ(8) = 4, and φ(16) = 8 > 6.

so we already have it whittled down to:

2
2*2
3
3*3
2*3
2*2*3
2*3*3
2*2*3*3
7
2*7
2*2*7
3*7
3*3*7
2*3*7
2*2*3*7
2*3*3*7
2*2*3*3*7

one could check all these manually. however, note that if φ(n) = 6, and 7 divides n, then φ(n/7) = 1, since φ(7) = 6. that means that 7 and 14 are the only possibilities for n divisible by 7 (since φ(k) = 1 implies k =1 or 2). that takes the last 7 off the list.

note that if 9 divides n, we have the same situation, which eliminates 36.

if n is divisible by 3, but not by 9, then since φ(3) = 2, we need φ(n/3) = 3. but φ(k) = 3 has no solutions (can you prove this? it's not hard). this eliminates 6 and 12.

φ(4) = 3, φ(3) = 2, and φ(2) = 1. none of these are 6.

so 9,18,7,14 are the only possible solutions. and these are solutions, so that's it.