Mathematical Olympiad Preparation
Number theory is one of the four areas of every mathematical olympiad, and the one where knowing the right theorem shortens a problem the most. Here is how the masterclass supplies the theory, and how to train the rest.
The olympiad path
The International Mathematical Olympiad (IMO) has been held every year since 1959 and now brings together teams of six from more than a hundred countries. Its problems come from four areas: algebra, combinatorics, geometry, and number theory. Each contestant sits two papers of three problems, four and a half hours each, and every problem asks for a proof, marked out of seven. Countries select their teams through national olympiads, usually over several rounds, so the way to the IMO leads through the olympiad of your own country. The European Girls' Mathematical Olympiad (EGMO), held since 2012 with the same format and teams of four, is reached the same way, and many countries outside Europe send guest teams.
University students have their own competitions. The William Lowell Putnam Mathematical Competition, held on the first Saturday of December since 1938, sets twelve problems in two sessions of three hours for undergraduates in the United States and Canada; the problems and solutions since 1985 are collected in Kiran Kedlaya's archive. The International Mathematics Competition for University Students (IMC) has been held every summer since 1994 and takes individual entrants from universities worldwide. Number theory appears in both.
An olympiad problem in number theory does not ask you to state a theorem; it assumes you know a dozen of them cold and asks you to see which one applies to a situation you have never met. The masterclass supplies the theorems, with their proofs and the hypotheses that a marking scheme checks. The seeing comes from problems, and the second half of this page is about how to add them.
Which units cover which topics
The number theory problems of the IMO, the EGMO, and the national olympiads draw on the areas in the table. Nothing in them needs calculus or analytic methods.
| Syllabus area | What it includes | Units |
|---|---|---|
| Divisibility, gcd, and Bézout's identity | Division with remainder, the Euclidean algorithm, Bézout's identity, Euclid's lemma, linear Diophantine equations | Unit 2, Unit 3 |
| Primes and factorization | The fundamental theorem of arithmetic, the exponent of a prime in n and in n!, Legendre's formula, the sieve | Unit 3 |
| Congruences | Arithmetic modulo n, inverses, linear congruences, the Chinese remainder theorem | Unit 4 |
| Fermat, Euler, and Wilson | Fermat's little theorem, Euler's theorem and the totient, Wilson's theorem, the order of an element | Unit 5 |
| Arithmetic functions | The number and sum of divisors, multiplicative functions, Möbius inversion | Unit 6 |
| Diophantine equations | Pythagorean triples, Fermat's descent (Vieta jumping in its olympiad form), Pell's equation | Unit 7 |
| Orders and primitive roots | Orders modulo a prime, primitive roots, discrete logarithms, the lifting-the-exponent lemma | Unit 9 |
| Quadratic residues | The Legendre symbol, Euler's criterion, the law of quadratic reciprocity, when minus one is a square | Unit 10 |
| Sums of squares | Thue's lemma, Fermat's two-square theorem, Lagrange's four-square theorem, quadratic forms | Unit 11 |
Units 1 to 8 (the Foundation masterclass) cover what the first rounds of a national olympiad ask: divisibility, primes, congruences, Fermat's and Euler's theorems, and Diophantine equations, with Unit 1 teaching what a proof is and how induction, contradiction, and descent are written down. Units 9 to 11 (in the Advanced masterclass) add orders and primitive roots, quadratic residues with the law of reciprocity, and sums of squares, which the later rounds and the IMO itself use. The lifting-the-exponent lemma, a classic olympiad tool for the exponent of a prime in an − bn, is named in Unit 9 and is best learned from a problem collection, where it comes with twenty problems. Units 12 to 16, on the distribution of the primes, the zeta function, Dirichlet's theorem, sieves, and prime gaps, lie outside the olympiad syllabus; they show where the subject goes after it. Every unit shows its computations step by step, and the Key Theorems and Formulas page collects the statements you need to know by heart.
Three IMO problems and the units behind them
The statements below are those of the official problem sheets. No solutions are given here: the point is to see which theorem of which unit the problem rests on, and then to sit down with it.
IMO 1988, Problem 6
Let a and b be positive integers such that ab + 1 divides a2 + b2. Show that (a2 + b2)/(ab + 1) is the square of an integer.
What it needs. Fermat's method of infinite descent: assume a solution that is not a square, build a smaller one, and continue until the well-ordering principle objects. In olympiad circles this form of descent, applied to a quadratic equation whose second root is read off from the coefficients, is called Vieta jumping. See Unit 7.
IMO 2005, Problem 4
Determine all positive integers relatively prime to all the terms of the infinite sequence an = 2n + 3n + 6n − 1, n ≥ 1.
What it needs. Fermat's little theorem, applied to each prime p in turn: it tells you what 2p−2, 3p−2, and 6p−2 are modulo p, and the primes 2 and 3 are checked by hand. See Unit 5.
IMO 2008, Problem 3
Prove that there exist infinitely many positive integers n such that n2 + 1 has a prime divisor which is greater than 2n + √(2n).
What it needs. The fact that −1 is a square modulo every prime p of the form 4k + 1 (Euler's criterion), together with the freedom to choose the square root of −1 close to p/2, which is the trick behind Thue's lemma. See Unit 10 and Unit 11.
Problem 6 of 1988 is famous for having been given to the IMO by the problem committee after four number theorists had failed to solve it in the six hours they were allowed; eleven contestants solved it in full. The lesson for a student is the opposite of discouraging: the theorem it needs is in Unit 7, and the difficulty lies entirely in seeing that it applies.
What to add to the masterclass
The masterclass teaches the theory and checks it with quizzes. It is not a problem-solving program. To do well at an olympiad, add these:
- Past problems. The official IMO problem archive has every paper since 1959, the EGMO archive every paper since 2012, and the olympiad of your own country publishes its past rounds; the contest collection of the Art of Problem Solving community gathers all of them with discussed solutions. Work on a problem without looking at the solution, for an hour at least. Check your result, then read the official solution even when yours was right, because the official one is usually shorter and shows what the problem committee had in mind.
- Written proofs. Write every solution out in full, as you would hand it in, and have someone read it: a teacher, a club leader, or a fellow student. Most lost marks at an olympiad are for a step the solver saw and did not write, or for a hypothesis (p odd, gcd(a, n) = 1) that was needed and not checked.
- Speed. Once an area is familiar, time yourself: three problems in four and a half hours leaves ninety minutes for each, and the first fifteen of those are for trying the small cases by hand. Number theory problems reward the student who computes n = 1, 2, 3, 4, 5 before thinking.
- Problem books. Two classics without which no olympiad shelf is complete: Arthur Engel's Problem-Solving Strategies, whose number theory chapter is a syllabus in itself, and 104 Number Theory Problems by Titu Andreescu, Dorin Andrica, and Zuming Feng, which goes from the division algorithm to the lifting-the-exponent lemma with full solutions.
- The theorems, cold. Before a contest, read the Key Theorems and Formulas page once more and say each statement with its hypothesis without looking.
A study plan
Follow the masterclass at one unit a week. In the same week, solve five to ten past problems on the area of that unit, starting with the first rounds of a national olympiad and moving to IMO shortlist problems only when those feel comfortable. After Unit 8 you have the theory for the first rounds; after Unit 11 you have the theory for everything the IMO asks in number theory. In the last weeks before your contest, take full past papers under exam conditions, all four areas, and have the written solutions read. Our blog article How to prepare for the number theory problems of the IMO goes into more detail, and the topic page Olympiads and competitions lists further articles.
For teachers
A school mathematics club can use the Foundation masterclass as its theory track: the students read the unit of the week at home and take its quiz, and the club meeting is spent on problems from the area of that unit, with the teacher or an older student reading the written solutions. One unit a week for eight weeks covers the number theory of the first rounds, and the certificate at the end gives the students something to show for it. Our page For Schools and Teachers describes how the program works with a group and how to look at the material before you recommend it.