
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 (p1)  \varphi(n)$ and $\displaystyle p^{a1}  \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^ap^{a1}=(p1)p^{a1}$
Thus $\displaystyle (p1)  \varphi(n)$ and $\displaystyle p^{a1}  \varphi(n)$.
Is this good enough?
b) I am stuck on this one.
Thanks for your help.

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

Re: totient function
for part (b) consider p^an.
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^an. a can be at most 3, since 4 is the largest power of 2 that divides 12.
if 8n, then φ(n/8) = 12/φ(8) = 3. but there is no number k for which φ(k) = 3, so 8 does not divide n.
if 4n, 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 8n, contradiction.
therefore, k can only be 7 or 9, leading to n = 28 or 36, both of which indeed have φ(n) = 12.
if 3^an, then a = 1 or 2 (since 18 does not divide 12). suppose 9n. 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.