Euler Totient Formula for Prime Powers | Help Needed for Homework

[sutupidmath]

Homework Statement

Well, the question is to find a formula for [tex]\phi(p^n)[/tex] where [tex]\phi[/tex] is the Euler's totient, and p is a positive prime.

Homework Equations

[tex]\phi(2^n)[/tex] well in this case here is what i did, i first took n=1, n=2, n=3, and it looks like

[tex]\phi(2^n)=2^{n-1}[/tex] but i am failing to prove it, because this is just by observation.

Also i tried

[tex]\phi(3^n)[/tex] and by observing what happens when, n=1,2,3 etc, this one also looks like the general formula for any n is going to be

[tex]\phi(3^n)=2*3^{n-1}[/tex] again i wasn't able to prove this one formally either.

I tried in both cases to prove it by induction, but i have a feeling that i need to know more properties about that function in order to know what operations i can perform. We, basically have only learned what euler's function is, and that's it.

The Attempt at a Solution

I really don't know whot to go about it.

Well, i gave it a shot, but nothing
say n=1 then

[tex]\phi(p)=p-1[/tex] since the group of invertibles is going to have p-1 elements.

Now, let n=2

[tex]\phi(p^2)=?[/tex]

 

[HallsofIvy]

Do you know that 1- xⁿ= (1- x)(1+ x+ x²=+ ... + x^n-2+ xⁿ)? That's all you need. The proper divisors or pⁿ are precisely 1, p, ..., p^n-1.

 

[Dick]

Do you know that 1- xⁿ= (1- x)(1+ x+ x²=+ ... + x^n-2+ xⁿ)? That's all you need. The proper divisors or pⁿ are precisely 1, p, ..., p^n-1.

It's not even that hard, is it? A number is relatively prime to p^n only if it isn't divisible by p. Count the numbers that AREN'T relatively prime to p^n (i.e. p,2p,3p,4p...p^n-p). Now count ALL the numbers less that p^n. Subtract.

 

[sutupidmath]

Well, thanks guys a lot, i see it now!