# Euler Totient. Help needed.

1. Nov 20, 2008

### sutupidmath

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

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

2. Relevant equations

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

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

Also i tried

$$\phi(3^n)$$ 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

$$\phi(3^n)=2*3^{n-1}$$ 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

$$\phi(p)=p-1$$ since the group of invertibles is going to have p-1 elements.

Now, let n=2

$$\phi(p^2)=??????$$
1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

2. Nov 20, 2008

### HallsofIvy

Staff Emeritus
Do you know that 1- xn= (1- x)(1+ x+ x2=+ ... + xn-2+ xn)? That's all you need. The proper divisors or pn are precisely 1, p, ..., pn-1.

3. Nov 20, 2008

### 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.

4. Nov 20, 2008

### sutupidmath

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