Lemma › Guides › Order modulo p in olympiad number theory
Guide

Order modulo p in olympiad number theory

Most olympiad number theory about primes comes down to one question: how many steps does it take for a,a2,a3,…a, a^2, a^3, \dots to come back to 11 modulo pp? That count is the order of aa, and a handful of facts about it let you say a lot about the prime factors of a number you cannot factor.

The definition and the one fact

Let pp be a prime and aa an integer with p∤ap \nmid a. The order of aa modulo pp, written ord⁡p(a)\operatorname{ord}_p(a), is the smallest k≥1k \ge 1 with ak≡1(modp)a^k \equiv 1 \pmod p. For example 22 modulo 77 goes 2,4,12, 4, 1, so the order is 33. Modulo 1111 it goes 2,4,8,5,10,9,7,3,6,12, 4, 8, 5, 10, 9, 7, 3, 6, 1, so the order is 1010. Modulo 1313 it is 1212.

The fact that carries almost every problem is this:

an≡1(modp)  ⟺  ord⁡p(a)∣n.a^n \equiv 1 \pmod p \iff \operatorname{ord}_p(a) \mid n.

So the order divides every exponent that works, and by Fermat's little theorem ap−1≡1a^{p-1} \equiv 1, so the order divides p−1p - 1. Two numbers come out of that line: a divisor of nn and a divisor of p−1p - 1. If you can show the order is a common divisor of both, and that the common divisors are few, you often know the order outright.

The proof of the fact

Divide nn by the order dd: n=qd+rn = qd + r with 0≤r<d0 \le r < d. Then an=(ad)qar≡ara^n = (a^d)^q a^r \equiv a^r. If an≡1a^n \equiv 1 then ar≡1a^r \equiv 1, and since r<dr < d and dd is the smallest positive exponent that works, r=0r = 0. The other direction is immediate. That is Euclid's algorithm again, and it is the same step that gives the gcd of 2m−12^m - 1 and 2n−12^n - 1. Two consequences are worth keeping. If am≡1a^m \equiv 1 and an≡1a^n \equiv 1, then agcd⁡(m,n)≡1a^{\gcd(m,n)} \equiv 1. And the order of a power is ord⁡(ak)=d/gcd⁡(d,k)\operatorname{ord}(a^k) = d / \gcd(d, k).

Primes that divide a^n - 1

Here is the move that makes the order useful. Let qq be a prime dividing an−1a^n - 1, where nn is a prime. Then ord⁡q(a)\operatorname{ord}_q(a) divides nn, so it is 11 or nn. If it is 11, then q∣a−1q \mid a - 1. Otherwise it is nn, and the order also divides q−1q - 1, so

q≡1(modn).q \equiv 1 \pmod n.

Take 211−1=20472^{11} - 1 = 2047. Any prime factor qq of it has order 1111 for 22, so q≡1(mod11)q \equiv 1 \pmod{11}. Also qq is odd, so 2∣q−12 \mid q - 1. Since 11∣q−111 \mid q - 1 as well and 22 and 1111 are coprime, 22∣q−122 \mid q - 1, so q≡1(mod22)q \equiv 1 \pmod{22}. The candidates are 23,67,89,…23, 67, 89, \dots. Trial division finds 2047=23⋅892047 = 23 \cdot 89. Both are 11 more than a multiple of 2222: 23=22+123 = 22 + 1 and 89=4⋅22+189 = 4 \cdot 22 + 1. You test a few candidates instead of every prime up to 4545.

A worked problem

Find all positive integers nn such that nn divides 2n−12^n - 1.

The answer is n=1n = 1 only. Suppose n>1n > 1. The number 2n−12^n - 1 is odd, so nn is odd, and the smallest prime factor qq of nn is at least 33. Since q∣n∣2n−1q \mid n \mid 2^n - 1, we have 2n≡1(modq)2^n \equiv 1 \pmod q, so ord⁡q(2)\operatorname{ord}_q(2) divides nn. It also divides q−1q - 1. Every prime factor of nn is at least qq, and every prime factor of q−1q - 1 is less than qq, so nn and q−1q - 1 share no prime factor. Their only common divisor is 11. So ord⁡q(2)=1\operatorname{ord}_q(2) = 1, which means q∣2−1=1q \mid 2 - 1 = 1. That is absurd.

The argument has a pattern you will use again. Take the smallest prime factor of the thing you want to show is impossible, and compare what nn says about the order with what q−1q - 1 says about it. A brute force up to 30003000 finds nothing past n=1n = 1, which agrees.

The size of the order, and primitive roots

How many numbers modulo pp have order exactly p−1p - 1? The answer is φ(p−1)\varphi(p - 1), where φ\varphi is Euler's totient. For p=13p = 13 that is φ(12)=4\varphi(12) = 4, and the four elements are 2,6,7,112, 6, 7, 11. Such an element is a primitive root, and one always exists. It means every nonzero residue is a power of it, which lets you turn a multiplicative problem modulo pp into an addition problem on exponents modulo p−1p - 1.

You usually cite that primitive roots exist, without proof. You do not need to know which element is one.

When to reach for it

Traps

The order depends on the modulus. Modulo 77, the order of 22 is 33, and modulo 99 it is 66. When the modulus is composite, the order divides φ(m)\varphi(m), not m−1m - 1, and the clean statement about q≡1(modn)q \equiv 1 \pmod n needs a prime modulus.

You also need aa to be coprime to the modulus. If q∣aq \mid a, no power of aa is ever 11, and "the order" does not exist.

The last trap is to stop at "the order divides nn" and forget the other half. You need both constraints, one from nn and one from p−1p - 1.

Where it sits

This is modular thinking with a measuring stick. You ask for the smallest exponent where ana^n becomes 11, and every other exponent that works is a multiple of it. The archive proves that if 2n−12^n - 1 is prime then nn is prime by a factorisation. The order gives a second view of the same numbers: the prime factors of 2p−12^p - 1 are all 11 more than a multiple of pp. For practice, pick any prime pp under thirty and write down the order of every residue modulo pp. Check that each one divides p−1p - 1. The problem archive has the number theory problems linked here.

Related guides

Techniques in this guide

Train it on Lemma

Every technique here is taught explicitly, in order. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.

Find your level