Euler's Theorem

Eulers Theorem (1760)

• If $n\ge 1$ and $\gcd (a,n)=1$, then $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$

Proof!

Lemma) Reordering a set of co-prime numbers

• Let $S=\{a_1,...,a_{\varphi (n)}\}$, where $\gcd (a_i,n)=1$ We construct another set, call it $T=\{a\cdot a_1,...,a\cdot a_{\varphi (n)}\},a\in S$. We claim that $S=T$.

Proof

In multiplying by an arbitrary element in S, we transposed the elements in the set. Hence a transposition of elements in the set results in two equal sets

• Using the above lemma, we can do the following: (note: $\sigma$ is being used as a group action to denote the transposition of the index)

$$\begin{array}{rl}(a\cdot a_1)\cdot ...\cdot (a\cdot a_{\varphi (n)})& \equiv a_{\sigma (1)}\cdot ...\cdot a_{\sigma (\varphi (n))}(\mathrm{mod}n)\\ (a^{\varphi (n)})(a_1\cdot ...\cdot a_{\varphi (n)})& \equiv a_1\cdot ...\cdot a_{\varphi (n)}(\mathrm{mod}n)\\ a^{\varphi (n)}& \equiv 1(\mathrm{mod}n)\end{array}$$