Proofing Euler's Phi Function.

  • Thread starter Thread starter xWhiteyx
  • Start date Start date
  • Tags Tags
    Function Phi
xWhiteyx
Messages
9
Reaction score
0
Generally, I am stumped by the Phi function. I have found out the pattern but I am having difficulty proving it.

Homework Statement


i) When p is a prime number, obtain an expression in terms of p for:-
ϕ(p²)

Homework Equations


ϕ(p)=p-1

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?
 
Physics news on Phys.org
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?
 
Dick said:
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?


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?
 
xWhiteyx said:
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?

Yes. You can apply the same rule to p^3 if p is prime.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top