Euler Totient. Help needed.

sutupidmath

1. The problem statement, all variables and given/known data

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.



2. Relevant 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.

3. The attempt at a solution
1. The problem statement, all variables and given/known data



2. Relevant equations



3. 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]
1. The problem statement, all variables and given/known data



2. Relevant equations



3. The attempt at a solution

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

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!