Most olympiad number theory about primes comes down to one question: how many steps does it take for to come back to modulo ? That count is the order of , 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 be a prime and an integer with . The order of modulo , written , is the smallest with . For example modulo goes , so the order is . Modulo it goes , so the order is . Modulo it is .
The fact that carries almost every problem is this:
So the order divides every exponent that works, and by Fermat's little theorem , so the order divides . Two numbers come out of that line: a divisor of and a divisor of . 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 by the order : with . Then . If then , and since and is the smallest positive exponent that works, . The other direction is immediate. That is Euclid's algorithm again, and it is the same step that gives the gcd of and . Two consequences are worth keeping. If and , then . And the order of a power is .
Primes that divide a^n - 1
Here is the move that makes the order useful. Let be a prime dividing , where is a prime. Then divides , so it is or . If it is , then . Otherwise it is , and the order also divides , so
Take . Any prime factor of it has order for , so . Also is odd, so . Since as well and and are coprime, , so . The candidates are . Trial division finds . Both are more than a multiple of : and . You test a few candidates instead of every prime up to .
A worked problem
Find all positive integers such that divides .
The answer is only. Suppose . The number is odd, so is odd, and the smallest prime factor of is at least . Since , we have , so divides . It also divides . Every prime factor of is at least , and every prime factor of is less than , so and share no prime factor. Their only common divisor is . So , which means . 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 says about the order with what says about it. A brute force up to finds nothing past , which agrees.
The size of the order, and primitive roots
How many numbers modulo have order exactly ? The answer is , where is Euler's totient. For that is , and the four elements are . 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 into an addition problem on exponents modulo .
You usually cite that primitive roots exist, without proof. You do not need to know which element is one.
When to reach for it
- Prime factors of such numbers. For a number like : "Show that every prime factor of ... is of the form ." That is the order argument, word for word.
- A number that divides a power of itself plus or minus one. For or , take the smallest prime factor of , as above.
- Which primes divide a power minus one. For , the answer is the primes where the order of divides , and the order divides .
- A congruence with a variable exponent, such as . The solutions are the multiples of the order.
Traps
The order depends on the modulus. Modulo , the order of is , and modulo it is . When the modulus is composite, the order divides , not , and the clean statement about needs a prime modulus.
You also need to be coprime to the modulus. If , no power of is ever , and "the order" does not exist.
The last trap is to stop at "the order divides " and forget the other half. You need both constraints, one from and one from .
Where it sits
This is modular thinking with a measuring stick. You ask for the smallest exponent where becomes , and every other exponent that works is a multiple of it. The archive proves that if is prime then is prime by a factorisation. The order gives a second view of the same numbers: the prime factors of are all more than a multiple of . For practice, pick any prime under thirty and write down the order of every residue modulo . Check that each one divides . The problem archive has the number theory problems linked here.
Related guides
- Zsigmondy's theorem: statement, exceptions and examplesZsigmondy's theorem says a^n - b^n has a prime factor no earlier a^k - b^k has, with two exceptions. The statement, the traps, and a worked problem.
- Lifting the exponent lemma explained for competitionsThe lifting the exponent lemma in one line, the p = 2 version that catches almost everyone, and the signals that tell you a contest problem wants it.
- gcd(2^m − 1, 2^n − 1): the proof, and how to spot itWhy gcd(2^m − 1, 2^n − 1) = 2^gcd(m,n) − 1: run Euclid's algorithm on the exponents. A full proof, a second proof by orders, and where it turns up.
- Chinese remainder theorem in olympiad problemsThe Chinese remainder theorem for coprime moduli, how to solve a system by hand, what changes when moduli share a factor, and where olympiads use it.
- Legendre's formula for the power of a prime in n!Legendre's formula gives the exponent of a prime in n! as a sum of floors. The proof, the digit-sum form, trailing zeros, and the traps that cost marks.
Techniques in this guide
- Modular ThinkingWhen the numbers are too big, shrink the universe.
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