# Another proof using the phi-function

• April 27th 2009, 11:53 PM
F350
Another proof using the phi-function
Prove the following:

1.Φ(n^k)= n^(k-1)•Φ(n)

2.Φ(Φ(p^n))=p^(n-2)•Φ((p-1)^2)
• April 29th 2009, 12:15 PM
htata123
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)
• April 29th 2009, 12:28 PM
Aryth
If I'm not mistaken, all you have to do is:

$\phi(n^k) = n^k \prod_{p|n} \left(1 - \frac{1}{p}\right)$

We know that:

$\phi(n) = n\prod_{p|n} \left(1 - \frac{1}{p}\right)$

So, with a little manipulation, we get:

$\phi(n^k) = n^{k-1}\left(n\prod_{p|n} \left(1 - \frac{1}{p}\right)\right)$

And this turns out to be:

$\phi(n^k) = n^{k-1}\phi(n)$

For the second one, note that:

$\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:

$\phi(m) = m\left(1 - \frac{1}{p}\right)$

$\phi(m) = p^{n-2}(p-1)^2$

But I'm not sure this is right, since you put $\phi((p-1)^2)$... So, hopefully this just gets you thinking.