Orders and Primitive Roots

Study Sheet

Orders and Primitive Roots

How powers cycle, and quadratic residues

The Order of an Element

Concept
Order

For gcd⁡(a,m)=1\gcd(a, m) = 1, the order of aa mod mm is the least d>0d > 0 with ad≡1a^d \equiv 1. Key facts: an≡1a^n \equiv 1 iff d∣nd \mid n; hence d∣φ(m)d \mid \varphi(m). So to find the order, test only the divisors of φ(m)\varphi(m).

The order is the period of the sequence a,a2,a3,…a, a^2, a^3, \ldots mod mm: once ad≡1a^d \equiv 1 the sequence starts over, so the powers go around a cycle of length dd. Fermat and Euler only say the period divides p−1p - 1 or φ(m)\varphi(m); the order is the exact period. This is why "find the smallest nn with 2n≡1(modp)2^n \equiv 1 \pmod{p}" is not answered by Fermat alone, and why decimal expansions of 1/p1/p have period equal to the order of 1010 mod pp.

Example
Order of 22 mod 1313
1248361211951072, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1: all twelve
Each arrow multiplies by 2 mod 13; the cycle has length 12, the order of 2.

The order divides φ(13)=12\varphi(13) = 12, so the candidates are 1,2,3,4,6,121, 2, 3, 4, 6, 12. Compute: 22=42^2 = 4, 23=82^3 = 8, 24=16≡32^4 = 16 \equiv 3, 26=64≡12≡−12^6 = 64 \equiv 12 \equiv -1. None is 11, so the order is 1212: the powers of 22 visit every nonzero residue before returning to 11.

Example
Order of 33 mod 1313

Again the order divides 1212. 31=33^1 = 3, 32=93^2 = 9, 33=27≡13^3 = 27 \equiv 1. The order is 33: the powers of 33 cycle through only 3,9,13, 9, 1. Fermat's 312≡13^{12} \equiv 1 is true but hides the fact that 333^3 already is.

Example
Order of 22 mod 2525

φ(25)=20\varphi(25) = 20, so the order divides 2020: test 1,2,4,5,10,201, 2, 4, 5, 10, 20. 24=162^4 = 16, 25=32≡72^5 = 32 \equiv 7, 210=1024≡24≡−1(mod25)2^{10} = 1024 \equiv 24 \equiv -1 \pmod{25}. Since 210≡−12^{10} \equiv -1, the order does not divide 1010, and 220=(210)2≡12^{20} = (2^{10})^2 \equiv 1. The divisors of 2020 that do not divide 1010 are just 44 and 2020, and 24=16≠12^4 = 16 \ne 1, so the order is 2020.

Tip
Period of 1/p1/p

The decimal expansion of 1/p1/p (p≠2,5p \ne 2, 5) has period equal to the order of 1010 modulo pp. For p=7p = 7, the order of 1010 is 66: 1/7=0.142857‾1/7 = 0.\overline{142857}.

Side note
Where it goes wrong

Taking φ(m)\varphi(m) as the order. Fermat gives 312≡1(mod13)3^{12} \equiv 1 \pmod{13}, but the order of 33 is 33, not 1212. And testing exponents that are not divisors of φ(m)\varphi(m) wastes time: an order can only be a divisor.

Try it
Try it: order

Find the order of 33 modulo 77, and the period of the decimal expansion of 1/131/13.

Show the answer

31=3,32=2,33=6,36=36≡13^1 = 3, 3^2 = 2, 3^3 = 6, 3^6 = 36 \equiv 1 (and 31,32,33≠13^1, 3^2, 3^3 \ne 1): order 6\mathbf{6} (a primitive root). For 1/131/13: 102=100≡910^2 = 100 \equiv 9, 103≡90≡12≡−110^3 \equiv 90 \equiv 12 \equiv -1, so 106≡110^6 \equiv 1 and no smaller divisor of 1212 works: period 6\mathbf{6} (1/13=0.076923‾1/13 = 0.\overline{076923}).

Primitive Roots

Concept
A generator

A primitive root mod mm is an element of order exactly φ(m)\varphi(m). Every prime pp has one, and then every nonzero residue is a power gkg^k of it. If gg is a primitive root mod pp, then gkg^k is also one exactly when gcd⁡(k,p−1)=1\gcd(k, p - 1) = 1 — so there are φ(p−1)\varphi(p - 1) primitive roots.

A primitive root turns multiplication into addition: writing x=gkx = g^k, the exponent kk (the index or discrete logarithm) is defined mod p−1p - 1, and multiplying residues adds their indices. The order of gkg^k is (p−1)/gcd⁡(k,p−1)(p - 1)/\gcd(k, p - 1), because (gk)n≡1(g^k)^n \equiv 1 exactly when p−1∣knp - 1 \mid kn. That is where the count φ(p−1)\varphi(p - 1) comes from. Not every modulus has a primitive root — only 1,2,4,pe1, 2, 4, p^e and 2pe2p^e for odd primes pp do.

Example
Primitive roots mod 77

We need order 66. Powers of 33: 3,2,6,4,5,13, 2, 6, 4, 5, 1 — order 66, a primitive root. Powers of 55: 5,4,6,2,3,15, 4, 6, 2, 3, 1 — also order 66. The others fall short: 22 has order 33 (23=8≡12^3 = 8 \equiv 1), 44 has order 33, and 6≡−16 \equiv -1 has order 22. So the primitive roots are 33 and 55 — φ(6)=2\varphi(6) = 2 of them.

Example
A discrete logarithm

Solve 2k≡5(mod13)2^k \equiv 5 \pmod{13}. Since 22 is a primitive root mod 1313, some kk works; read it off the cycle 21,…,212≡2,4,8,3,6,12,11,9,5,10,7,12^1, \ldots, 2^{12} \equiv 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1. The value 55 is the ninth: k≡9(mod12)k \equiv 9 \pmod{12}. Check: 29=512=39⋅13+52^9 = 512 = 39\cdot13 + 5. ✓

Example
All primitive roots mod 1313
124836121195107placed in the order 1, 2, 4, 8, … (powers of 2)
Going round the circle is multiplying by 2; the shaded positions k = 1, 5, 7, 11 are the primitive roots.

With g=2g = 2, the primitive roots are 2k2^k for kk coprime to 1212: k=1,5,7,11k = 1, 5, 7, 11. From the cycle, 21=22^1 = 2, 25≡62^5 \equiv 6, 27≡112^7 \equiv 11, 211≡72^{11} \equiv 7. So the primitive roots mod 1313 are 2,6,7,112, 6, 7, 11 — four of them, and φ(12)=4\varphi(12) = 4.

Side note
Where it goes wrong

Assuming every modulus has a primitive root. Mod 88 the units are 1,3,5,71, 3, 5, 7 and 32=93^2 = 9, 52=255^2 = 25, 72=497^2 = 49 are all ≡1\equiv 1: every element has order at most 22, though φ(8)=4\varphi(8) = 4. Nothing generates the group.

Try it
Try it: primitive roots mod 1111

Find all primitive roots modulo 1111.

Show the answer

Try 22: 22=42^2 = 4, 25=32≡−12^5 = 32 \equiv -1, so neither 222^2 nor 252^5 is 11, and the order (a divisor of 1010) must be 1010. The primitive roots are 2k2^k with gcd⁡(k,10)=1\gcd(k, 10) = 1: 21=22^1 = 2, 23=82^3 = 8, 27=128≡72^7 = 128 \equiv 7, 29=512≡62^9 = 512 \equiv 6. So 2,6,7,8\mathbf{2, 6, 7, 8} — φ(10)=4\varphi(10) = 4 of them.

Quadratic Residues

Concept
Squares mod pp

For an odd prime pp, exactly half of the nonzero residues are squares (quadratic residues). Euler's criterion: aa is a residue iff a(p−1)/2≡1a^{(p-1)/2} \equiv 1; a non-residue gives −1-1. In particular −1-1 is a square mod pp iff p≡1(mod4)p \equiv 1 \pmod 4.

Half the residues are squares because xx and −x-x have the same square and no others do (from x2≡y2x^2 \equiv y^2, p∣(x−y)(x+y)p \mid (x-y)(x+y)). The criterion is Fermat cut in half: ap−1=(a(p−1)/2)2≡1a^{p-1} = (a^{(p-1)/2})^2 \equiv 1, so a(p−1)/2≡±1a^{(p-1)/2} \equiv \pm1, and it is +1+1 exactly for the squares. The statement about −1-1 is what makes x2+1x^2 + 1 factor mod 5,13,17,…5, 13, 17, \ldots and never mod 3,7,11,…3, 7, 11, \ldots — and behind it sits quadratic reciprocity.

Example
Is 22 a square mod 77?

Euler's criterion: 2(7−1)/2=23=8≡12^{(7-1)/2} = 2^3 = 8 \equiv 1, so yes. Indeed 32=9≡23^2 = 9 \equiv 2 and 42=16≡24^2 = 16 \equiv 2 — two square roots, 33 and −3≡4-3 \equiv 4, as the pairing predicts.

Example
Is 33 a square mod 1313?
112233445566778899101011111212xx²x and 13 − x share a square: six squares, each hit twice
Squaring mod 13 folds the twelve residues onto six, each hit by x and −x.

3(13−1)/2=36=729=56⋅13+1≡13^{(13-1)/2} = 3^6 = 729 = 56\cdot13 + 1 \equiv 1: yes. To find a root, square 1,…,61, \ldots, 6 (the other half are their negatives): 1,4,9,16≡3,…1, 4, 9, 16 \equiv 3, \ldots — so 42≡34^2 \equiv 3 and also 92≡39^2 \equiv 3. The squares mod 1313 are 1,3,4,9,10,121, 3, 4, 9, 10, 12: six of the twelve.

Example
−1-1 mod 1313

Since 13≡1(mod4)13 \equiv 1 \pmod 4, −1≡12-1 \equiv 12 should be a square, and the table shows 52=25≡125^2 = 25 \equiv 12 and 82=64≡128^2 = 64 \equiv 12. Consequence: every odd prime dividing a number of the form n2+1n^2 + 1 is ≡1(mod4)\equiv 1 \pmod 4, since n2≡−1n^2 \equiv -1 modulo that prime. For example 82+1=65=5⋅138^2 + 1 = 65 = 5\cdot13.

Side note
Where it goes wrong

Concluding x2≡ax^2 \equiv a has a solution because aa looks like a square, or has none because it does not. 44 is a square mod every pp, but 22 is a square mod 77 and not mod 55 (the squares mod 55 are 1,41, 4). Being a residue depends on pp.

Try it
Try it: residues

List the quadratic residues mod 1111, and decide whether x2≡−1(mod11)x^2 \equiv -1 \pmod{11} has a solution.

Show the answer

Squares of 1,…,51, \ldots, 5: 1,4,9,16≡5,25≡31, 4, 9, 16 \equiv 5, 25 \equiv 3 (and 6,…,106, \ldots, 10 repeat them). Residues: {1,3,4,5,9}\mathbf{\{1, 3, 4, 5, 9\}}. −1≡10-1 \equiv 10 is not among them, as expected since 11≡3(mod4)11 \equiv 3 \pmod 4: no solution.

Why It Works

Let dd be the order of aa and suppose an≡1a^n \equiv 1. Divide: n=dq+rn = dq + r with 0≤r<d0 \le r < d. Then 1≡an=(ad)qar≡ar1 \equiv a^n = (a^d)^qa^r \equiv a^r. If r>0r > 0 this contradicts the minimality of dd; so r=0r = 0 and d∣nd \mid n. Apply it to n=φ(m)n = \varphi(m) (Euler) and d∣φ(m)d \mid \varphi(m) follows. The division algorithm, once more, is the whole proof.