= Multiplication by a unit permutes reduced residues
{title2=$u\mapsto au\quad\text{on }U(n)$}
Choose a <reduced residue system> $u_1,\ldots,u_{\varphi(n)}$. For a <unit modulo n> $a$, the <bijection> $u\mapsto au$ on the <unit group> has inverse $u\mapsto a^{-1}u$. Comparing products before and after this <permutation> gives
$$
P=\prod_{i=1}^{\varphi(n)}u_i
\equiv\prod_{i=1}^{\varphi(n)}(au_i)
=a^{\varphi(n)}P\pmod n.
$$
The product $P$ is a <unit>; its <modular inverse> cancels it, proving <Euler's theorem>. Merely being nonzero would not justify cancellation.<Euler’s Theorem by Keith Conrad>[pp. 2–3, Section 2: permutation of the units, comparison of products, cancellation]{ref}
In the modulo-twelve example, $P=1\cdot5\cdot7\cdot11=385\equiv1\pmod{12}$. The permuted representatives $5,1,11,7$ have the same product, while the unreduced products $(5\cdot1)(5\cdot5)(5\cdot7)(5\cdot11)$ equal $5^4P$. Equating these products modulo twelve exposes the fourth power without calculating it directly. Using all nonzero <congruence classes> instead would include <nonunits>, whose product need not permit cancellation.
Back to article page
