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}