Thread: totient function

Part (a) looks good. I don't know how to do part (b).

for part (b) consider p^a|n.

there are two cases: a = 1, in which case p = 2,3,5,7 or 13.

a > 1, in which case p = 2 or 3.

i will give something of the flavor of what you have to do. suppose 2^a|n. a can be at most 3, since 4 is the largest power of 2 that divides 12.

if 8|n, then φ(n/8) = 12/φ(8) = 3. but there is no number k for which φ(k) = 3, so 8 does not divide n.

if 4|n, then φ(n/4) = 12/φ(4) = 6. the numbers for which φ(k) = 6 are 7,9 and 14. 14 is divisible by 2, which would imply 8|n, contradiction.

therefore, k can only be 7 or 9, leading to n = 28 or 36, both of which indeed have φ(n) = 12.

if 3^a|n, then a = 1 or 2 (since 18 does not divide 12). suppose 9|n. then φ(n/9) = 12/φ(9) = 2. hence n/9 = 3,4,or 6.

since 3,6 are divisible by 3, and 27 does not divide n, we must have n = 36 (which we have already accounted for).

that leaves only products of primes to the first power as factors for n.

i leave it to you to show that 13, 2*13, 3*7, and 2*3*7 are the only possibilities left.