How to prepare for the number theory problems of the IMO Image: Mathematical Gymnasium Belgrade (public domain)

How to prepare for the number theory problems of the IMO

The International Mathematical Olympiad has been held every year since 1959, except 1980, and now gathers teams of six students from more than a hundred countries. The format has not changed for decades: two days, three problems each, four and a half hours per day, seven points per problem. The problems come from four areas, algebra, combinatorics, geometry, and number theory, and most papers contain one or two problems in which the integers are the subject. A student who reaches the national olympiad will meet number theory problems at every stage, and the theory they assume is small, definite, and learnable.

What an olympiad problem looks like

It is a proof. There is no multiple choice and no numerical answer to look up; the student writes an argument and a coordinator reads it. Problem 6 of the 1988 IMO is the famous example: if a and b are positive integers such that ab + 1 divides a² + b², show that (a² + b²)/(ab + 1) is a perfect square. Every tool needed is in a first course, and the solution, a descent argument now called Vieta jumping, is two pages long. Problem 4 of the 2005 IMO asks to show that the only positive integer coprime to every number of the form 2ⁿ + 3ⁿ + 6ⁿ - 1 is 1, and the solution is a few lines once you think of Fermat's little theorem. The statements are at imo-official.org, with the results of every contestant since 1959.

The theory the problems assume is not the hard part. The hard part is seeing which theorem a problem is hiding, and that comes from having the theorems ready and from having solved a few hundred problems. This guide is about the first of those; nothing replaces the second.

The syllabus, area by area

The olympiad does not publish a syllabus, but the problems of the last forty years define one, and it maps onto the Foundation and Advanced units of the masterclass almost exactly.

Divisibility and the greatest common divisor: the division theorem, Euclid's algorithm, Bézout's identity, and the lemma that if d divides ab and is coprime to a then d divides b. Also the linear Diophantine equation ax + by = c. These are Unit 2, and they appear in some form in nearly every number theory problem.

Primes and factorization: the fundamental theorem of arithmetic, the exponent v_p(n) of a prime in n, Legendre's formula for v_p(n!), and the bound that a composite number has a prime factor at most its square root. Unit 3. The exponent v_p is the single most useful notation in olympiad number theory, because most "divisibility" problems are statements about exponents.

Congruences: the arithmetic of residues, inverses, the Chinese remainder theorem, and the habit of reducing an equation modulo a well-chosen number to show it has no solutions. Unit 4. Problems that look like Diophantine equations are often killed by one congruence; x² + y² = 3z² has no non-trivial solutions because squares are 0 or 1 modulo 3.

Fermat, Euler, and Wilson: a^(p-1) ≡ 1 (mod p), a^φ(n) ≡ 1 (mod n), and (p - 1)! ≡ -1 (mod p), with the notion of the order of a modulo n. Unit 5. The order is where many problems live: if a^k ≡ 1 (mod p), then the order of a divides k, and that divisibility is often the whole problem.

Arithmetic functions: d(n), σ(n), and φ(n) with their product formulas, and the multiplicativity that makes them computable. Unit 6.

Diophantine equations: Pythagorean triples, the descent method, Pell's equation, and congruence obstructions. Unit 7. Vieta jumping is a form of descent and belongs here.

Orders and primitive roots: the existence of a primitive root modulo a prime, the structure of the invertible residues, and the lifting-the-exponent lemma, which gives v_p(aⁿ - bⁿ) in terms of v_p(a - b) and v_p(n). The lemma is a classic olympiad tool that textbooks rarely state; Unit 9 covers the theory it rests on, and the lemma itself should be learnt from a problem collection with its proof.

Quadratic residues: Euler's criterion, the two supplements, and the law of quadratic reciprocity, mostly in the form "which primes divide n² + 1, n² + 2, n² - 2". Unit 10. Problem 3 of the 2008 IMO, which asks for infinitely many n such that n² + 1 has a prime factor greater than 2n + √(2n), is a quadratic residue problem: -1 is a square modulo the primes of the form 4k + 1, and that is the entrance.

Sums of squares, which primes are sums of two squares, and Thue's lemma. Unit 11, lightly.

Units 12 to 16 of the masterclass, on the distribution of the primes, the zeta function, and sieves, lie outside the olympiad syllabus. They are where the subject goes after it, and a student who has finished competing is the ideal reader.

Theorems to know cold

Knowing a theorem cold means being able to state it with its hypotheses, prove it, and recognize it in disguise. The short list: Bézout's identity; Euclid's lemma; the fundamental theorem of arithmetic; Legendre's formula; the Chinese remainder theorem; Fermat's little theorem; Euler's theorem; Wilson's theorem; the fact that the order divides φ(n); the existence of primitive roots modulo primes; the lifting-the-exponent lemma; Euler's criterion and the first supplement; the parametrization of Pythagorean triples; the structure of the solutions of Pell's equation. Fourteen items. A student who can prove all fourteen on a blank sheet has the theory of olympiad number theory, and what remains is practice.

Where the problems are

The official IMO site has every problem since 1959 with the statistics. The Art of Problem Solving forum holds the problems of nearly every national olympiad and most team selection tests, with solutions discussed in threads. Project Euler is a programming site rather than an olympiad, and its problems exercise the same theorems with a computer in hand, and a student who writes a program for Pell's equation understands Pell's equation. Among books, two classics: Ireland and Rosen, A Classical Introduction to Modern Number Theory, for the theory, and Titu Andreescu and Dorin Andrica, Number Theory: Structures, Examples, and Problems, for the olympiad side. Neither is cheap and both are in university libraries.

A training rhythm

Olympiad coaches disagree about most things and agree about this: solve problems under time, write the solutions out in full, and have them read by someone who will tell you what is missing. A plan that works for a student with a school year ahead of them:

First, learn the theory in order, one area a week, proving each theorem yourself before reading the proof. The masterclass is built for this; the quiz at the end of each unit checks the statement and the hypotheses, which is what a problem will test.

Second, for each area, solve ten problems from past national olympiads, easy ones first. Write each solution as if for a stranger. Then compare with a published solution and note what you would have lost points for.

Third, from a few months before the competition, sit timed papers: three problems, four and a half hours, no notes. Number theory problems are usually Problem 1 or 4 (the easier slots) or 3 or 6 (the hard ones), and the skill of recognizing which is which in the first ten minutes is worth as much as any theorem.

Fourth, keep a notebook of ideas, as distinct from theorems: "reduce modulo 4 when squares appear", "if a prime divides a product look at the orders", "when the equation is symmetric in two variables, try Vieta jumping". Over a year the notebook becomes the student's own syllabus.

For teachers

A school mathematics club usually has one or two students who could reach the national olympiad and a teacher who has not trained for it. The arrangement that works is a theory track next to a problem session: the students take the Foundation masterclass at one unit a week and bring the week's theorem to the club, where the group solves problems that use it. The teacher's role is to read the written solutions and ask where each step is justified, which needs no olympiad experience, only patience with "it is obvious". The For Schools and Teachers page describes the arrangement and the group enrolment, and the olympiad preparation guide on this site lists the units against the syllabus areas with the three IMO problems above worked as connections, without their solutions.

The European Girls' Mathematical Olympiad, held since 2012, has the same format and its own archive of problems; for university students, the Putnam competition in North America and the International Mathematics Competition for University Students cover the same number theory with analysis added. All of them reward the same thing: a short list of theorems, understood to the bottom, and a long list of problems, solved on paper.

Study the integers properly

The NT Masterclass: weekly units, quizzes, a final exam, and a certificate.
About the program