Ivory’s demonstration of Fermat’s theorem exploit the fact that given a prime p, all the numbers from 1 to p−1 are relatively prime to p (obvious since p is prime). Ivory multiply them by x and he gets:
(x)(2x)⋯((p−1)x)≡(1)(2)⋯(p−1)(modp)
which gives the theorem since I can cancel all the integers and leave:
xp−1≡1(modp).
To derive Euler’s theorem I should switch to modulus m non-prime and take the positive integers relatively prime to m and repeat the process. At this point I have ϕ(m) such numbers. How do I prove that they are all non congruent one another (to form a complete set of residues to the modulus ϕ(m)) so that I can multiply them by an x relatively prime to m and repeat the same steps to prove
xϕ(m)≡1(modm) ?
No comments:
Post a Comment