Primitive Roots and the Structure of Residues
Modulo every prime there is a residue whose powers run through all the others, and this unit proves it by counting the residues of each order, after Lagrange's theorem on polynomial congruences has limited how many roots a congruence can have. It works out which moduli have such a primitive root, turns multiplication into addition with Gauss's indices, explains why the digits of 1/7 repeat every six places, and ends with the Diffie-Hellman key exchange, the discrete logarithm problem behind it, and the attack of 2015 that broke it for shared 512-bit primes.
The fraction \(1/7\) has the decimal expansion \(0.142857\,142857\ldots\), which repeats after six digits, and \(1/13\) repeats after six digits as well, although \(13\) is the larger denominator. Modulo \(11\) there are residues whose powers run through every non-zero residue before they return to \(1\), and modulo \(8\) there is none. A web browser that opens a secure connection runs a key exchange which, in its classical form, raises a number to a secret power modulo a prime with several hundred digits, and the exchange relies on nobody being able to undo that operation. All three observations concern the cycle of the powers of a residue, and this unit works out its structure. Modulo every prime the powers of one residue produce all the others, and the applications run from the index tables of the Disquisitiones Arithmeticae (1801) to the key exchange behind most secure connections on the internet.
1 The order of a residue
Unit 5 defined the multiplicative order \(\operatorname{ord}_n(a)\) of a residue \(a\) coprime to \(n\) as the least exponent \(k \ge 1\) with \(a^{k} \equiv 1 \pmod n\), proved that \(a^{k} \equiv 1 \pmod n\) holds exactly when \(\operatorname{ord}_n(a)\) divides \(k\), and concluded from Euler’s theorem that the order divides \(\varphi(n)\). Two consequences of that divisibility rule carry the whole unit.
The first is that the powers \(a, a^{2}, \ldots, a^{d}\), where \(d = \operatorname{ord}_n(a)\), are all different modulo \(n\). If \(a^{i} \equiv a^{j}\) with \(1 \le i < j \le d\), then multiplying by the inverse of \(a^{i}\) gives \(a^{j - i} \equiv 1\) with \(0 < j - i < d\), which contradicts the choice of \(d\) as the least such exponent. So the cycle of powers visits \(d\) different residues before it closes.
The second concerns the order of a power. Let \(d = \operatorname{ord}_n(a)\) and let \(k \ge 1\). The congruence \((a^{k})^{m} \equiv 1\) holds exactly when \(d \mid km\), and dividing by \(g = \gcd(k, d)\) turns this into \((d/g) \mid (k/g)\,m\). Since \(d/g\) and \(k/g\) are coprime, Euclid’s lemma of Unit 2, which says that a number that divides a product and is coprime to one factor divides the other factor, gives \((d/g) \mid m\). The least such \(m\) is \(d/g\), which is the order of \(a^{k}\).
Modulo a prime \(p\) the possible orders are the divisors of \(p - 1\), and the question of this unit is which of them occur, and how often. The first example settles it for \(p = 11\) by testing every residue.