proof of Euler-Fermat theorem

Let $a_{1},a_{2},\ldots,a_{\phi(n)}$ be all positive integers less than $n$ which are coprime to $n$ . Since $\text{gcd}(a,n)=1$ , then the set $aa_{1},aa_{2},\ldots,aa_{\phi(n)}$ are each congruent to one of the integers $a_{1},a_{2},\ldots,a_{\phi(n)}$ in some order. Taking the product of these congruences, we get

(aa_{1})(aa_{2})\cdots(aa_{\phi(n)})\equiv a_{1}a_{2}\cdots a_{\phi(n)}\pmod{n}

hence

a^{\phi(n)}(a_{1}a_{2}\cdots a_{\phi(n)})\equiv a_{1}a_{2}\cdots a_{\phi(n)}% \pmod{n}.

Since $\text{gcd}(a_{1}a_{2}\cdots a_{\phi(n)},n)=1$ , we can divide both sides by $a_{1}a_{2}\cdots a_{\phi(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