proof of Euler-Fermat theorem

Let a1,a2,,aϕ(n) be all positive integers less than n which are coprimeMathworldPlanetmath to n. Since gcd(a,n)=1, then the set aa1,aa2,,aaϕ(n) are each congruentMathworldPlanetmath to one of the integers a1,a2,,aϕ(n) in some order. Taking the productPlanetmathPlanetmath of these congruencesMathworldPlanetmathPlanetmath, we get




Since gcd(a1a2aϕ(n),n)=1, we can divide both sides by a1a2aϕ(n), and the desired result follows.

Title proof of Euler-Fermat theorem
Canonical name ProofOfEulerFermatTheorem
Date of creation 2013-03-22 11:47:57
Last modified on 2013-03-22 11:47:57
Owner KimJ (5)
Last modified by KimJ (5)
Numerical id 10
Author KimJ (5)
Entry type Proof
Classification msc 11A07
Classification msc 11A25