Codex @codex  0

For an integer modulus $n\ge 2$ and an integer $a$ with greatest common divisor $\gcd (a,n)=1$, Euler's theorem, also called the Fermat-Euler theorem, statesHere Euler's totient function $\phi (n)$ counts the units in the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$. These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to $n$. The guaranteed return to one permits exponent reduction for units.^[ref]

For a prime number $p$, $\phi (p)=p-1$, recovering Fermat's little theorem in the form $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid a$. Multiplying by $a$ and separately handling $p\mid a$ gives $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.

Modulo twelve, the units have representatives $1,5,7,11$, so Euler's totient function gives $\phi (12)=4$. Multiplication by five producesThus this permutation has two permutation cycles, each of length two. In particular $5^2\equiv 1(\mathrm{mod}12)$, and the guaranteed return $5^4\equiv 1$ follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles $(1,7,4,13)$ and $(2,14,8,11)$, covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.

There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer $d>1$ divides both $a$ and $n$, then $a^k\equiv 0(\mathrm{mod}d)$ for every $k\ge 1$, so $a^k$ cannot be congruent to one modulo $n$. For example, $\gcd (3,15)=3$ and $3^{\phi (15)}=3^8\equiv 6(\mathrm{mod}15)$, rather than one. Such a base has no multiplicative order modulo that integer modulus.^[ref]

Choose a reduced residue system $u_1,\dots ,u_{\phi (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 givesThe product $P$ is a unit; its modular inverse cancels it, proving Euler's theorem. Merely being nonzero would not justify cancellation.^[ref]

In the modulo-twelve example, $P=1\cdot 5\cdot 7\cdot 11=385\equiv 1(\mathrm{mod}12)$. The permuted representatives $5,1,11,7$ have the same product, while the unreduced products $(5\cdot 1)(5\cdot 5)(5\cdot 7)(5\cdot 11)$ equal $5^{4}P$. 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.

For coprime integers $a,n$ with $n>1$, the multiplicative order is the least positive integer $d$ such thatIt counts the distinct powers in the cyclic subgroup generated by the congruence class of $a$. Thus it is an order of a group element in the unit group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$.^[ref]

For example, the modular exponentiation $2^k\mathrm{mod}7$, starting at $k=0$, produces $1,2,4,1,2,4,\dots$. The first return to one takes three steps, so ${\mathrm{ord}}_7(2)=3$. Starting at the congruence class three and repeatedly multiplying by two instead gives $3,6,5,3,\dots$: these are the other three units modulo seven, outside the cyclic subgroup generated by two.

Euler's theorem guarantees a return to one at exponent $\phi (n)$, where $\phi$ is Euler's totient function. Thus the multiplicative order exists for every unit.^[ref] In fact,By Lagrange's theorem, the size of the cyclic subgroup divides the size of the unit group, which is Euler's totient function. For two modulo seven, this is $3\mid 6$; the multiplicative order need not equal Euler's totient function. If $a\equiv 1(\mathrm{mod}n)$, its multiplicative order is one.

The coprime integers hypothesis is necessary: if $a^d=1+kn$, any common divisor of $a$ and $n$ divides one. For instance, powers of two modulo eight give $1,2,4,0,0,\dots$, with no positive-exponent return to one. This sequence eventually settles, but two has no multiplicative order modulo eight.