Fermet Euler Theorem

Math NT

Theorem

Let $a$ and $m$ be coprime numbers.

$$a^{\varphi (m)}\equiv 1\mathrm{mod}m$$

This is a generalization of Fermet’s Little Theorem, as $m$ is a prime number in Fermet’s Little Theorem.

Proof

Let:

$$\begin{gathered} A=\{p_1,p_2,p_3,...p_{\varphi (m)}\}\mathrm{mod}m \\ B=\{a{p}_1,a{p}_2,a{p}_3,...a{p}_{\varphi (m)}\}\mathrm{mod}m \end{gathered}$$

Where $p_x$ is the $x$th number relatively prime to $m$.

Since $a$ and $p_x$ are coprime to $m$, $a{p}_x$ is coprime to $m$. Since each $p_x$ is unique, $a{p}_x$ is unique, which makes set $B$ the same as set $A$.

Since all terms are coprime to $m$:

$$\begin{gathered} a^{\varphi (m)}\prod _{k=0}^{\varphi (m)}{p}_k\equiv \prod _{k=0}^{\varphi (m)}{p}_k\mathrm{mod}m \\ {a}^{\varphi (m)}\equiv 1\mathrm{mod}m \end{gathered}$$