Prove the following:

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

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

Printable View

- Apr 27th 2009, 11:53 PMF350Another proof using the phi-function
Prove the following:

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

2.Φ(Φ(p^n))=p^(n-2)•Φ((p-1)^2) - Apr 29th 2009, 12: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) - Apr 29th 2009, 12:28 PMAryth
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.