Euler’s totient function:

Euler’s totient function is defined as follows:

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

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

$$a^{\phi(n)} \equiv 1 \pmod{n}$$

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:

$$U_n = \{u_n\}_{n=1}^{\phi(n)}$$

Now, if we define:

$$a \cdot U_n = \{a \cdot u_n\}_{n=1}^{\phi(n)}$$

we have:

$$\prod_{n=1}^{\phi(n)} u_n \equiv 1 \pmod{n}$$

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

and so by the cancellation law, we have:

$$a^{\phi(n)} \equiv 1 \pmod{n}$$