1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Euler Totient. Help needed.

  1. Nov 20, 2008 #1
    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
     
  2. jcsd
  3. Nov 20, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  4. Nov 20, 2008 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. Nov 20, 2008 #4
    Well, thanks guys a lot, i see it now!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Euler Totient. Help needed.
  1. Euler function-totient (Replies: 3)

  2. Euler's Formula help (Replies: 4)

Loading...