Euler's theorem

Let $R=\{r_1,\dots,r_{\varphi(n)}\}$ be a reduced residue system modulo $n$: representatives of every residue class coprime to $n$.

Multiplication by $a$ permutes $R$: for each $r_i$, $\gcd(ar_i,n)=1$ because $\gcd(a,n)=1$ and $\gcd(r_i,n)=1$ (a product is coprime to $n$ iff both factors are), so $ar_i \bmod n$ is again a member of the coprime residue classes; and the map $r_i\mapsto ar_i \bmod n$ is injective by the cancellation law, since $\gcd(a,n)=1$.

An injective map from the finite set $R$ to itself (up to residue) is a bijection, so $\{ar_1,\dots,ar_{\varphi(n)}\} \pmod n$ is just $\{r_1,\dots,r_{\varphi(n)}\}$ reordered.

Multiplying all $\varphi(n)$ elements of each set: $a^{\varphi(n)}\, (r_1 r_2\cdots r_{\varphi(n)}) \equiv r_1 r_2 \cdots r_{\varphi(n)} \pmod n$. Since each $r_i$ is coprime to $n$, so is their product $R=\prod r_i$, i.e. $\gcd(R,n)=1$.

Cancel $R$ from both sides (valid since $\gcd(R,n)=1$) to get $a^{\varphi(n)}\equiv1\pmod n$. $\blacksquare$

This is again Lagrange's theorem in disguise: the residues coprime to $n$ form a group of order $\varphi(n)$ under multiplication (the group of units $(\mathbb{Z}/n\mathbb{Z})^{*}$), and the order of any element divides $\varphi(n)$.