Question

Find all positive inegers such that n is divisible by its φ(n)

Answer 1

Answer:

We give an "examination of all cases" solution. Use the fact that φ(n) is multiplicative. Let

n=2ape11pe22⋯pekk,

where the pi are distinct odd primes, the ei are ≥1, and a≥0. Then

φ(n)=φ(2a)φ(pe11)φ(pe22)⋯φ(pekk).

We find all n such that φ(n)=6. If k≥2, then since φ(peii) is even, φ(n) is divisible by 4, so cannot be equal to 6.

If k=0, then φ(n)=φ(2a). But φ(2a)=1 if a=0 and φ(2a)=2a−1 if a≥1. So if k=0 we cannot have φ(n)=6. We conclude that k=1. Thus n must have the shape 2ape, where a≥0 and p is an odd prime.

But φ(pe)=pe−1(p−1). It follows that p≤7. If p=7, then p−1=6, so we must have e=1 and φ(2a)=1. This gives the solutions n=7 and n=14.

We cannot have p=5, for 4 divides φ(5e).

Let p=3. If e≥3, then φ(3e)≥(32)(2). So we are left with the possibilities e=1 and e=2.

If e=1, then φ(n)=φ(2a)(2). This cannot be 6.

Finally, we deal with the case e=2. Note that φ(32)=6. So to have φ(2a32)=6, we need φ(2a)=1, which gives n=9 and n=18.