Prove the following:

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

2.Φ(Φ(p^n))=p^(n-2)•Φ((p-1)^2)

Printable View

- April 28th 2009, 12:53 AMF350Another 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, 01:15 PMhtata123
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, 01:28 PMAryth
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.