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)\cdots((p-1)x)\equiv(1)(2)\cdots(p-1)\pmod{p}
which gives the theorem since I can cancel all the integers and leave:
x^{p-1}\equiv1\pmod{p}.
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 \phi(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 \phi(m)) so that I can multiply them by an x relatively prime to m and repeat the same steps to prove
x^{\phi(m)}\equiv1\pmod{m} ?
No comments:
Post a Comment