Euler phi-function?

Question

Find all positive integers n such that phi(n)=6. Prove that you have found all solutions.

Thanks

Answer 1

7, 9, 14, 18

Proof that this list is exhaustive: Suppose φ(n) = 6 and p is a prime number such that p|n. Then p-1 will be a factor of φ(n), so since the only factors of φ(n) are 1, 2, 3, and 6, it follows that p must be 2, 3, 4, or 7. Obviously, 4 is right out, since it is not prime. So we have n = 2^k₁ 3^k₂ 7^k₃. We know that k₃ is at most 1, since if k₃≥2, φ(n) would have a factor of 7, which it doesn't. So suppose k₃=1 -- then k₂ must be zero, or else φ(n) would have 2 distinct factors of 2 (one from 7-1, the other from 3-1), which it doesn't. And obviously, we cannot have k₁≥2, or else again φ(n) would have 2 distinct factors of 2. Therefore, if k₃=1, then k₁ is either 0 or 1, and thus n is either 7 or 14.

So now consider the other possibility, that k₃=0. If additionally k₂≤1, we have that φ(n) contains no factors of 3, and that is not the case. So we have k₂≥2. We also have k₂≤2, since if k₂>2, then φ(n) contains two distinct factors of 3, and it doesn't. So in fact k₂=2. This means that φ(n) already contains 1 factor of 2 (from 3-1). If k₁≥2, then it would contain a second factor of 2, and it does not. So k₁ must be either 0 or 1, which means that if k₃=0, then n = 9 or 18.

Thus the only possibilities are 7, 9, 14, 18. And we are done.