proof of Euler-Fermat theorem

Let $a_1,a_2,\mathrm{\dots },a_{\varphi (n)}$ be all positive integers less than $n$ which are coprime to $n$. Since $\text{gcd}(a,n)=1$, then the set $a{a}_1,a{a}_2,\mathrm{\dots },a{a}_{\varphi (n)}$ are each congruent to one of the integers $a_1,a_2,\mathrm{\dots },a_{\varphi (n)}$ in some order. Taking the product of these congruences, we get

$$(a{a}_1)(a{a}_2)\mathrm{\cdots }(a{a}_{\varphi (n)})\equiv a_1{a}_2\mathrm{\cdots }{a}_{\varphi (n)}(modn)$$

hence

$$a^{\varphi (n)}(a_1{a}_2\mathrm{\cdots }{a}_{\varphi (n)})\equiv a_1{a}_2\mathrm{\cdots }{a}_{\varphi (n)}(modn).$$

Since $\text{gcd}(a_1{a}_2\mathrm{\cdots }{a}_{\varphi (n)},n)=1$, we can divide both sides by $a_1{a}_2\mathrm{\cdots }{a}_{\varphi (n)}$, and the desired result follows.