Orders and primitive roots

Euler's theorem says that \(a^{\varphi(n)} \equiv 1 \pmod n\), but the powers of \(a\) often return to 1 sooner. Modulo 13, the powers of 3 are \(3, 9, 1\), back to 1 after three steps, while the powers of 2 run through all twelve nonzero residues before returning. This lesson studies the first return time, the order, and the residues like 2 modulo 13 whose powers reach everything, the primitive roots. Gauss proved that every prime has primitive roots. The theory explains the repeating decimals of fractions, gives logarithms for modular arithmetic, and supplies the setting for the Diffie–Hellman key exchange of lesson 12.

The order of an element

Definition. Let \(\gcd(a, n) = 1\). The order of \(a\) modulo \(n\), written \(\operatorname{ord}_n(a)\), is the least positive integer \(k\) with \(a^k \equiv 1 \pmod n\).

The order exists, since Euler's theorem provides one exponent that works, \(\varphi(n)\). Modulo 13: \(\operatorname{ord}(1) = 1\), \(\operatorname{ord}(12) = 2\) since \(12 \equiv -1\), \(\operatorname{ord}(3) = 3\), \(\operatorname{ord}(5) = 4\) since \(5^2 = 25 \equiv -1\), and \(\operatorname{ord}(2) = 12\).

Theorem. Let \(k = \operatorname{ord}_n(a)\). Then \(a^m \equiv 1 \pmod n\) if and only if \(k \mid m\). In particular \(k \mid \varphi(n)\). More generally \(a^i \equiv a^j\) if and only if \(i \equiv j \pmod k\).

Proof. Divide: \(m = qk + r\) with \(0 \le r < k\). Then \(a^m = (a^k)^qa^r \equiv a^r\). If \(a^m \equiv 1\), then \(a^r \equiv 1\) with \(r < k\), so by minimality \(r = 0\). Conversely, if \(k \mid m\) then \(a^m = (a^k)^{m/k} \equiv 1\). The statement about \(a^i \equiv a^j\) follows by multiplying by an inverse of \(a^j\).

So the powers of \(a\) cycle with period exactly \(k\): \(1, a, a^2, \ldots, a^{k-1}\) are distinct, and then the pattern repeats. Since the order divides \(\varphi(n)\), to find it we only need to test the divisors of \(\varphi(n)\). Modulo 13 the possible orders are 1, 2, 3, 4, 6 and 12.

Theorem. If \(\operatorname{ord}_n(a) = k\), then \(\operatorname{ord}_n(a^j) = \dfrac{k}{\gcd(j, k)}\). Proof: \((a^j)^m \equiv 1\) iff \(k \mid jm\) iff \(\frac{k}{\gcd(j, k)} \mid m\), since \(k/\gcd(j, k)\) and \(j/\gcd(j, k)\) are coprime. For example, modulo 13, \(\operatorname{ord}(2^4) = 12/\gcd(4, 12) = 3\), and indeed \(2^4 = 16 \equiv 3\), which we saw has order 3.

Primitive roots

Definition. An integer \(g\) is a primitive root modulo \(n\) if \(\operatorname{ord}_n(g) = \varphi(n)\). Equivalently, the powers \(g, g^2, \ldots, g^{\varphi(n)}\) run through a reduced residue system modulo \(n\).

The figure is the complete table of powers modulo 13. Each row is periodic, with the 1s marking the multiples of the order. Rows 2, 6, 7 and 11 contain every nonzero residue exactly once in their first twelve entries; these are the primitive roots. Counting the orders in the right-hand column, there is one element of order 1, one of order 2, two of order 3, two of order 4, two of order 6 and four of order 12. Those counts are \(\varphi(1), \varphi(2), \varphi(3), \varphi(4), \varphi(6), \varphi(12)\), and they add up to 12, which is Gauss's identity from lesson 7. That is no coincidence, and it is the key to the existence proof.

Not every modulus has primitive roots. Modulo 8, the units 1, 3, 5, 7 all satisfy \(a^2 \equiv 1\), so no element has order \(\varphi(8) = 4\). Modulo 15, \(\varphi(15) = 8\) but every unit satisfies \(a^4 \equiv 1\), because \(a^4 \equiv 1\) modulo both 3 and 5 by Fermat.

Lagrange's theorem on polynomial congruences

Theorem (Lagrange, 1768). Let \(p\) be prime and \(f(x) = a_dx^d + \cdots + a_0\) a polynomial with integer coefficients and \(p \nmid a_d\). Then the congruence \(f(x) \equiv 0 \pmod p\) has at most \(d\) solutions modulo \(p\).

Proof. Induct on \(d\). For \(d = 0\) there are no solutions, since \(p \nmid a_0\). Suppose the result holds for degree \(d - 1\), and let \(r\) be a solution of \(f(x) \equiv 0\) (if there is none we are done). Dividing \(f(x)\) by \(x - r\) gives \(f(x) = (x - r)g(x) + f(r)\) with \(g\) of degree \(d - 1\) and the same leading coefficient. If \(s\) is another solution, \(0 \equiv (s - r)g(s) \pmod p\), and since \(p\) is prime and \(s \not\equiv r\), \(g(s) \equiv 0\). By induction \(g\) has at most \(d - 1\) roots, so \(f\) has at most \(d\).

The primality of the modulus is essential: \(x^2 \equiv 1 \pmod 8\) has four solutions, 1, 3, 5, 7. The theorem says that \(\mathbb{Z}_p\) behaves like a field, in which a polynomial of degree \(d\) has at most \(d\) roots.

Corollary. If \(d \mid p - 1\), then \(x^d \equiv 1 \pmod p\) has exactly \(d\) solutions. Proof: write \(p - 1 = de\). Then \(x^{p-1} - 1 = (x^d - 1)(x^{d(e-1)} + \cdots + x^d + 1)\). The left side has exactly \(p - 1\) roots by Fermat. The second factor has at most \(p - 1 - d\) roots by Lagrange, so \(x^d - 1\) has at least \(d\), and by Lagrange at most \(d\).

Every prime has a primitive root

Theorem (Gauss). If \(p\) is prime and \(d \mid p - 1\), there are exactly \(\varphi(d)\) residues of order \(d\) modulo \(p\). In particular there are \(\varphi(p - 1)\) primitive roots modulo \(p\), at least one.

Proof. Let \(\psi(d)\) be the number of residues of order \(d\). We claim \(\psi(d) \le \varphi(d)\). If \(\psi(d) = 0\) this is clear. Otherwise let \(a\) have order \(d\). Then \(1, a, \ldots, a^{d-1}\) are \(d\) distinct solutions of \(x^d \equiv 1\), so by Lagrange they are all the solutions. Every element of order \(d\) is among them, and \(a^j\) has order \(d/\gcd(j, d)\), which equals \(d\) exactly when \(\gcd(j, d) = 1\). So \(\psi(d) = \varphi(d)\) in this case. Now every unit has some order dividing \(p - 1\), so \(\sum_{d \mid p-1}\psi(d) = p - 1 = \sum_{d \mid p-1}\varphi(d)\) by Gauss's identity. Since each term \(\psi(d) \le \varphi(d)\) and the sums agree, \(\psi(d) = \varphi(d)\) for every \(d\). Taking \(d = p - 1\) finishes the proof.

In group language, the multiplicative group of \(\mathbb{Z}_p\) is cyclic, and the same proof shows the multiplicative group of every finite field is cyclic, as MATH-323 explains. The proof is not constructive: it shows primitive roots exist without saying where. In practice one tests small candidates, using the following criterion.

Test. \(g\) is a primitive root modulo \(p\) if and only if \(g^{(p-1)/q} \not\equiv 1 \pmod p\) for every prime \(q\) dividing \(p - 1\). Proof: if \(g\) had order \(k < p - 1\), then \(k\) would be a proper divisor of \(p - 1\), so \(k \mid (p - 1)/q\) for some prime \(q\), and \(g^{(p-1)/q} \equiv 1\). For \(p = 13\), \(p - 1 = 12 = 2^2 \cdot 3\), and \(g = 2\) passes: \(2^6 = 64 \equiv 12\) and \(2^4 = 16 \equiv 3\), neither 1. For \(p = 41\), \(40 = 2^3 \cdot 5\), and 2 fails since \(2^{20} \equiv 1\) (we saw \(2^{10} \equiv -1\)), but 6 works.

The least primitive root is usually small; it is 2 for roughly three primes in every eight. Artin conjectured in 1927 that 2 is a primitive root for infinitely many primes, indeed for a positive proportion of them, about 0.374. The conjecture is still unproved, although Heath-Brown showed in 1986 that at least one of 2, 3, 5 has this property.

Which moduli have primitive roots? Gauss settled this too: exactly \(n = 1, 2, 4, p^k\) and \(2p^k\) for odd primes \(p\). The argument for \(n = 8\) above extends to all higher powers of 2, and a modulus with two different odd prime factors fails as 15 does: if \(n = ab\) with coprime \(a, b > 2\), then \(\varphi(a)\) and \(\varphi(b)\) are both even, and \(x^{\varphi(n)/2} \equiv 1\) modulo both \(a\) and \(b\) for every unit \(x\).

Indices: logarithms modulo p

If \(g\) is a primitive root modulo \(p\), every unit \(a\) is \(g^k\) for a unique \(k\) modulo \(p - 1\). This \(k\) is the index or discrete logarithm of \(a\), written \(\operatorname{ind}_g(a)\). Like ordinary logarithms it turns multiplication into addition, \[\operatorname{ind}(ab) \equiv \operatorname{ind}(a) + \operatorname{ind}(b), \qquad \operatorname{ind}(a^m) \equiv m\operatorname{ind}(a) \pmod{p - 1}.\] Jacobi published a table of indices for all primes below 1000 in 1839, used much as tables of logarithms were.

Indices solve power congruences. To solve \(x^3 \equiv 5 \pmod{13}\) with \(g = 2\): the powers of 2 are \(2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1\), so \(\operatorname{ind}(5) = 9\). Writing \(x = 2^y\), the congruence becomes \(3y \equiv 9 \pmod{12}\), which has the three solutions \(y \equiv 3, 7, 11 \pmod{12}\), giving \(x \equiv 8, 11, 7\). Check: \(8^3 = 512 = 39 \cdot 13 + 5\). In general \(x^k \equiv a \pmod p\) is solvable iff \(\gcd(k, p - 1) \mid \operatorname{ind}(a)\), equivalently iff \(a^{(p-1)/\gcd(k, p-1)} \equiv 1\).

Computing \(g^k \bmod p\) is fast, by square-and-multiply. Computing the index \(k\) from \(g^k\), the discrete logarithm problem, appears to be very hard when \(p\) is large and chosen carefully. The best known methods for a 2048-bit prime would take far longer than the age of the universe on current computers. This one-way property is the basis of the Diffie–Hellman key exchange and of digital signature schemes.

Repeating decimals

Orders explain the periods of repeating decimals. If \(p\) is a prime other than 2 and 5, the decimal expansion of \(1/p\) is purely periodic, and its period length is \(\operatorname{ord}_p(10)\). Reason: if \(10^k \equiv 1 \pmod p\), then \(10^k - 1 = pm\) and \(\frac{1}{p} = \frac{m}{10^k - 1} = m(10^{-k} + 10^{-2k} + \cdots)\), so the \(k\)-digit block \(m\) repeats; and a repeating block of length \(k\) forces \(p \mid 10^k - 1\). So \(1/7 = 0.\overline{142857}\) has period 6 because 10 is a primitive root modulo 7, while \(1/13 = 0.\overline{076923}\) has period 6 because \(\operatorname{ord}_{13}(10) = 6\). Primes like 7, 17, 19 and 23, for which the period is the maximum \(p - 1\), are called full reptend primes, and the digits of \(2/7, 3/7, \ldots\) are cyclic shifts of 142857. Whether there are infinitely many full reptend primes is a case of Artin's conjecture.

Orders and primitive roots by computer

The program computes orders, finds all primitive roots modulo 13 and the least primitive root of each prime below 100, checks Gauss's count of elements of each order, builds an index table, solves \(x^3 \equiv 5 \pmod{13}\), and compares decimal periods with orders of 10.

import math

def order(a, n):
    k, x = 1, a % n
    while x != 1:
        x, k = x * a % n, k + 1
    return k

def prime_factors(n):
    f, d = set(), 2
    while d * d <= n:
        while n % d == 0:
            f.add(d); n //= d
        d += 1
    if n > 1:
        f.add(n)
    return f

def is_primitive_root(g, p):
    return all(pow(g, (p - 1) // q, p) != 1 for q in prime_factors(p - 1))

p = 13
print("orders mod 13:", {a: order(a, p) for a in range(1, p)})
print("primitive roots mod 13:", [g for g in range(1, p) if is_primitive_root(g, p)])
counts = {}
for a in range(1, p):
    counts[order(a, p)] = counts.get(order(a, p), 0) + 1
print("number of elements of each order:", dict(sorted(counts.items())))

primes = [q for q in range(3, 100) if all(q % d for d in range(2, math.isqrt(q) + 1))]
print("least primitive root:", {q: next(g for g in range(2, q) if is_primitive_root(g, q)) for q in primes})

g, ind = 2, {}
for k in range(12):
    ind[pow(g, k, p)] = k
print("index table base 2 mod 13:", dict(sorted(ind.items())))
print("solutions of x^3 = 5 mod 13:", [x for x in range(13) if pow(x, 3, 13) == 5])

def period(q):
    r, seen, k = 1, {}, 0
    while r not in seen:
        seen[r] = k; r = r * 10 % q; k += 1
    return k - seen[r]

for q in [7, 13, 17, 31, 41, 97]:
    print(f"1/{q}: decimal period {period(q)}, ord_{q}(10) = {order(10, q)}")
print("full reptend primes below 100:", [q for q in primes if q != 5 and order(10, q) == q - 1])

orders mod 13: {1: 1, 2: 12, 3: 3, 4: 6, 5: 4, 6: 12, 7: 12, 8: 4, 9: 3, 10: 6, 11: 12, 12: 2}
primitive roots mod 13: [2, 6, 7, 11]
number of elements of each order: {1: 1, 2: 1, 3: 2, 4: 2, 6: 2, 12: 4}
least primitive root: {3: 2, 5: 2, 7: 3, 11: 2, 13: 2, 17: 3, 19: 2, 23: 5, 29: 2, 31: 3, 37: 2, 41: 6, 43: 3, 47: 5, 53: 2, 59: 2, 61: 2, 67: 2, 71: 7, 73: 5, 79: 3, 83: 2, 89: 3, 97: 5}
index table base 2 mod 13: {1: 0, 2: 1, 3: 4, 4: 2, 5: 9, 6: 5, 7: 11, 8: 3, 9: 8, 10: 10, 11: 7, 12: 6}
solutions of x^3 = 5 mod 13: [7, 8, 11]
1/7: decimal period 6, ord_7(10) = 6
1/13: decimal period 6, ord_13(10) = 6
1/17: decimal period 16, ord_17(10) = 16
1/31: decimal period 15, ord_31(10) = 15
1/41: decimal period 5, ord_41(10) = 5
1/97: decimal period 96, ord_97(10) = 96
full reptend primes below 100: [7, 17, 19, 23, 29, 47, 59, 61, 97]

The counts of elements of each order modulo 13 match \(\varphi(d)\) for each divisor \(d\) of 12. The least primitive root is 2 for many primes, but 7 needs 3 and 41 needs 6. The decimal period of \(1/q\) equals \(\operatorname{ord}_q(10)\) in every case: \(1/41 = 0.\overline{02439}\) repeats after only five digits.