= Nonzero residue permutation
{title2=$x\mapsto ax\pmod p$}
For a <prime number> $p$ and $p\nmid a$, <multiplication> by $a$ gives a <permutation> of the $p-1$ nonzero <residue classes>. For $a=3$ modulo seven, the representatives $1,2,3,4,5,6$ map to $3,6,2,5,1,4$: the same collection in a different order. Repeating this <permutation> from one visits all six representatives before returning.
\Image[/fermat-prime-residue-permutation.png]
{title=<Multiplication> by three modulo seven permutes all six nonzero <residue classes>}
{id=fermat-prime-residue-permutation}
{description=The upper arrows show each input and its image. The lower arrows repeatedly apply the same <permutation> to one, displaying the powers $3^0,\ldots,3^6$ modulo seven. The highlighted final one is the first positive return, at <exponent> six.}
For $a=2$ modulo seven, the <permutation cycles> are instead $(1,2,4)$ and $(3,6,5)$. The powers of two visit only the <permutation cycle> containing one, so their <multiplicative order> is three. Both <permutation cycles> return after three steps; applying the <permutation> six times still fixes every nonzero <residue class>. <Fermat's little theorem> guarantees a return at six, not that every base visits every nonzero <residue class>.
\Image[/fermat-prime-residue-short-cycles.png]
{title=<Multiplication> by two modulo seven gives two <permutation cycles> of length three}
{id=fermat-prime-residue-short-cycles}
{description=Every arrow multiplies by two modulo seven. The left <permutation cycle> contains one and hence the powers of two. The right <permutation cycle> contains the other three nonzero <residue classes>. Their common length three divides $p-1=6$.}
More generally, every <permutation cycle> of this map has length equal to the <multiplicative order> of $a$: starting at a nonzero <residue class> $x$, a return means $a^kx\equiv x\pmod p$, and its <modular multiplicative inverse> allows cancellation of $x$. Thus the $p-1$ nonzero <residue classes> split into equal-length <permutation cycles>, which also explains the <divisibility> of the <multiplicative order> into $p-1$.
The product argument gives a short proof outline. Since <multiplication> by $a$ is a <permutation> of the nonzero <residue classes>,
$$
\prod_{r=1}^{p-1}r\equiv\prod_{r=1}^{p-1}(ar)
=a^{p-1}\prod_{r=1}^{p-1}r\pmod p.
$$
Every factor is a <unit>, so their product has a <modular multiplicative inverse> and can be cancelled. This leaves $a^{p-1}\equiv1\pmod p$. The whole argument works for $p=2$, where the product is just one.<Euler’s Theorem by Keith Conrad>[p. 2, proof of Theorem 1.1: the sets S and aS, product comparison and cancellation]{ref}
Back to article page
