1. Limited time only! Sign up for a free 30min personal 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!

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