The Order of an Element
Fermat
tells us a^{p-1} \equiv 1, but sometimes a smaller power of
a already returns to 1. The first one to do
so is the order of a — the length of the cycle its
powers trace out, and the key to the multiplicative structure mod n.
Definition
The order of a modulo n
(with \gcd(a,n)=1) is the smallest positive
k with
a^{k} \equiv 1 \pmod{n}.
Modulo 7, the powers of 2 go
2, 4, 1 and repeat — so 2 has order
3. The powers of 3 go
3, 2, 6, 4, 5, 1 — order 6, the longest
possible.
The divisibility law
The order of a always divides
\varphi(n). In particular
a^{k} \equiv 1 \pmod n holds if and only if the order of
a divides k.
Why? If a^{k} \equiv 1 but the order d did
not divide k, the
remainder
k \bmod d would give an even smaller power equal to
1 — contradicting minimality. Since
a^{\varphi(n)} \equiv 1 by
Euler, the
order divides \varphi(n).
Why order matters
The order tells you the size of the cyclic "orbit" a generates. Elements
of maximal order — equal to \varphi(n) itself — are special
enough to earn their own name,
primitive roots,
and they are the generators that make Diffie–Hellman key exchange and ElGamal encryption possible.