Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proofing Euler's Phi Function.

  1. Jan 4, 2010 #1
    Generally, I am stumped by the Phi function. I have found out the pattern but I am having difficulty proving it.

    1. The problem statement, all variables and given/known data
    i) When p is a prime number, obtain an expression in terms of p for:-
    ϕ(p²)


    2. Relevant equations
    ϕ(p)=p-1



    3. The attempt at a solution
    ϕ(p)=p-1
    so ϕ(5)=4 therefore p²=5²=25 therefore ϕ(p²)=20
    Also, if p=3 then ϕ(3)=2 therefore ϕ(9)=6

    It appears that ϕ(p²)= p(p-1)

    My problem is that I am not able to proof it. Yes, the pattern is p(p-1) but I am stuck as to how to explain it. Any soloutions?
     
  2. jcsd
  3. Jan 4, 2010 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Just use the definition of phi. phi(p^2) is the number of integers less than p^2 that are relatively prime to p^2. If a number is NOT relatively prime to p^2 then it must be divisible by p. How many numbers less than p^2 are divisible by p?
     
  4. Jan 5, 2010 #3

    But how would you then mvoe onto p^3? Would p^3 then be p(p(p-1) or am I wrong. If I take what you say which is that If a number is NOT relatively prime to p^2 then it must be divisible by p Then can I apply the same rule to p^3?
     
  5. Jan 5, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes. You can apply the same rule to p^3 if p is prime.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook