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 ProofOfEulerFermatTheorem 2013-03-22 11:47:57 2013-03-22 11:47:57 KimJ (5) KimJ (5) 10 KimJ (5) Proof msc 11A07 msc 11A25