Euler’s totient function:

Euler’s totient function is defined as follows:

\begin{equation} \phi(n) = |\{k \in [1,n]: \text{gcd}(n,k)=1\}| \end{equation}

i.e. $$\phi(n)$$ counts the number of positive integers $$k \in [1,n]$$ that are relatively prime to $$n$$.

Euler’s theorem:

For any $$a,n \in \mathbb{N}^*$$, if $$\text{gcd}(a,n)=1$$ then

\begin{equation} a^{\phi(n)} \equiv 1 \pmod{n} \end{equation}

Proof:

Let $$U_n \subset \mathbb{N}^*$$ be the set of all positive integers less than $$n$$ that are relatively prime to $$n$$. By definition, $$|U_n| = \phi(n)$$ and so we have:

\begin{equation} U_n = \{u_n\}_{n=1}^{\phi(n)} \end{equation}

Now, if we define:

\begin{equation} a \cdot U_n = \{a \cdot u_n\}_{n=1}^{\phi(n)} \end{equation}

we have:

\begin{equation} \prod_{n=1}^{\phi(n)} u_n \equiv 1 \pmod{n} \end{equation}

\begin{equation} \prod_{n=1}^{\phi(n)} a \cdot u_n \equiv a^{\phi(n)} \prod_{n=1}^{\phi(n)} u_n \pmod{n} \end{equation}

and so by the cancellation law, we have:

\begin{equation} a^{\phi(n)} \equiv 1 \pmod{n} \end{equation}