Prove the following:
1.Φ(n^k)= n^(k-1)•Φ(n)
2.Φ(Φ(p^n))=p^(n-2)•Φ((p-1)^2)
If I'm not mistaken, all you have to do is:
$\displaystyle \phi(n^k) = n^k \prod_{p|n} \left(1 - \frac{1}{p}\right)$
We know that:
$\displaystyle \phi(n) = n\prod_{p|n} \left(1 - \frac{1}{p}\right)$
So, with a little manipulation, we get:
$\displaystyle \phi(n^k) = n^{k-1}\left(n\prod_{p|n} \left(1 - \frac{1}{p}\right)\right)$
And this turns out to be:
$\displaystyle \phi(n^k) = n^{k-1}\phi(n)$
For the second one, note that:
$\displaystyle \phi(p^n) = p^n - p^{n-1} = p^{n-1}(p - 1)$
Now, if we call the above answer m, we can see that p|m and we get:
$\displaystyle \phi(m) = m\left(1 - \frac{1}{p}\right)$
$\displaystyle \phi(m) = p^{n-2}(p-1)^2$
But I'm not sure this is right, since you put $\displaystyle \phi((p-1)^2)$... So, hopefully this just gets you thinking.