Tools this book assumes

An A-level course teaches a great deal that this book uses without comment: algebra, the circle theorems, similar triangles, the sine and cosine rules, permutations and combinations, the binomial theorem. It also leaves out a handful of things that competition problems lean on constantly. This chapter supplies those, and nothing else. Each one arrives through a problem it cracks, because a tool met while it is doing something is a tool you still have next month.

Read it once now, quickly, and come back when a solution points here. Everything the book needs beyond this chapter is proved where it is used.

Conventions and a few words

The natural numbers in this book are $1, 2, 3, \ldots$, and zero is not among them. Where a problem means to include zero it says so.

The greatest common divisor of $a$ and $b$, written $\gcd(a,b)$, is what school called the highest common factor. The competition literature says gcd almost without exception, so that is what is used here. Similarly $\operatorname{lcm}(a,b)$ is the lowest common multiple.

Two numbers are coprime when their only common factor is $1$, so $9$ and $14$ are coprime while $9$ and $15$ are not. The word does a lot of work in number theory problems, since a condition that two quantities share no factor is usually the hinge the problem turns on.

A lemma is a result proved on the way to something else, worth stating on its own because the main argument reads better once it is out of the way.

Congruences

A problem to start

What is the remainder when $7^{100}$ is divided by $5$?

Nobody wants to compute $7^{100}$. Notice instead that $7$ leaves remainder $2$ on division by $5$, and that remainders behave well under multiplication: if $7$ behaves like $2$, then $7^{100}$ behaves like $2^{100}$. Now $2^4 = 16$ leaves remainder $1$, so $$2^{100} = \left(2^4\right)^{25} \quad\text{behaves like}\quad 1^{25} = 1 .$$ The remainder is $1$.

The notation

That argument is worth a language of its own. Write $$a \equiv b \pmod{n}$$ to mean that $a$ and $b$ leave the same remainder on division by $n$, equivalently that $n$ divides $a - b$. Read it as “$a$ is congruent to $b$ modulo $n$”. So $7 \equiv 2 \pmod 5$, and $17 \equiv 5 \equiv -1 \pmod 6$. Negative representatives are allowed and are often the convenient ones.

The three rules

If $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then $$a + c \equiv b + d, \qquad a - c \equiv b - d, \qquad ac \equiv bd \pmod{n} .$$ Each follows from the definition in one line. For the last, write $a = b + kn$ and $c = d + ln$; then $ac = bd + n(bl + dk + kln)$, which differs from $bd$ by a multiple of $n$. Multiplying a congruence by itself repeatedly gives the fourth rule, the one that did the work above: if $a \equiv b \pmod n$ then $a^m \equiv b^m \pmod n$ for every positive integer $m$.

Where it goes wrong

You may not divide. From $2 \times 3 \equiv 2 \times 8 \pmod{10}$, which says $6 \equiv 16$, it does not follow that $3 \equiv 8 \pmod{10}$. Cancelling a factor $k$ is legitimate only when $\gcd(k, n) = 1$, and then it is legitimate always. Keep that condition in view: a large share of wrong solutions to number theory problems are a division nobody checked.

A second problem

What are the last two digits of $7^{2026}$?

The last two digits of a number are its remainder modulo $100$, so this asks for $7^{2026}$ modulo $100$. Compute the small powers: $7^2 = 49$, and $7^4 = 49^2 = 2401 \equiv 1 \pmod{100}$. That $1$ is the whole solution. Since $2026 = 4 \times 506 + 2$, $$7^{2026} = \left(7^4\right)^{506} \times 7^2 \equiv 1^{506} \times 49 = 49 \pmod{100} .$$ The last two digits are $49$. The shape recurs throughout the book: find the smallest power that comes back to $1$, then reduce the exponent modulo that.

Fermat’s little theorem

Sometimes the exponent that returns to $1$ can be named in advance. If $p$ is prime and $p$ does not divide $a$, then $$a^{p-1} \equiv 1 \pmod{p} .$$ Here is why. Consider the $p-1$ numbers $a, 2a, 3a, \ldots, (p-1)a$ modulo $p$. No two of them are congruent, since $ia \equiv ja$ would give $p \mid a(i-j)$, and $p$ divides neither $a$ nor the difference $i - j$, which lies strictly between $-p$ and $p$. None of them is $0$ modulo $p$ for the same reason. So they are the numbers $1, 2, \ldots, p-1$ in some order, and multiplying them together, $$a^{p-1} \times (p-1)! \equiv (p-1)! \pmod p .$$ Every factor of $(p-1)!$ is coprime to $p$, so it may be cancelled, which leaves the theorem.

For example, the remainder of $3^{100}$ modulo $7$: the theorem gives $3^6 \equiv 1$, and $100 = 6 \times 16 + 4$, so $3^{100} \equiv 3^4 = 81 \equiv 4 \pmod 7$.

The Euclidean algorithm

A problem to start

Find $\gcd(1071, 462)$ without factorising either number.

Any common divisor of $1071$ and $462$ divides their difference, and more usefully divides $1071 - 2 \times 462 = 147$. So the pair $(1071, 462)$ and the pair $(462, 147)$ have exactly the same common divisors, and the second pair is the smaller. Repeat: $$1071 = 2 \times 462 + 147, \qquad 462 = 3 \times 147 + 21, \qquad 147 = 7 \times 21 + 0 .$$ The last non-zero remainder is $21$, and $\gcd(1071, 462) = 21$.

The tool

Replacing $(a, b)$ by $(b, r)$, where $r$ is the remainder of $a$ on division by $b$, preserves the set of common divisors and strictly decreases the numbers, so the process stops. The last non-zero remainder is the greatest common divisor. It is fast: the numbers roughly halve every two steps, so even four-digit numbers take a handful of lines.

Running it backwards

Read the same equations upwards and each remainder becomes a combination of the two original numbers: $$21 = 462 - 3 \times 147 = 462 - 3\left(1071 - 2 \times 462\right) = 7 \times 462 - 3 \times 1071 .$$ This always works, and it proves something the book uses repeatedly: for any $a$ and $b$ there are integers $x$ and $y$ with $$ax + by = \gcd(a, b) ,$$ and in particular $ax + by = 1$ can be solved exactly when $a$ and $b$ are coprime. One consequence deserves its own line, since it is the reason primes matter: if a prime $p$ divides $ab$ then it divides $a$ or it divides $b$.

Proof by induction

A problem to start

Show that $1^3 + 2^3 + \cdots + n^3 = \left(\tfrac{1}{2}n(n+1)\right)^2$ for every natural number $n$.

Check $n = 1$: the left side is $1$ and the right side is $1$. Now suppose the formula holds for some particular $n$, and add the next cube: $$\begin{align*} \left(\tfrac{1}{2}n(n+1)\right)^2 + (n+1)^3 &= (n+1)^2\left(\frac{n^2}{4} + n + 1\right) \\ &= (n+1)^2 \times \frac{n^2 + 4n + 4}{4} \\ &= \left(\tfrac{1}{2}(n+1)(n+2)\right)^2 , \end{align*}$$ which is the formula for $n+1$. Since it holds at $1$, it holds at $2$, and so on through every natural number.

The tool

To prove a statement $P(n)$ for all $n \geq n_0$, prove $P(n_0)$ and prove that $P(n)$ implies $P(n+1)$. Both halves are needed. The first is not a formality: plenty of false statements survive the second test and fail the first.

A variant appears often here. Strong induction assumes $P(k)$ for every $k$ below $n$ rather than for $n-1$ alone, and is what you want when the step reaches back several places, as it does whenever a problem splits a number into two smaller ones.

The pigeonhole principle

A problem to start

Fifty-one numbers are chosen from $1$ to $100$. Show that two of them are coprime.

Pair the numbers off as $(1,2), (3,4), (5,6), \ldots, (99,100)$, which is fifty pairs. Fifty-one chosen numbers cannot avoid putting two into the same pair, and two numbers in the same pair are consecutive. Consecutive numbers differ by $1$, so any common divisor divides $1$, and they are coprime.

The tool

If $n$ objects go into $k$ boxes and $n > k$, some box holds at least two. More is true and is used just as often: some box holds at least $\lceil n/k \rceil$ objects, since if every box held fewer there would be fewer than $n$ objects in total.

The principle is trivial. The work is always in choosing the boxes, and that choice is the crux of every problem that uses it.

Inclusion and exclusion

A problem to start

How many of the numbers $1$ to $100$ are divisible by $2$, by $3$ or by $5$?

There are $50$ multiples of $2$, $33$ of $3$ and $20$ of $5$. Adding those counts every multiple of $6$, of $10$ and of $15$ twice, so subtract $16$, $10$ and $6$. That subtraction has now removed the multiples of $30$ three times having added them three times, so add the $3$ of them back: $$50 + 33 + 20 - 16 - 10 - 6 + 3 = 74 .$$

The tool

For two sets, $|A \cup B| = |A| + |B| - |A \cap B|$. For three, $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |C \cap A| + |A \cap B \cap C| .$$ In general, add the sizes of the sets, subtract the sizes of all pairwise intersections, add back the triples, and continue with alternating signs. The reason is a count from the point of view of one object: an object in exactly $m$ of the sets is counted $m$ times, then removed $\binom{m}{2}$ times, then restored $\binom{m}{3}$ times, and the alternating sum $\binom{m}{1} - \binom{m}{2} + \cdots$ equals $1$ for every $m \geq 1$.

The arithmetic and geometric means

A problem to start

A rectangle has perimeter $40$. How large can its area be?

Let the sides be $a$ and $b$ with $a + b = 20$. Then $$ab = \left(\frac{a+b}{2}\right)^2 - \left(\frac{a-b}{2}\right)^2 = 100 - \left(\frac{a-b}{2}\right)^2 ,$$ which is largest when $a = b$, giving area $100$. No calculus was needed, and the answer came with its equality case attached.

The tool

For non-negative $a$ and $b$, $$\frac{a+b}{2} \geq \sqrt{ab} ,$$ with equality exactly when $a = b$. This is $\left(\sqrt a - \sqrt b\right)^2 \geq 0$ rearranged. For three non-negative numbers, $$\frac{a+b+c}{3} \geq \sqrt[3]{abc} ,$$ with equality exactly when $a = b = c$. Writing $a = x^3$, $b = y^3$, $c = z^3$, this is the identity $$x^3 + y^3 + z^3 - 3xyz = (x+y+z)\left(x^2 + y^2 + z^2 - xy - yz - zx\right)$$ together with the observation that the second bracket equals $\tfrac{1}{2}\left((x-y)^2 + (y-z)^2 + (z-x)^2\right)$ and so is never negative.

Use it in the direction that helps: a sum bounded below by a product when the product is fixed, a product bounded above by a sum when the sum is fixed. The equality case is half the tool, since it tells you where the extreme configuration sits.

Geometry the A-level course leaves out

An A-level course does geometry with coordinates, vectors and trigonometry, and leaves the synthetic subject at GCSE. Four things from that older tradition are needed here, and each is a short argument from what school already gave you.

Three centres and a word

The incentre of a triangle is where its three angle bisectors meet, and it is the centre of the circle that touches all three sides. The circumcentre is where the perpendicular bisectors of the sides meet, and it is the centre of the circle through all three vertices. The orthocentre is where the three altitudes meet. Each of those three claims is that three lines pass through one point, and each is proved where the book first needs it.

Four or more points are concyclic when a single circle passes through all of them. Showing that four points are concyclic is one of the most useful moves in the subject, because it puts the circle theorems at your disposal: opposite angles of the quadrilateral then add to $180$ degrees, and angles standing on the same chord from the same side are equal.

Similar triangles, the workhorse

Two triangles with equal angles have proportional sides. Almost every synthetic solution in this book is a hunt for a pair of similar triangles, and the usual way to find one is an angle chase: equal angles in the same segment, angles in a cyclic quadrilateral, the alternate segment theorem, or a pair of parallel lines.

The angle bisector theorem

In triangle $ABC$, let the bisector of the angle at $A$ meet $BC$ at $D$. Then $$\frac{BD}{DC} = \frac{AB}{AC} .$$ Compare the two triangles $ABD$ and $ACD$. They have the same height from $A$, so their areas are in the ratio $BD : DC$. Using the formula $\tfrac12 pq \sin \theta$ on the angle at $A$, which the bisector splits into two equal halves, their areas are also in the ratio $AB : AC$. The two ratios are equal.

The power of a point

Let a line through $P$ meet a circle at $A$ and $B$, and another line through $P$ meet it at $C$ and $D$. Then $$PA \times PB = PC \times PD .$$ When $P$ is inside the circle, triangles $PAC$ and $PDB$ have equal angles at $P$, being vertically opposite, and equal angles at $A$ and $D$, being angles in the same segment on $BC$. So they are similar and $PA/PD = PC/PB$, which rearranges to the claim. When $P$ is outside, the same pair of triangles is similar for the same reasons, with the angle at $P$ now shared rather than vertically opposite.

The tangent case is the one to remember: if $PT$ touches the circle at $T$, then $$PT^2 = PA \times PB ,$$ which follows by the alternate segment theorem in place of the angles in the same segment. The common value is called the power of $P$, and a problem that mentions two circles and a point is very often asking about it.

Ptolemy’s theorem

For a cyclic quadrilateral $ABCD$, $$AC \times BD = AB \times CD + BC \times DA .$$ It is used twice in this book and proved at its first use, since the construction that proves it is worth seeing where it is doing work rather than here.

What is not here

Everything else. Where a solution needs a result this chapter has not given, it proves the case it needs on the spot, and where a solution needs an idea rather than a result, the crux at its head names the idea before the computation starts. Nothing in the book asks you to accept a theorem you have not seen justified, and nothing in it uses calculus.