Thread: totient function

Hey guys, I need some help here.

a)Let $\displaystyle n$ and $\displaystyle a$ be positive integers and $\displaystyle p$ be a prime. Show $\displaystyle (p-1) | \varphi(n)$ and $\displaystyle p^{a-1} | \varphi(n)$ given $\displaystyle p^a | n$.
b) Using part a, find all positive integers n for $\displaystyle \varphi(n) =12$.

a)
Since $\displaystyle p^a | n$, this implies $\displaystyle \varphi(p^a) | \varphi(n)$
And $\displaystyle \varphi(p^a)=p^a-p^{a-1}=(p-1)p^{a-1}$
Thus $\displaystyle (p-1) | \varphi(n)$ and $\displaystyle p^{a-1} | \varphi(n)$.

Is this good enough?

b) I am stuck on this one.

Thanks for your help.

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.