phi(n) = (n)product(1-1/pj) for j = 1,......,m
phi(n^k) = (n^k)product(1-1/pj) for j = 1,.......,m (look through the def. of phi(n) to see why
phi(n^k) = n^(k-1)((n)product(1-1/pj))
phi(n^k) = (n^k-1)phi(n)
If I'm not mistaken, all you have to do is:
We know that:
So, with a little manipulation, we get:
And this turns out to be:
For the second one, note that:
Now, if we call the above answer m, we can see that p|m and we get:
But I'm not sure this is right, since you put ... So, hopefully this just gets you thinking.