Discrete Mathematics

The mathematics of things that come in whole pieces: counting without listing, recurrences, the arithmetic of whole numbers that secures the internet, and graphs.

Counting without listing

Many questions in mathematics and computing ask how many, and listing the answers stops being possible almost at once: there are more subsets of a forty element set than there are stars in the Milky Way.

This lesson collects the four tools that count without listing. Two of them, the sum and product rules, build a count from smaller counts. The third counts a set by pairing it perfectly with a set that is easier to count. The fourth, the pigeonhole principle, does something stranger: it uses a count to prove that an object exists without ever producing it. The lesson assumes only sets and functions, and it recalls what a bijection is where it is needed.

The sum rule

If a set splits into pieces that do not overlap, its size is the sum of the sizes of the pieces. Written with sets, if $A$ and $B$ are disjoint then $| A \cup B | = | A | + | B |$ , and the same holds for any finite number of pairwise disjoint pieces. The proof is hardly a proof: counting every element of the union once is the same as counting the elements of $A$ and then carrying on through $B$ , and disjointness guarantees that nothing is met twice.

The rule is almost too obvious to state, and its value lies in what it permits. A hard count can be broken into cases, each case counted by whatever method suits it, and the answers added. The one condition is that the cases must not overlap, and a case analysis that quietly double counts is the most common error in the subject. When the pieces do overlap, the sum overcounts by exactly the elements that are shared, and correcting for that exactly is the business of a later lesson on inclusion and exclusion.

A close relative is counting by complement. If $A$ sits inside a universe $U$ , then $A$ and its complement $U ∖ A$ split $U$ into two disjoint pieces, so $| A | = | U | - | U ∖ A |$ . This is the sum rule read backwards, and it is the right move whenever a condition says "at least one": the complement says "none", which is usually far easier to count. How many integers from $1$ to $999$ contain at least one digit $7$ ? Pad each with leading zeros to three digits; the strings with no $7$ anywhere number $9 \times 9 \times 9 = 729$ , which includes $000$ , so $728$ of the integers from $1$ to $999$ avoid the digit, and the remaining $999 - 728 = 271$ contain it.

That last count already used a multiplication, and the rule behind it deserves its own section.

The product rule

The probability course derives the product rule from a grid of choices: if a first choice can be made in $a$ ways and, whatever it was, a second in $b$ ways, the pair can be made in $a b$ ways. With $k$ stages it becomes a product of $k$ factors. The proof is the sum rule in disguise: group the outcomes by the first choice, so that there are $a$ disjoint groups of $b$ each, and add.

That grouping also shows exactly what the rule needs. The later stages may depend on the earlier ones in which options they offer, but not in how many. Consider four digit PINs in which no two adjacent digits are equal. The first digit has $10$ options. The second must differ from the first, and whichever the first was, that leaves $9$ . The third must differ from the second, again $9$ , and the fourth $9$ more, giving $10 \times 9^{3} = 7290$ . The set of allowed digits changes at every stage, but its size does not, and size is all the rule looks at.

Two real systems show the rule at work. The Dartmouth BASIC of 1964 allowed a variable name to be a single letter or a letter followed by one digit. Those two kinds of name are disjoint, so the sum rule adds them, and the product rule counts the second kind: $26 + 26 \times 10 = 286$ variables in all. The genetic code reads DNA, an alphabet of four bases, in words called codons that specify twenty amino acids and a stop signal. Words of two bases would give only $4^{2} = 16$ possibilities, too few for twenty one meanings; words of three give $4^{3} = 64$ , which is enough with room to spare, and the real code is indeed read in triplets, most amino acids having several codons.

Example. How many integers from $1$ to $9999$ contain no digit $0$ ?

Split by the number of digits, since integers of different lengths form disjoint sets and the sum rule will add them. An integer with $d$ digits and no zero has each of its $d$ digits chosen from $1$ to $9$ , so by the product rule there are $9^{d}$ of them. The total is $9 + 81 + 729 + 6561 = 7380$ . Padding with leading zeros would not have worked directly here, because the padded zeros are exactly what the condition forbids, which is why the cases were needed.

Now you. How many integers from $1$ to $999$ have all their digits different?

Answer

Split by length again. One digit integers: $9$ . Two digits: the first from $1$ to $9$ , the second any of the $9$ digits other than the first, so $81$ . Three digits: $9 \times 9 \times 8 = 648$ , since the third must avoid two digits already used. The total is $9 + 81 + 648 = 738$ .

Counting one set by counting another

A bijection from $A$ to $B$ is a function that pairs every element of $A$ with exactly one element of $B$ and leaves nothing in $B$ unpaired. For finite sets that is the definition of having the same size, so $| A | = | B |$ as soon as a bijection exists, and the second set may be much easier to count than the first. Much of combinatorics consists of finding the right $B$ .

The cleanest illustration is a knockout tournament. The Wimbledon singles draw has $128$ players; how many matches are played? One could count rounds: $64$ in the first, then $32$ , $16$ , $8$ , $4$ , $2$ and the final, totalling $127$ . The bijection argument is shorter and more general. Every match produces exactly one loser, and every player except the champion loses exactly once, since a loss ends their tournament. So matches pair off perfectly with the players who are not the champion, and there are $128 - 1 = 127$ of them. The same argument works for a draw of $100$ players with byes, where counting by rounds becomes awkward: $99$ matches, whatever the arrangement of the byes.

A bijection is a claim that has to be checked in both directions. It must be a function (each element of $A$ goes somewhere definite), it must be one to one (different elements go to different places), and it must be onto (everything in $B$ is hit). The usual way to settle the last two at once is to write down the inverse: a rule taking each element of $B$ back to the element of $A$ it came from. In the tournament, the inverse takes a non-champion to the match they lost, which is plainly well defined.

Divisors give a more arithmetical example. Every positive integer factors into primes in exactly one way, a fact proved in a later lesson, so $720 = 2^{4} \times 3^{2} \times 5$ . A divisor of $720$ can only use these primes, and no more of each than $720$ has, so it is $2^{a} 3^{b} 5^{c}$ with $0 \leq a \leq 4$ , $0 \leq b \leq 2$ and $0 \leq c \leq 1$ . Uniqueness of factorisation makes the map from exponent triples to divisors a bijection, and the triples are counted by the product rule.

Example. How many positive divisors does $720$ have?

By the bijection just described, the divisors correspond to triples $(a, b, c)$ with $a$ one of the $5$ values $0$ to $4$ , $b$ one of the $3$ values $0$ to $2$ , and $c$ one of the $2$ values $0$ or $1$ . The product rule gives $5 \times 3 \times 2 = 30$ . In general, a number whose factorisation has exponents $e_{1}, e_{2}, \dots, e_{r}$ has $(e_{1} + 1) (e_{2} + 1) \dots (e_{r} + 1)$ divisors, the $+ 1$ in each factor accounting for the option of leaving that prime out.

Now you. How many positive divisors does $1 000 000$ have, and how many of them are perfect squares?

Answer

$1 000 000 = 2^{6} \times 5^{6}$ , so there are $7 \times 7 = 49$ divisors. A divisor $2^{a} 5^{b}$ is a perfect square exactly when both exponents are even, which allows $a$ and $b$ each to be $0$ , $2$ , $4$ or $6$ , giving $4 \times 4 = 16$ square divisors.

Subsets and bit strings

How many subsets does a set of $n$ elements have? List the elements in some fixed order, $x_{1}, x_{2}, \dots, x_{n}$ , and send each subset $S$ to the string of $n$ bits whose $i$ th bit is $1$ if $x_{i} \in S$ and $0$ if not. The subset ${x_{1}, x_{3}}$ of a four element set becomes $1010$ , the empty set becomes $0000$ and the whole set $1111$ . The inverse reads the string and collects the positions holding a $1$ , so this is a bijection, and the bit strings are counted by the product rule: each of the $n$ positions has $2$ options, giving $2^{n}$ .

The same picture explains why computers store sets this way. A subset of a $64$ element set fits exactly in one $64$ bit machine word, union becomes bitwise OR, and intersection becomes bitwise AND. It also shows how fast subsets multiply: a thirty element set has $2^{30} = 1 073 741 824$ of them, so an algorithm that checks every subset of its input is hopeless well before the input reaches a hundred items.

Bijections can also compare two sets without counting either. Among the subsets of ${1, 2, \dots, n}$ , with $n \geq 1$ , which are more numerous, those of even size or those of odd size? Pair each subset with the one obtained by toggling the element $1$ : add it if absent, remove it if present. Toggling twice returns the original subset, so the map is its own inverse and therefore a bijection, and it changes the size by exactly one, so it pairs every even subset with an odd one. The two kinds are equal in number, $2^{n - 1}$ each, and no formula for the number of subsets of a given size was needed to see it.

The pigeonhole principle

If more than $k$ objects are placed in $k$ boxes, some box holds at least two. The proof is by contradiction: if every box held at most one, there would be at most $k$ objects. What makes the principle powerful is what it does not say. It names no box and no pair, so it proves existence without construction, and the art is entirely in choosing the boxes.

A counting fact about files shows the flavour. No lossless compressor can shorten every file. There are $2^{n}$ files of exactly $n$ bits, but only $2^{0} + 2^{1} + \dots + 2^{n - 1} = 2^{n} - 1$ files shorter than that. If every $n$ bit file were sent to a shorter one, two would land on the same output, and decompression could not tell them apart. Every compressor that shrinks some files must lengthen others.

Example. Prove that any $11$ integers chosen from $1$ to $20$ include two of which one divides the other.

Write each integer as $2^{a} m$ with $m$ odd; $m$ is its odd part. The odd parts of numbers from $1$ to $20$ lie among the ten odd numbers $1, 3, \dots, 19$ , so these are the boxes. Eleven integers in ten boxes put two, say $2^{a} m$ and $2^{b} m$ with $a < b$ , in the same box, and then the first divides the second. The bound is sharp: the ten integers $11$ to $20$ contain no such pair, since the smallest multiple of $11$ beyond itself is $22$ . This is a result of Paul Erdős, stated for $n + 1$ integers from $1$ to $2 n$ .

Now you. Prove that any $6$ integers chosen from $1$ to $10$ include two that sum to $11$ .

Answer

Use as boxes the five pairs ${1, 10}$ , ${2, 9}$ , ${3, 8}$ , ${4, 7}$ and ${5, 6}$ , each summing to $11$ and together covering $1$ to $10$ . Six integers in five boxes put two in the same pair, and they sum to $11$ . Five integers are not enough: $1$ to $5$ contains no such pair.

The generalised form

If $N$ objects go into $k$ boxes, some box holds at least $⌈ N / k ⌉$ of them, the ceiling meaning $N / k$ rounded up. Again by contradiction: if every box held at most $⌈ N / k ⌉ - 1$ , which is less than $N / k$ , the total would be less than $k \times N / k = N$ .

The 2021 census counted $8 799 800$ people in London. A human scalp carries around a hundred thousand hairs, and certainly nobody has a million, so the possible hair counts are $0$ to $999 999$ , a million boxes. Some hair count is therefore shared by at least $⌈ 8 799 800 / 1 000 000 ⌉ = 9$ Londoners. Nobody will ever find them, and the argument does not need to.

Read the other way, the principle gives thresholds. To guarantee that three people share a birth month, $2 \times 12 + 1 = 25$ people are needed: twenty four could be spread two per month.

What the rules leave open

The sum and product rules, bijections and the pigeonhole principle count anything whose structure can be described, and the structures that turn up most often are arrangements and selections. How many orders can ten runners finish in, or how many committees of three can ten people form? The product rule answers the first and, with a correction for order, the second, but the same reasoning recurs so often that it deserves formulas of its own. The next lesson derives them, and extends them to selections in which repetition is allowed.

Arrangements and selections

Arrangements and selections are the structures counted most often, and the product rule reaches them only by rebuilding the same argument every time.

This lesson turns that argument into formulas. It starts from the two questions the previous lesson left open, how many orders ten runners can finish in and how many committees of three ten people can form, then goes further: words whose letters repeat, selections in which a kind may be taken more than once, and routes along a grid. Each needs the right set to count, reached by a bijection (a perfect pairing between two sets, which forces them to have the same size) to something the product rule already handles.

Arrangements

Ten runners cross the line. The winner is any of the $10$ ; whoever won, second place is any of the $9$ left; then $8$ for third, and so on down to $1$ . The product rule, which multiplies the number of options at each stage provided that number does not depend on earlier choices, gives $10 \times 9 \times \dots \times 1 = 3 628 800$ finishing orders. The product $n (n - 1) \dots 1$ is written $n!$ , read " $n$ factorial", and an ordering of $n$ distinct objects is a permutation of them. The convention $0! = 1$ , one way to arrange nothing, keeps the formulas below true at their edges.

If only the podium matters, the product stops after three stages: $10 \times 9 \times 8 = 720$ ways to award gold, silver and bronze. In general an ordered selection of $k$ objects from $n$ , nothing reused, can be made in

P (n, k) = n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!}

ways, the second form being the full factorial with the orders of the unused $n - k$ objects divided away. The probability course derives this and the next formula the same way and applies them to poker hands and the birthday problem.

Selections

A committee of three is a set, not a sequence. The $720$ podium lists count Ana, Ben, Chloe and Chloe, Ben, Ana separately, while as a committee they are one. The fix is the division rule: if a map from one set onto another sends exactly $d$ elements to each element of the target, the target has $1 / d$ as many elements. Send each ordered list of three people to the set of those three. Every committee is hit by exactly $3! = 6$ lists, one per ordering of its members, so there are $720 / 6 = 120$ committees.

The number of $k$ element subsets of an $n$ element set is written $(\binom{n}{k})$ , read " $n$ choose $k$ ", and the same argument gives

(\binom{n}{k}) = \frac{P (n, k)}{k!} = \frac{n!}{k! (n - k)!}

The formula is symmetric in $k$ and $n - k$ , and a bijection explains why without algebra: sending each subset to its complement pairs the $k$ element subsets perfectly with the $(n - k)$ element ones.

The previous lesson paired the subsets of an $n$ element set with bit strings of length $n$ , a $1$ marking each chosen element. Under that pairing a $k$ element subset becomes a string with exactly $k$ ones, so $(\binom{8}{3}) = 56$ bytes have exactly three bits set. This reading, $(\binom{n}{k})$ as the number of ways to choose which $k$ of $n$ positions receive a given symbol, is the one the rest of the lesson uses over and over.

Words with repeated letters

How many strings can be made by rearranging MISSISSIPPI? The probability course pretends the letters are distinct, giving $11!$ , then divides out the $4!$ orders of the S's, the $4!$ of the I's and the $2!$ of the P's that the pretence counted separately, reaching $34 650$ .

A second derivation builds the word instead of correcting an overcount, and it is the one that generalises. An arrangement is fixed once we know which positions hold each letter. Of the $11$ positions, choose the $1$ for M in $(\binom{11}{1}) = 11$ ways; of the $10$ left, the $4$ for the I's in $(\binom{10}{4}) = 210$ ways; of the $6$ still free, the $4$ for the S's in $(\binom{6}{4}) = 15$ ways; the last $2$ take the P's. The number of options at each stage does not depend on which positions were taken before, so the product rule gives $11 \times 210 \times 15 \times 1 = 34 650$ . Written out in factorials, everything cancels except $11!$ on top and $1! 4! 4! 2!$ below.

In general a word of length $n$ with $n_{1}$ copies of one letter, $n_{2}$ of another and so on up to $n_{r}$ has

\frac{n!}{n_{1}! n_{2}! \dots n_{r}!}

arrangements, a multinomial coefficient. With only two kinds of letter it is $(\binom{n}{k})$ itself: arranging $k$ ones and $n - k$ zeros is the bit string count again.

Example. How many distinct arrangements does BOOKKEEPER have?

Count the letters first, since everything rests on it: B once, O twice, K twice, E three times, P once and R once, all $10$ accounted for. Then

\frac{10!}{2! 2! 3!} = \frac{3 628 800}{24} = 151 200

omitting the factors $1! = 1$ . Checking by positions: $(\binom{10}{3}) = 120$ ways to place the E's, $(\binom{7}{2}) = 21$ for the O's, $(\binom{5}{2}) = 10$ for the K's, and $3! = 6$ for the three single letters, and $120 \times 21 \times 10 \times 6 = 151 200$ .

Now you. How many distinct arrangements does ABRACADABRA have, and in how many do the five A's stand together?

Answer

A five times, B twice, R twice, C and D once each, eleven in all: $11! / (5! 2! 2!) = 83 160$ arrangements. With the A's together, glue them into one block; the word becomes seven symbols, the block, B, B, R, R, C and D, with $7! / (2! 2!) = 1260$ arrangements.

Selections with repetition

A domino is an unordered pair of spot counts from $0$ to $6$ , repetition allowed, since the double six is a tile. Pairs of different values number $(\binom{7}{2}) = 21$ and doubles $7$ , so a full set has $28$ tiles, as a real set does. Splitting into cases works for pairs but soon becomes painful. Three identical dice show a multiset of size three from six values (a multiset being a collection where order does not matter but repetition is allowed), and the cases all different, two alike and all alike already need care. One idea handles every case at once.

Record a multiset of size $k$ from $n$ types as a row of $k$ stars and $n - 1$ bars. The bars cut the row into $n$ compartments, one per type in a fixed order, and the stars in each compartment say how many of that type were taken. For three dice, ${2, 2, 5}$ becomes |**|||*|: nothing before the first bar, so no $1$ ; two stars, so two $2$ s; two empty compartments for $3$ and $4$ ; one star for the $5$ ; nothing for $6$ . Any row of $3$ stars and $5$ bars reads back as exactly one multiset, so this is a bijection, and the rows are counted by choosing which of the $k + n - 1$ positions hold stars. The number of multisets of size $k$ from $n$ types is therefore

(\binom{n + k - 1}{k})

Three dice give $(\binom{8}{3}) = 56$ distinguishable outcomes, and dominoes $(\binom{8}{2}) = 28$ , agreeing with the case count. The method is called stars and bars, and its only difficulty is seeing that the thing to count is not the objects but the dividers between the types.

Equations and distributions

The same count wears two other disguises. A multiset of size $k$ from $n$ types is determined by how many of each type it holds, whole numbers $x_{1}, \dots, x_{n}$ , each at least $0$ , adding to $k$ . So $x_{1} + x_{2} + \dots + x_{n} = k$ has $(\binom{n + k - 1}{k})$ solutions in nonnegative integers. Handing $k$ identical objects to $n$ people is the same list of numbers again: ten identical sweets shared among four children, some perhaps getting none, can be shared in $(\binom{13}{3}) = 286$ ways.

Lower bounds are handled by handing out the guaranteed part first. If each child must get at least one sweet, give each one, then share the remaining six freely: $(\binom{9}{3}) = 84$ ways. As equations, $y_{i} = x_{i} - 1$ turns a positive solution of $x_{1} + \dots + x_{4} = 10$ into a nonnegative solution of $y_{1} + \dots + y_{4} = 6$ and back, a bijection. In general $x_{1} + \dots + x_{n} = k$ has $(\binom{k - 1}{n - 1})$ positive solutions.

Upper bounds are different. If no child may have more than four sweets, there is nothing to hand out first. One counts everything and removes the distributions where some child exceeds the limit, but several can exceed it at once, so the removed sets overlap. Correcting for that overlap is the job of inclusion and exclusion, in a later lesson.

Example. A bakery sells five kinds of doughnut. How many different boxes of a dozen are there, and how many contain at least one of each kind?

A box is a multiset of size $12$ from $5$ types, $12$ stars and $4$ bars: $(\binom{16}{4}) = 1820$ boxes. For at least one of each, place one of each kind first and choose the other $7$ freely: $(\binom{11}{4}) = 330$ boxes, which the positive solution formula confirms as $(\binom{12 - 1}{5 - 1})$ .

Now you. How many solutions does $a + b + c + d = 20$ have in integers with every variable at least $2$ ?

Answer

Set $a^{'} = a - 2$ and likewise for the others. Then $a^{'} + b^{'} + c^{'} + d^{'} = 12$ with every variable at least $0$ , which has $(\binom{15}{3}) = 455$ solutions.

Lattice paths

Most of Manhattan is a grid of streets and avenues, fixed by the Commissioners' Plan of 1811. A walker going $5$ blocks east and $3$ north, never doubling back, has many shortest routes. Model the grid as the points with integer coordinates and a route as a lattice path from $(0, 0)$ to $(5, 3)$ made of unit steps, each right, $R$ , or up, $U$ .

The thing to count is the sequence of steps. Every such path takes five $R$ s and three $U$ s in some order, so it is a word of length $8$ , and every such word traces exactly one path. Choosing which $3$ of the $8$ positions are $U$ gives $(\binom{8}{3}) = 56$ routes, and in general there are $(\binom{m + n}{n})$ lattice paths from $(0, 0)$ to $(m, n)$ .

Conditions yield to the product and sum rules. A path from $(0, 0)$ to $(6, 4)$ through $(2, 2)$ is a path to $(2, 2)$ followed by an independent path onwards, so the counts of the two legs multiply. A path that must avoid a point is counted by complement: all paths, minus those through it. Some conditions are harder. The paths from $(0, 0)$ to $(n, n)$ that never rise above the line $y = x$ cannot be split at one point, since the condition binds at every step; there are $5$ for $n = 3$ and $42$ for $n = 5$ , the Catalan numbers, which a later lesson counts with generating functions.

Example. How many lattice paths run from $(0, 0)$ to $(6, 4)$ , how many pass through $(2, 2)$ , and how many avoid it?

All paths: $(\binom{10}{4}) = 210$ . To $(2, 2)$ there are $(\binom{4}{2}) = 6$ paths, and from $(2, 2)$ the walker needs $4$ right and $2$ up, $(\binom{6}{2}) = 15$ paths. Through the point, $6 \times 15 = 90$ ; avoiding it, $210 - 90 = 120$ .

Now you. How many lattice paths from $(0, 0)$ to $(7, 5)$ avoid the point $(3, 2)$ ?

Answer

All paths: $(\binom{12}{5}) = 792$ . Through $(3, 2)$ : $(\binom{5}{2}) = 10$ paths to it and, with $4$ right and $3$ up remaining, $(\binom{7}{3}) = 35$ from it, so $350$ . Avoiding it: $792 - 350 = 442$ .

Choosing what to count

Selecting $k$ things from $n$ kinds now has four answers, set by two questions: does order matter, and may a kind repeat? Ordered with repetition, the product rule gives $n^{k}$ . Ordered without, $P (n, k)$ . Unordered without, $(\binom{n}{k})$ . Unordered with, $(\binom{n + k - 1}{k})$ . With $n = 5$ and $k = 3$ they are $125$ , $60$ , $10$ and $35$ , so choosing the wrong model is never a small error.

Most counting mistakes answer a different question from the one asked, and the question to settle first is whether swapping two objects produces a different outcome. Ten different sweets handed to four children is ten independent choices of recipient, $4^{10} = 1 048 576$ ways, not the $286$ of identical sweets. Three dice rolled by three different people give $6^{3} = 216$ sequences, while three identical dice rolled together show one of $56$ outcomes, and those outcomes are not equally likely: ${1, 2, 3}$ arises from $6$ sequences and ${1, 1, 1}$ from one. Stars and bars counts outcomes, not probabilities.

A reliable habit is to state the bijection in words, such as "a box of doughnuts is a row of $12$ stars and $4$ bars", and check it both ways before computing. When no single formula fits, split into cases that do not overlap and add, as the domino count did with its doubles.

Numbers that keep returning

The binomial coefficients have appeared in every section: as committees, bit strings, positions in a word, stars and bars, and routes. They also satisfy identities that look like accidents of algebra. Checking $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ by expanding factorials takes a line of fractions and explains nothing, and $(\binom{n}{0}) + (\binom{n}{1}) + \dots + (\binom{n}{n}) = 2^{n}$ looks just as mysterious.

The lattice paths hint that neither is an accident. Every path to $(m, n)$ arrives by a last step, from $(m - 1, n)$ or from $(m, n - 1)$ , and the two kinds do not overlap, so the count to each point is the sum of the counts to the two points behind it. Written in binomial coefficients, that sentence is the first identity. The next lesson makes it a method: count one set in two ways, set the answers equal, and the identity arrives with its reason attached.

Binomial coefficients

The numbers $(\binom{n}{k})$ turn up in counts of committees, lattice paths and bit strings, and they satisfy a crowd of identities that look, when proved by pushing factorials around, like accidents of algebra.

They are not accidents. This lesson proves them with a method that runs through the rest of the course: find one set, count it in two different ways, and set the two answers equal. Each identity then says something you can see, rather than something you have to trust. The same idea explains why these numbers appear as the coefficients when $(x + y)^{n}$ is multiplied out, which is where their name comes from. The lesson assumes the previous one, which defined $(\binom{n}{k})$ as the number of $k$ element subsets of an $n$ element set, and it recalls whatever else it needs.

Pascal's rule

Recall the formula. Choosing $k$ things in order from $n$ can be done in $n (n - 1) \dots (n - k + 1)$ ways by the product rule, and each unordered choice has been counted once for each of its $k!$ orders, so

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}

for $0 \leq k \leq n$ . For $k$ outside that range there are no such subsets, and $(\binom{n}{k}) = 0$ , a convention that saves a great many special cases below. So ten people can form $(\binom{10}{3}) = 120$ committees of three.

The formula is symmetric in $k$ and $n - k$ , so $(\binom{n}{k}) = (\binom{n}{n - k})$ . The explanation is a bijection, a function pairing two sets perfectly with nothing left over: send each $k$ element subset to its complement, the $n - k$ elements left behind. Different subsets have different complements, and every $n - k$ element subset is the complement of exactly one $k$ element subset, so the two collections have the same size. Choosing three people for a committee is the same act as choosing seven to stay at home.

The rule that generates everything else is Pascal's rule: for $1 \leq k \leq n$ ,

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

Here is a proof that uses no factorials. Count the $k$ person committees drawn from $n$ people, one of whom is called Ada. Every committee either includes Ada or does not, and those two kinds do not overlap, so by the sum rule their counts add. A committee that includes Ada is fixed by choosing its other $k - 1$ members from the remaining $n - 1$ people, in $(\binom{n - 1}{k - 1})$ ways. A committee that leaves her out takes all $k$ members from the other $n - 1$ , in $(\binom{n - 1}{k})$ ways. The total is $(\binom{n}{k})$ by definition, and the rule is proved.

The algebraic proof, putting both fractions over $k! (n - k)!$ , is correct but gives no reason for the answer to be so simple. The committee proof gives the reason: Ada is either in or out.

Laid out in rows, with row $n$ holding $(\binom{n}{0})$ to $(\binom{n}{n})$ , Pascal's rule says each entry is the sum of the two above it. Rows $0$ to $6$ read $1$ ; $1, 1$ ; $1, 2, 1$ ; $1, 3, 3, 1$ ; $1, 4, 6, 4, 1$ ; $1, 5, 10, 10, 5, 1$ ; and $1, 6, 15, 20, 15, 6, 1$ . Blaise Pascal wrote the triangle up systematically in his Traité du triangle arithmétique of 1654, but it is far older: Yang Hui printed it in 1261, crediting Jia Xian two centuries earlier, and in China it still carries Yang Hui's name.

Counting in two ways

Pascal's rule was proved by a pattern worth naming. Pick a set, here the committees. Count it one way, getting the left side, and another way, getting the right. Both answers count the same set, so they are equal. This is double counting, and its one real difficulty is choosing the set.

A good first test is the identity

k (\binom{n}{k}) = n (\binom{n - 1}{k - 1})

To see it, count the committees of $k$ people from $n$ in which one member is marked as chair. First choose the committee, in $(\binom{n}{k})$ ways, and then its chair from among its $k$ members, giving $k (\binom{n}{k})$ . Alternatively, choose the chair first from all $n$ people, then fill the other $k - 1$ seats from the $n - 1$ left, giving $n (\binom{n - 1}{k - 1})$ . Same set, two counts, and the identity follows.

Example. Check the chair identity with $n = 12$ and $k = 5$ , and say what the common number counts.

The left side is $5 (\binom{12}{5}) = 5 \times 792 = 3960$ . The right side is $12 (\binom{11}{4}) = 12 \times 330 = 3960$ . Both count the ways a club of twelve can form a five person committee with one member as chair: $792$ committees, each with five possible chairs, or twelve possible chairs, each with $330$ ways to fill the remaining four seats.

Now you. Prove that $(\binom{n}{k}) (\binom{k}{m}) = (\binom{n}{m}) (\binom{n - m}{k - m})$ for $0 \leq m \leq k \leq n$ by counting one set in two ways, and check it with $n = 10$ , $k = 4$ , $m = 2$ .

Answer

Count the ways to choose a committee of $k$ from $n$ people together with a subcommittee of $m$ inside it. Choosing the committee first and then the subcommittee from its members gives $(\binom{n}{k}) (\binom{k}{m})$ . Choosing the subcommittee first from everyone, then the other $k - m$ committee members from the $n - m$ people outside it, gives $(\binom{n}{m}) (\binom{n - m}{k - m})$ . With the numbers, $210 \times 6 = 1260$ and $45 \times 28 = 1260$ .

The binomial theorem

Multiply out $(x + y)^{3}$ and the coefficients are $1, 3, 3, 1$ , row $3$ of the triangle. Multiply out $(x + y)^{4}$ and they are $1, 4, 6, 4, 1$ . The pattern is the binomial theorem:

(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k}

Write $(x + y)^{n}$ as $n$ brackets multiplied together. Expanding the product means choosing one term, $x$ or $y$ , from each bracket, multiplying the choices, and adding up the results over every possible set of choices, $2^{n}$ of them in all. A set of choices gives $x^{n - k} y^{k}$ exactly when $y$ was taken from $k$ of the brackets and $x$ from the rest. So the coefficient of $x^{n - k} y^{k}$ is the number of ways to choose which $k$ of the $n$ brackets supply the $y$ , and that is $(\binom{n}{k})$ .

This is why the numbers are called binomial coefficients. It also explains Pascal's rule again: in $(x + y)^{n} = (x + y) (x + y)^{n - 1}$ , the first bracket supplies either the $y$ or the $x$ of a term $x^{n - k} y^{k}$ , giving $(\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$ . That bracket plays the part of Ada.

Example. Find the coefficient of $x^{2}$ in $(2 x - 3)^{5}$ .

Treat $2 x$ and $- 3$ as the two terms of the binomial. The general term is $(\binom{5}{k}) (2 x)^{5 - k} (- 3)^{k}$ , and it contains $x^{2}$ when $5 - k = 2$ , that is $k = 3$ . The coefficient is $(\binom{5}{3}) \times 2^{2} \times (- 3)^{3} = 10 \times 4 \times (- 27) = - 1080$ . Writing the general term out in full first guards against the two usual slips: leaving the $2$ unpowered and losing the sign.

Now you. Find the coefficient of $x^{5}$ in $(x - 2)^{8}$ .

Answer

The general term is $(\binom{8}{k}) x^{8 - k} (- 2)^{k}$ , and $8 - k = 5$ gives $k = 3$ . The coefficient is $(\binom{8}{3}) \times (- 2)^{3} = 56 \times (- 8) = - 448$ .

The sum of a row

Add up the entries of any row of the triangle: $1 + 4 + 6 + 4 + 1 = 16$ , and $1 + 6 + 15 + 20 + 15 + 6 + 1 = 64$ . The general statement is

\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}

and it has two proofs, one from each side of this lesson. The algebraic one sets $x = y = 1$ in the binomial theorem, so the left side is $2^{n}$ and the right is the sum of the row. The counting one needs no theorem at all. An $n$ element set has $2^{n}$ subsets, since each element is independently in or out, and each subset has some size between $0$ and $n$ . Sorting the subsets by size, there are $(\binom{n}{k})$ of size $k$ , and the sizes do not overlap, so the sum rule adds them up to $2^{n}$ . The row sum is the total number of subsets, counted by size.

Setting $x = 1$ and $y = - 1$ instead gives an alternating sum:

(\binom{n}{0}) - (\binom{n}{1}) + (\binom{n}{2}) - \dots + (- 1)^{n} (\binom{n}{n}) = 0

for $n \geq 1$ , since the left side of the theorem is $0^{n}$ . In counting terms, a nonempty set has exactly as many subsets of even size as of odd size, and a bijection shows it directly. Fix one element, say $a$ . Pair each subset with the subset obtained by toggling $a$ : adding it if absent, removing it if present. Toggling changes the size by one, swapping even with odd, and undoes itself, so the pairing is perfect. For $n = 6$ that is $32$ even subsets and $32$ odd ones.

The chair identity combines with the row sum to give one more. Summing $k (\binom{n}{k})$ over all $k$ counts every committee of every size with a chair; choosing the chair first, in $n$ ways, and then any subset of the other $n - 1$ people to join, gives $n \cdot 2^{n - 1}$ . For $n = 5$ both sides are $80$ .

Vandermonde's identity

A department has $m$ mathematicians and $n$ physicists, and needs a committee of $r$ . Counted directly, there are $(\binom{m + n}{r})$ committees. Counted by how many mathematicians sit on it, a committee with exactly $k$ mathematicians is a choice of $k$ from $m$ and $r - k$ from $n$ , in $(\binom{m}{k}) (\binom{n}{r - k})$ ways, and different values of $k$ do not overlap. So

\sum_{k = 0}^{r} (\binom{m}{k}) (\binom{n}{r - k}) = (\binom{m + n}{r})

which is Vandermonde's identity, named after Alexandre-Théophile Vandermonde, who published it in 1772. Zhu Shijie had stated it in China in 1303. The convention that $(\binom{n}{k}) = 0$ outside $0 \leq k \leq n$ quietly handles the cases where $k$ exceeds $m$ or $r - k$ exceeds $n$ .

The binomial theorem gives a second proof, which is worth seeing because it is the model for a technique of a later lesson. Since $(1 + x)^{m} (1 + x)^{n} = (1 + x)^{m + n}$ , the coefficients of $x^{r}$ on the two sides must agree. On the right it is $(\binom{m + n}{r})$ . On the left, an $x^{r}$ arises by taking $x^{k}$ from the first factor, with coefficient $(\binom{m}{k})$ , and $x^{r - k}$ from the second, with coefficient $(\binom{n}{r - k})$ , summed over $k$ . The two proofs are the same argument: the first factor is the mathematicians.

Example. A panel of four is chosen from five chemists and six biologists. Count the panels by the number of chemists on them, and check the total against Vandermonde.

With $k$ chemists the count is $(\binom{5}{k}) (\binom{6}{4 - k})$ . For $k = 0$ to $4$ that gives $1 \times 15 = 15$ , then $5 \times 20 = 100$ , then $10 \times 15 = 150$ , then $10 \times 6 = 60$ , then $5 \times 1 = 5$ . The sum is $330$ , and $(\binom{11}{4}) = 330$ , the number of ways to pick four from all eleven.

Now you. Use Vandermonde's identity to show that $\sum_{k = 0}^{n} {(\binom{n}{k})}^{2} = (\binom{2 n}{n})$ , and check it for $n = 5$ .

Answer

Take $m = n$ and $r = n$ , so the identity reads $\sum_{k} (\binom{n}{k}) (\binom{n}{n - k}) = (\binom{2 n}{n})$ , and symmetry replaces $(\binom{n}{n - k})$ by $(\binom{n}{k})$ . For $n = 5$ the squares of the row are $1, 25, 100, 100, 25, 1$ , which sum to $252$ , and $(\binom{10}{5}) = 252$ .

The identity has a picture in lattice paths, routes of unit steps right and up: an $n$ by $n$ grid has $(\binom{2 n}{n})$ corner to corner paths, and sorting them by where they cross the diagonal from top left to bottom right gives $n + 1$ groups of sizes ${(\binom{n}{k})}^{2}$ .

The hockey stick

Run down a diagonal of the triangle and add: $1 + 3 + 6 + 10 + 15 = 35$ , and $35$ sits in the next row, just below and to one side of the last entry, so that the numbers summed and the answer trace the shape of a hockey stick. In symbols, for $r \leq n$ ,

\sum_{i = r}^{n} (\binom{i}{r}) = (\binom{n + 1}{r + 1})

and the example is $r = 2$ , $n = 6$ , with $(\binom{7}{3}) = 35$ .

To prove it, count the $(r + 1)$ element subsets of ${1, 2, \dots, n + 1}$ , which number $(\binom{n + 1}{r + 1})$ directly. Sort them instead by their largest element. If the largest element is $i + 1$ , the other $r$ elements are chosen freely from ${1, \dots, i}$ , in $(\binom{i}{r})$ ways, and the largest element can be anything from $r + 1$ up to $n + 1$ . Summing over it gives the left side. A second proof applies Pascal's rule to $(\binom{n + 1}{r + 1})$ , splits off $(\binom{n}{r})$ , applies it again to what remains, and keeps going; the chain unrolls into the diagonal.

With $r = 1$ the identity is the familiar $1 + 2 + \dots + n = (\binom{n + 1}{2}) = \frac{n (n + 1)}{2}$ . With $r = 2$ it adds up the triangular numbers, and it answers a question every December. In the song The Twelve Days of Christmas, the gifts on day $d$ number $1 + 2 + \dots + d = (\binom{d + 1}{2})$ , so the whole song delivers $\sum_{d = 1}^{12} (\binom{d + 1}{2}) = (\binom{14}{3}) = 364$ gifts, one for nearly every day of the year. The same sum says that a triangular pyramid of cannonballs ten layers high holds $(\binom{12}{3}) = 220$ balls.

Where the method stops

Look back at what every proof here did. Pascal's rule split committees into those with Ada and those without. The row sum split subsets by size, Vandermonde split committees by the number of mathematicians, and the hockey stick split subsets by their largest element. Each time the set was cut into pieces that did not overlap, and the sum rule added the pieces.

Many natural questions refuse to split cleanly. How many integers from $1$ to $100$ are divisible by $2$ or by $3$ ? There are $50$ multiples of $2$ and $33$ of $3$ , but adding them counts every multiple of $6$ twice, and the honest answer is $50 + 33 - 16 = 67$ . With three or four overlapping conditions the corrections pile up, and guessing them stops being safe. The next lesson turns that correction into an exact formula, inclusion and exclusion, and proves it by the method of this one: counting how many times each element is included.

Inclusion and exclusion

When the sets being counted overlap, adding their sizes counts some elements more than once, and the question is how to correct the total exactly.

The sum rule adds the sizes of sets that do not overlap, and the previous lesson ended where it fails: of the integers from $1$ to $100$ , fifty are divisible by $2$ and thirty-three by $3$ , but $50 + 33 = 83$ is too many, because the multiples of $6$ are in both lists. This lesson builds the exact correction for any number of sets and spends it on three problems that are hard to attack any other way. It assumes the language of sets and the binomial coefficient $(\binom{n}{k})$ , the number of $k$ element subsets of an $n$ element set.

Two overlapping sets

Write $| A |$ for the number of elements of a finite set $A$ . The sum $| A | + | B |$ counts every element of $A \cup B$ , but it counts the elements of $A \cap B$ twice, once in $A$ and once in $B$ . Subtracting $| A \cap B |$ removes the second copy and nothing else:

| A \cup B | = | A | + | B | - | A \cap B |

Check this element by element, because that check is the proof that generalises. An element in $A$ only contributes $1$ to the right side, through $| A |$ ; one in $B$ only contributes $1$ through $| B |$ ; one in both contributes $1 + 1 - 1 = 1$ ; one in neither contributes nothing. Each element of the union is counted once.

For the question left open, let $A$ be the multiples of $2$ up to $100$ and $B$ the multiples of $3$ . An integer is in both exactly when it is divisible by $6$ , and there are $⌊ 100 / 6 ⌋ = 16$ of those, where $⌊ x ⌋$ means $x$ rounded down. So $| A \cup B | = 50 + 33 - 16 = 67$ , and $33$ integers are divisible by neither, which is often the count actually wanted.

The integers from 1 to 100, with A the 50 multiples of 2 and B the 33 multiples of 3. The overlap holds the 16 multiples of 6, leaving 34 in A only and 17 in B only, so the union has 34 + 16 + 17 = 67 elements and 33 integers lie outside both.

The one step needing thought was the intersection. For divisors sharing a factor it is the multiples of the least common multiple: divisible by both $4$ and $6$ means divisible by $12$ , not $24$ .

Three sets

With three sets, start from $| A | + | B | + | C |$ and subtract the three pairwise intersections, since elements in two sets were counted twice. An element in all three sets, though, was counted three times and then subtracted three times, once for each pair, so it is now counted $3 - 3 = 0$ times and has to be put back:

| A \cup B \cup C | = | A | + | B | + | C | - | A \cap B | - | A \cap C | - | B \cap C | + | A \cap B \cap C |

Element by element: one in exactly one set is counted once; one in exactly two, say $A$ and $B$ , is counted by $| A |$ and $| B |$ and subtracted by $| A \cap B |$ alone, a net $2 - 1 = 1$ ; one in all three is counted $3 - 3 + 1 = 1$ time. The numbers being added and subtracted, $1$ ; $2, 1$ ; $3, 3, 1$ , are rows of Pascal's triangle, which is the clue to the general case.

Example. How many integers from $1$ to $1000$ are divisible by at least one of $2$ , $3$ and $5$ ?

Let $A$ , $B$ and $C$ be the multiples of $2$ , $3$ and $5$ . The singles are $500$ , $⌊ 1000 / 3 ⌋ = 333$ and $200$ , totalling $1033$ . The pairs are the multiples of $6$ , $10$ and $15$ , numbering $166$ , $100$ and $66$ , totalling $332$ . The triple is the $33$ multiples of $30$ . So the union has $1033 - 332 + 33 = 734$ elements, and $266$ integers up to $1000$ are divisible by none of the three. Testing each integer by computer gives the same $734$ .

Now you. How many integers from $1$ to $600$ are divisible by at least one of $4$ , $6$ and $10$ ?

Answer

The singles are $150$ , $100$ and $60$ . The pairwise intersections are the multiples of the least common multiples $12$ , $20$ and $30$ , numbering $50$ , $30$ and $20$ , and the triple is the $10$ multiples of $60$ . The count is $310 - 100 + 10 = 220$ . Using products ( $24$ , $40$ , $60$ and $240$ ) instead would give a wrong answer.

The general formula

Take finite sets $A_{1}, A_{2}, \dots, A_{n}$ . For each $k$ from $1$ to $n$ , let $S_{k}$ be the result of choosing $k$ of the sets in every possible way, intersecting each choice, and adding up the sizes of those $(\binom{n}{k})$ intersections. So $S_{1}$ is $| A_{1} | + \dots + | A_{n} |$ , $S_{2}$ adds the sizes of all pairwise intersections, and $S_{n}$ is the size of the intersection of all $n$ sets. The principle of inclusion and exclusion says

| A_{1} \cup A_{2} \cup \dots \cup A_{n} | = S_{1} - S_{2} + S_{3} - \dots + (- 1)^{n - 1} S_{n}

In words: add the sizes of the sets, subtract the pairwise overlaps, add the triple overlaps, and keep alternating.

The proof counts how many times each element is included. Take an element $x$ in exactly $m$ of the sets, with $m \geq 1$ . An intersection of $k$ sets contains $x$ precisely when all $k$ chosen sets are among the $m$ that contain it, and there are $(\binom{m}{k})$ such choices. So $x$ is counted $(\binom{m}{k})$ times in $S_{k}$ (zero times once $k > m$ ), and its net count is

(\binom{m}{1}) - (\binom{m}{2}) + (\binom{m}{3}) - \dots + (- 1)^{m - 1} (\binom{m}{m})

The previous lesson proved that the alternating sum of a row of Pascal's triangle vanishes, $(\binom{m}{0}) - (\binom{m}{1}) + (\binom{m}{2}) - \dots + (- 1)^{m} (\binom{m}{m}) = 0$ for $m \geq 1$ , because a nonempty set has as many subsets of even size as of odd size. The displayed sum is that row with its first term, $(\binom{m}{0}) = 1$ , removed and every sign flipped, so it equals $1$ . Every element of the union is counted exactly once, and one in none of the sets appears in no term.

Usually the sets live inside a universe $U$ of $N$ elements, each $A_{i}$ collecting the elements with some unwanted property, and the question is how many have none of the properties. Subtracting the union from $N$ flips every sign, giving the sieve form used in the rest of the lesson:

| U | - | A_{1} \cup \dots \cup A_{n} | = N - S_{1} + S_{2} - S_{3} + \dots + (- 1)^{n} S_{n}

Abraham de Moivre used the idea in his Doctrine of Chances of 1718. Its cost is that $n$ sets have $2^{n} - 1$ intersections, over a billion for thirty sets, so it is a practical method only when every intersection of $k$ sets has the same size, say $s_{k}$ . Then $S_{k} = (\binom{n}{k}) s_{k}$ and the formula collapses to one sum of $n + 1$ terms, as in each application below.

Onto functions

A function from a set $K$ to a set $T$ is onto if every element of $T$ is assigned to something. If $| K | = k$ and $| T | = n$ , the product rule gives $n^{k}$ functions in all. "Everything is hit" constrains the whole function at once, but its failure splits into simple pieces: the function misses some particular element.

So let $A_{i}$ be the functions that miss the $i$ th element of $T$ . A function missing $j$ given elements sends all of $K$ into the other $n - j$ , which can be done in $(n - j)^{k}$ ways whichever $j$ were chosen. The intersections are uniform, and the number of onto functions is

\sum_{j = 0}^{n} (- 1)^{j} (\binom{n}{j}) (n - j)^{k} = n^{k} - (\binom{n}{1}) (n - 1)^{k} + (\binom{n}{2}) (n - 2)^{k} - \dots

Two quick checks: with $k = 2$ and $n = 3$ nothing is onto, and the formula gives $9 - 12 + 3 - 0 = 0$ ; with $k = n = 3$ onto means bijection, and it gives $27 - 24 + 3 = 6 = 3!$ .

Example. Five different tasks are shared among three people so that everyone gets at least one. In how many ways?

An allocation is a function from tasks to people, and "everyone gets at least one" means onto. The count is $3^{5} - 3 \times 2^{5} + 3 \times 1^{5} - 0 = 243 - 96 + 3 = 150$ .

Now you. Six students are assigned to four different projects, each project needing at least one student. How many assignments are there?

Answer

Count onto functions from students to projects: $4^{6} - 4 \times 3^{6} + 6 \times 2^{6} - 4 \times 1^{6} + 0 = 4096 - 2916 + 384 - 4 = 1560$ .

Derangements and the hat check problem

At a party, $n$ guests leave their hats at the door, and the attendant, having lost the tickets, hands them back at random. What is the chance that nobody gets their own hat? Pierre Rémond de Montmort posed the question in 1708 as a card game called treize.

Handing back the hats is a permutation of the guests, one of $n!$ . A permutation that sends nothing to itself is a derangement, and $D_{n}$ is the number of derangements of $n$ elements. Let $A_{i}$ be the permutations that give guest $i$ their own hat. Fixing $j$ given guests leaves the other $n - j$ hats to be arranged freely, in $(n - j)!$ ways, so $S_{j} = (\binom{n}{j}) (n - j)! = \frac{n!}{j!}$ and the sieve gives

D_{n} = n! (1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(- 1)^{n}}{n!})

Example. Five guests. How many ways are there to return the hats so that nobody gets their own, and what is the probability?

The terms are $120 / j!$ for $j = 0$ to $5$ with alternating signs, so $D_{5} = 120 - 120 + 60 - 20 + 5 - 1 = 44$ , and the probability is $44 / 120 \approx 0.3667$ . Listing all $120$ permutations by computer finds the same $44$ .

Now you. Six guests. What is the probability that exactly two of them get their own hats back?

Answer

Choose the two lucky guests in $(\binom{6}{2}) = 15$ ways; the other four must form a derangement, and $D_{4} = 24 - 24 + 12 - 4 + 1 = 9$ . So $135$ of the $720$ permutations qualify, a probability of $135 / 720 = 0.1875$ .

The probability that nobody gets their own hat is $D_{n} / n!$ , the bracket in the formula, and its values are strange.

$n$	$D_{n}$	$D_{n} / n!$
2	1	0.500000
3	2	0.333333
4	9	0.375000
5	44	0.366667
6	265	0.368056
7	1854	0.367857
8	14833	0.367882
10	1334961	0.367879

The answer barely depends on $n$ : eight guests or a thousand agree to four decimal places. The bracket is the start of the series $e^{x} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!} + \dots$ at $x = - 1$ , so it converges to $1 / e \approx 0.367879$ . It converges fast, because in an alternating series with shrinking terms, stopping early is wrong by less than the first term left out, here $1 / (n + 1)!$ . Multiplying by $n!$ , $D_{n}$ is within $1 / (n + 1)$ of $n! / e$ , so $D_{n}$ is $n! / e$ rounded to the nearest integer: $40320 / e \approx 14832.9$ , and $D_{8} = 14833$ .

Euler's totient

For a positive integer $n$ , Euler's totient $φ (n)$ counts the integers from $1$ to $n$ that share no factor with $n$ except $1$ . So $φ (12) = 4$ , counting $1$ , $5$ , $7$ and $11$ , and $φ (p) = p - 1$ for a prime $p$ . Euler introduced it in 1763, and it drives a later lesson's generalisation of Fermat's little theorem and with it the RSA cryptosystem.

An integer shares a factor greater than $1$ with $n$ exactly when some prime divisor of $n$ divides it. So let $p_{1}, \dots, p_{r}$ be the distinct primes dividing $n$ , and $A_{i}$ the multiples of $p_{i}$ from $1$ to $n$ . A number lies in several of these sets exactly when it is divisible by the product of those primes, and since that product divides $n$ , its multiples up to $n$ number exactly $n$ divided by it. Subtract $n / p$ for each prime, add back $n / (p q)$ for each pair of primes, subtract $n / (p q r)$ for each triple, and so on. The alternating sum factorises:

φ (n) = n (1 - \frac{1}{p_{1}}) (1 - \frac{1}{p_{2}}) \dots (1 - \frac{1}{p_{r}})

To see why, expand the product as the previous lesson expanded $(x + y)^{n}$ , choosing $1$ or $- 1 / p_{i}$ from each bracket. Each set of primes arises once, as the brackets that supplied $- 1 / p_{i}$ , with sign $+$ for an even number of primes and $-$ for an odd number. That is the sieve, term for term.

Take $360 = 2^{3} \times 3^{2} \times 5$ . The sieve reads $360 - (180 + 120 + 72) + (60 + 36 + 24) - 12 = 96$ , and the product reads $360 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 96$ . For $1000 = 2^{3} \times 5^{3}$ , $φ (1000) = 1000 \times \frac{1}{2} \times \frac{4}{5} = 400$ . Only which primes divide $n$ matters, not how often, and a computer check of every number confirms both.

Counts built from smaller counts

The three applications share a shape. Each negated a condition on the whole object (every person busy, nobody with their own hat, no prime shared) into simple failures, one per person, guest or prime, whose intersections depended only on how many failures were demanded. That uniformity is what to look for.

The derangement numbers $1, 2, 9, 44, 265, 1854$ hide something else: $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ , so that $265 = 5 \times (44 + 9)$ . Guest $1$ gets some guest $i$ 's hat, in $n - 1$ ways. If guest $i$ gets hat $1$ back, the other $n - 2$ guests form a derangement, in $D_{n - 2}$ ways. If not, treat hat $1$ as guest $i$ 's forbidden hat, and the $n - 1$ guests other than guest $1$ form a derangement, in $D_{n - 1}$ ways.

That description needs no alternating sum: it defines each count through smaller versions of itself. Such descriptions are recurrences, and the next lesson is about setting them up and solving them.

Recurrences

Some counts have no obvious formula, yet are easy to describe in terms of smaller versions of themselves: the moves needed for ten discs are easy to relate to the moves needed for nine.

The previous lessons counted a set directly, by a product, a binomial coefficient, or the inclusion and exclusion formula that corrects for overlap. This lesson writes the answer for size $n$ in terms of the answers for smaller sizes, which is a recurrence, and then turns the recurrence into a formula by one of two methods: unrolling, or guessing and proving the guess by induction (show the first case, then show that each case implies the next). It ends with a famous recurrence that defeats both.

The Tower of Hanoi

In 1883 Édouard Lucas put a puzzle on sale under the name N. Claus de Siam, an anagram of Lucas d'Amiens. Eight discs of different sizes sit on one of three pegs, largest at the bottom, and the task is to move the tower to another peg one disc at a time, never placing a disc on a smaller one. A legend published with it told of priests moving a tower of sixty-four golden discs, with the world to end when they finished.

Let $T_{n}$ be the fewest moves that transfer $n$ discs. Plainly $T_{0} = 0$ and $T_{1} = 1$ , while $T_{2} = 3$ : the small disc steps aside, the large one moves, the small one returns. For the general case, watch the largest disc. It can only move when all $n - 1$ others are stacked on the third peg, out of its way. So one solution moves the top $n - 1$ discs to the spare peg, moves the largest disc, then moves the $n - 1$ discs back on top of it. Sitting at the bottom, the largest disc never obstructs those smaller towers, so this uses $2 T_{n - 1} + 1$ moves.

That is only an upper bound, so it remains to show nothing shorter exists. The largest disc must move at least once. Before its first move, the other $n - 1$ discs must be gathered into one stack on another peg, which takes at least $T_{n - 1}$ moves, and after its last move they must all be brought back on top of it, at least $T_{n - 1}$ more. So every solution uses at least $2 T_{n - 1} + 1$ moves, and

T_{n} = 2 T_{n - 1} + 1 for n \geq 1, T_{0} = 0

The rule produces $1, 3, 7, 15, 31$ , and Lucas's eight discs need $T_{8} = 255$ moves. The rule alone is not enough: $a_{n} = 2 a_{n - 1} + 1$ with $a_{0} = 5$ is a different sequence. A recurrence comes with initial conditions, as many as the number of earlier terms each step looks back to.

Unrolling

The values $1, 3, 7, 15, 31, 255$ are each one less than a power of two. To prove it, substitute the recurrence into itself:

T_{n} = 2 T_{n - 1} + 1 = 4 T_{n - 2} + 2 + 1 = 8 T_{n - 3} + 4 + 2 + 1

After $k$ steps, $T_{n} = 2^{k} T_{n - k} + 2^{k - 1} + \dots + 2 + 1$ . At $k = n$ the initial condition $T_{0} = 0$ appears, and the geometric series left behind sums to

T_{n} = 2^{n} - 1

This is unrolling: expand until the initial condition appears, then add up what has accumulated. It works when each term depends on one earlier term and the leftover sum can be evaluated. The priests' tower needs $2^{64} - 1 = 18 446 744 073 709 551 615$ moves, which at one a second takes about $585$ billion years, over forty times the present age of the universe.

Example. In a stricter version the pegs stand in a row and a disc may only move to a neighbouring peg. How many moves does the natural strategy use to carry $n$ discs from one end peg to the other?

Call it $a_{n}$ . The largest disc must go left to middle, then middle to right, and each time the other $n - 1$ discs must be on the peg it is not using. So move them left to right ( $a_{n - 1}$ moves), the largest disc to the middle ( $1$ ), the others right to left ( $a_{n - 1}$ ), the largest to the right ( $1$ ), and the others left to right ( $a_{n - 1}$ ). That is $a_{n} = 3 a_{n - 1} + 2$ with $a_{0} = 0$ . Unrolling gives $a_{n} = 3^{k} a_{n - k} + 2 (3^{k - 1} + \dots + 1)$ , and at $k = n$ the series sums to $\frac{3^{n} - 1}{2}$ , so $a_{n} = 3^{n} - 1$ . Three discs need $26$ moves instead of $7$ , and a computer search confirms nothing shorter exists.

Now you. A double tower has two identical discs of each of $n$ sizes, and a disc may rest on one of equal size. Set up a recurrence for the fewest moves $H_{n}$ that carry it to another peg, unroll it, and find $H_{5}$ .

Answer

The argument runs as before with the bottom pair in place of the largest disc: move the top $n - 1$ pairs aside, move the two largest discs, bring the pairs back. So $H_{n} = 2 H_{n - 1} + 2$ with $H_{0} = 0$ , which unrolls to $H_{n} = 2 (2^{n - 1} + \dots + 1) = 2^{n + 1} - 2$ , twice the single tower. So $H_{5} = 62$ .

Bit strings with no two consecutive 1s

How many bit strings of length $n$ have no two 1s side by side? For length $3$ , five of the eight qualify: $000$ , $001$ , $010$ , $100$ and $101$ . No product rule applies, because whether a bit may be $1$ depends on its neighbour.

Let $b_{n}$ count the good strings of length $n$ , and sort them by their last bit. A good string ending in $0$ is any good string of length $n - 1$ with a $0$ added, since a final $0$ cannot create a forbidden pair: $b_{n - 1}$ of those. A good string ending in $1$ has a $0$ just before it, so it is a good string of length $n - 2$ followed by $01$ : $b_{n - 2}$ of those. By the sum rule,

b_{n} = b_{n - 1} + b_{n - 2} for n \geq 2

Each step looks back two terms, so two initial conditions are needed: the empty string is good, so $b_{0} = 1$ , and both strings of length $1$ are good, so $b_{1} = 2$ . The recurrence then gives $3, 5, 8, 13, 21, 34, 55, 89, 144$ , so $b_{10} = 144$ , as a computer check of all $1024$ strings confirms.

These are the Fibonacci numbers, here defined by $F_{0} = 0$ , $F_{1} = 1$ and $F_{n} = F_{n - 1} + F_{n - 2}$ , so the sequence runs $0, 1, 1, 2, 3, 5, 8, \dots$ . The indexing matters because books differ, some starting from $1, 2$ . With this one, $b_{n}$ and $F_{n + 2}$ obey the same recurrence and agree at $n = 0$ and $n = 1$ , since $b_{0} = 1 = F_{2}$ and $b_{1} = 2 = F_{3}$ , so they agree forever: $b_{n} = F_{n + 2}$ . The name is that of Leonardo of Pisa, whose Liber Abaci of 1202 counted breeding rabbits and found $377$ pairs after a year, though Hemachandra had met the same numbers around 1150, counting rhythms in Sanskrit verse built from syllables of one beat and two.

Example. How many strings of length $5$ over ${a, b, c}$ have no two consecutive $a$ s?

Let $t_{n}$ count them and sort by the last letter. If it is $b$ or $c$ , the rest is any good string of length $n - 1$ , giving $2 t_{n - 1}$ . If it is $a$ , the letter before is $b$ or $c$ , preceded by any good string of length $n - 2$ , giving $2 t_{n - 2}$ . So $t_{n} = 2 t_{n - 1} + 2 t_{n - 2}$ with $t_{0} = 1$ and $t_{1} = 3$ . Then $t_{2} = 8$ , which is all nine pairs except $a a$ , followed by $t_{3} = 22$ , $t_{4} = 60$ and $t_{5} = 164$ .

Now you. How many bit strings of length $7$ contain no three consecutive 1s?

Answer

A good string ends in $0$ , $01$ or $011$ , preceded by a good string of length $n - 1$ , $n - 2$ or $n - 3$ . So $c_{n} = c_{n - 1} + c_{n - 2} + c_{n - 3}$ with $c_{0} = 1$ , $c_{1} = 2$ , $c_{2} = 4$ , and the sequence continues $7, 13, 24, 44, 81$ . So $c_{7} = 81$ .

Regions cut by lines

Into how many regions can $n$ straight lines cut the plane? The most comes when the lines are in general position: no two parallel and no three through one point. Jakob Steiner answered the question in 1826; it also counts the pieces a large pizza yields to $n$ straight cuts.

Let $R_{n}$ be the number of regions. No lines leave the whole plane, so $R_{0} = 1$ ; one line makes two regions, two crossing lines make four, and three make seven, a triangle with three regions on its sides and three at its corners.

Add the lines one at a time. The $n$ th line crosses each of the $n - 1$ earlier lines once, since none is parallel to it, at $n - 1$ distinct points, since no three lines meet. Those points cut it into $n$ pieces, two rays and $n - 2$ segments, and each piece crosses one old region from side to side and splits it in two. So

R_{n} = R_{n - 1} + n for n \geq 1, R_{0} = 1

and the values run $1, 2, 4, 7, 11, 16, 22$ . Both assumptions were used: a line parallel to an old one would add only $n - 1$ regions, and one through an existing crossing would be cut into fewer pieces. That is why general position gives the maximum.

Guessing and proving

This recurrence unrolls to $1 + (1 + 2 + \dots + n)$ , but there is a second method, useful whenever unrolling leaves a sum you cannot evaluate: compute some values, guess a formula, and prove it by induction.

The values $1, 2, 4, 7, 11, 16, 22$ have differences $1, 2, 3, 4, 5, 6$ , whose own differences are constant. Constant second differences mark a quadratic, so try $R_{n} = A n^{2} + B n + C$ . From $R_{0} = 1$ , $C = 1$ ; from $R_{1} = 2$ , $A + B = 1$ ; from $R_{2} = 4$ , $4 A + 2 B = 3$ . So $A = B = \frac{1}{2}$ , and the guess is

R_{n} = \frac{n (n + 1)}{2} + 1

A formula fitted to three values proves nothing, but induction does. It holds at $n = 0$ . If $R_{n - 1} = \frac{(n - 1) n}{2} + 1$ , the recurrence gives $R_{n} = \frac{n^{2} - n + 2 n}{2} + 1 = \frac{n (n + 1)}{2} + 1$ , the formula for $n$ . So ten cuts divide a pizza into at most $56$ pieces, and a hundred lines cut the plane into $5051$ regions. The induction step is one line of algebra; the hard part is the guess.

Example. Draw $n$ circles so that every two cross at two points and no three pass through one point. Find the number of regions $C_{n}$ .

One circle makes $2$ regions. The $n$ th circle crosses each of the $n - 1$ others twice, at $2 (n - 1)$ distinct points, which cut it into $2 (n - 1)$ arcs when $n \geq 2$ , and each arc splits an old region in two. So $C_{n} = C_{n - 1} + 2 (n - 1)$ with $C_{1} = 2$ , giving $2, 4, 8, 14, 22$ . The second differences are constant, and fitting a quadratic to $n = 1, 2, 3$ gives the guess $C_{n} = n^{2} - n + 2$ . It holds at $n = 1$ , and if $C_{n - 1} = (n - 1)^{2} - (n - 1) + 2 = n^{2} - 3 n + 4$ , then $C_{n} = n^{2} - 3 n + 4 + 2 n - 2 = n^{2} - n + 2$ . The formula fails at $n = 0$ , giving $2$ for an empty plane, so the base case matters. It also shows why Venn diagrams stop at three circles: four circles make only $14$ regions, short of the $2^{4} = 16$ that four sets need.

Now you. The $n$ lines of a general position arrangement are themselves cut into pieces, segments and rays, by their crossing points. Let $s_{n}$ be the total number of pieces. Set up a recurrence, guess a closed form and prove it.

Answer

The $n$ th line is cut into $n$ pieces, and it splits one piece of each of the $n - 1$ old lines in two. So $s_{n} = s_{n - 1} + n + (n - 1) = s_{n - 1} + 2 n - 1$ with $s_{1} = 1$ . The values $1, 4, 9, 16$ suggest $s_{n} = n^{2}$ , and indeed $(n - 1)^{2} + 2 n - 1 = n^{2}$ . It can also be seen directly: each of the $n$ lines is cut into $n$ pieces.

Where both methods stall

Turn both methods on the bit string recurrence, $F_{n} = F_{n - 1} + F_{n - 2}$ . Unrolling replaces the largest index each time:

F_{n} = F_{n - 1} + F_{n - 2} = 2 F_{n - 2} + F_{n - 3} = 3 F_{n - 3} + 2 F_{n - 4} = 5 F_{n - 4} + 3 F_{n - 5}

The coefficients $1, 2, 3, 5$ are Fibonacci numbers again, and in general $F_{n} = F_{k + 1} F_{n - k} + F_{k} F_{n - k - 1}$ . That is a true identity, but as a solution it goes in a circle: reaching the initial conditions means carrying coefficients that are the very numbers being sought. Each substitution replaces one unknown by two, and what accumulates is a copy of the original problem.

Guessing fares no better. The differences of $0, 1, 1, 2, 3, 5, 8, 13$ are $1, 0, 1, 1, 2, 3, 5$ , the same sequence shifted, so they never settle and no polynomial fits. The growth looks exponential: consecutive ratios run $\frac{8}{5} = 1.6$ , $\frac{13}{8} = 1.625$ , $\frac{21}{13} \approx 1.615$ and $\frac{144}{89} \approx 1.618$ . But ${1.618}^{n}$ is not an integer, so the exact answer is subtler than a single power, and nothing in a table of integers suggests what it is.

The ratio is the clue. If a sequence growing like $r^{n}$ is to obey $F_{n} = F_{n - 1} + F_{n - 2}$ , substituting $r^{n}$ forces a condition on $r$ with two solutions, not one. The next lesson follows that clue to the characteristic equation, which solves every recurrence of this shape, and gives the Fibonacci numbers an exact formula in which $\sqrt{5}$ appears and then cancels to leave an integer every time.

Linear recurrences

Fibonacci's recurrence $F_{n} = F_{n - 1} + F_{n - 2}$ is easy to run and hard to solve: unrolling it doubles the work at every step, and its values suggest no formula to guess.

The previous lesson set up recurrences, rules that give each term of a sequence from earlier ones, and solved the simple ones by unrolling, or by guessing a formula and proving it by induction. Both methods stalled on the Fibonacci numbers $0, 1, 1, 2, 3, 5, 8, 13, \dots$ , which also count the bit strings with no two consecutive 1s, and left one clue: the ratio of consecutive terms settles near $1.618$ , as if the sequence grew like a power. This lesson follows the clue to a method that solves every recurrence of that shape, then extends it to recurrences with an extra term, the Tower of Hanoi's among them.

Trying a power

A recurrence is linear with constant coefficients if each term is a fixed combination of the $k$ terms before it, $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k}$ , where the numbers $c_{i}$ do not depend on $n$ . The number $k$ is the order, and it is also how many initial conditions are needed. It is homogeneous, meaning nothing is added beyond the combination; a later section adds something.

Geometric sequences reproduce themselves under a shift: $r^{n}$ shifted back by one is $r^{n - 1}$ , the same sequence divided by $r$ . So try $a_{n} = r^{n}$ with $r \neq 0$ in the order $2$ recurrence $a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2}$ . It needs $r^{n} = c_{1} r^{n - 1} + c_{2} r^{n - 2}$ for every $n$ , and dividing by $r^{n - 2}$ removes $n$ altogether:

r^{2} = c_{1} r + c_{2}

This is the characteristic equation. For order $k$ it reads $r^{k} = c_{1} r^{k - 1} + \dots + c_{k}$ , and each root gives a solution $r^{n}$ , though not yet one that meets the initial conditions.

For $a_{n} = 5 a_{n - 1} - 6 a_{n - 2}$ the equation is $r^{2} - 5 r + 6 = (r - 2) (r - 3) = 0$ , so $2^{n}$ and $3^{n}$ both satisfy the recurrence. Check one: $5 \times 3^{n - 1} - 6 \times 3^{n - 2} = 3^{n - 2} (15 - 6) = 3^{n}$ .

Two roots, two constants

The recurrence is linear, and that supplies the second ingredient. If $x_{n}$ and $y_{n}$ both satisfy it, so does $A x_{n} + B y_{n}$ for any constants $A$ and $B$ : multiply the equation for $x_{n}$ by $A$ , the one for $y_{n}$ by $B$ , and add. So when the characteristic equation has distinct roots $r_{1}$ and $r_{2}$ , every sequence

a_{n} = A r_{1}^{n} + B r_{2}^{n}

satisfies the recurrence, and the constants are free to meet the initial conditions. Setting $n = 0$ and $n = 1$ gives $A + B = a_{0}$ and $A r_{1} + B r_{2} = a_{1}$ . Subtracting $r_{1}$ times the first from the second leaves $B (r_{2} - r_{1}) = a_{1} - r_{1} a_{0}$ , solvable precisely because $r_{1} \neq r_{2}$ , and then $A = a_{0} - B$ .

That settles every such recurrence, not just some. The fitted formula and the true sequence agree at $n = 0$ and $n = 1$ , and both compute each term from the two before it by the same rule, so by induction they agree forever. The formula is the solution, and the characteristic equation has missed nothing. Always check a fitted formula against the first few terms, since that catches almost every slip in the fit.

Example. A path $1$ unit wide and $n$ units long is paved with square tiles in $2$ colours and dominoes, $1$ by $2$ , in $3$ colours. Find a formula for the number of pavings, and the number for length $6$ .

Sort the pavings by the last tile. A square, in $2$ colours, leaves any paving of length $n - 1$ ; a domino, in $3$ colours, leaves any paving of length $n - 2$ . So $a_{n} = 2 a_{n - 1} + 3 a_{n - 2}$ , with $a_{0} = 1$ (the empty path has one paving) and $a_{1} = 2$ . The characteristic equation $r^{2} - 2 r - 3 = (r - 3) (r + 1) = 0$ has roots $3$ and $- 1$ , so $a_{n} = A \times 3^{n} + B (- 1)^{n}$ . The conditions $A + B = 1$ and $3 A - B = 2$ give $A = \frac{3}{4}$ and $B = \frac{1}{4}$ :

a_{n} = \frac{3^{n + 1} + (- 1)^{n}}{4}

Check: the recurrence gives $a_{2} = 4 + 3 = 7$ and $a_{3} = 14 + 6 = 20$ , and the formula gives $\frac{27 + 1}{4} = 7$ and $\frac{81 - 1}{4} = 20$ . So $a_{6} = \frac{2187 + 1}{4} = 547$ . Fractional constants are normal: the recurrence guarantees integers.

Now you. Solve $a_{n} = a_{n - 1} + 6 a_{n - 2}$ with $a_{0} = 3$ and $a_{1} = 4$ , check against $a_{2}$ and $a_{3}$ , and find $a_{10}$ .

Answer

The equation $r^{2} - r - 6 = (r - 3) (r + 2) = 0$ has roots $3$ and $- 2$ . Then $A + B = 3$ and $3 A - 2 B = 4$ give $A = 2$ , $B = 1$ , so $a_{n} = 2 \times 3^{n} + (- 2)^{n}$ . The recurrence gives $a_{2} = 22$ and $a_{3} = 46$ ; the formula gives $18 + 4$ and $54 - 8$ . So $a_{10} = 2 \times 59 049 + 1024 = 119 122$ .

Binet's formula

For $F_{n} = F_{n - 1} + F_{n - 2}$ the characteristic equation is $r^{2} = r + 1$ , with roots

φ = \frac{1 + \sqrt{5}}{2} \approx 1.618, ψ = \frac{1 - \sqrt{5}}{2} \approx - 0.618

The first is the golden ratio, the $1.618$ the ratios were approaching (the letter has nothing to do with the totient of an earlier lesson). Their difference is $φ - ψ = \sqrt{5}$ .

The roots are distinct, so $F_{n} = A φ^{n} + B ψ^{n}$ . The condition $F_{0} = 0$ gives $B = - A$ , and then $F_{1} = 1$ gives $A (φ - ψ) = 1$ , so $A = \frac{1}{\sqrt{5}}$ . Therefore

F_{n} = \frac{φ^{n} - ψ^{n}}{\sqrt{5}}

This is Binet's formula, published by Jacques Binet in 1843, though Abraham de Moivre and Daniel Bernoulli had it more than a century before. A formula full of $\sqrt{5}$ that returns an integer for every $n$ looks miraculous, but expanding $(1 + \sqrt{5})^{n}$ and $(1 - \sqrt{5})^{n}$ by the binomial theorem shows why: the terms with even powers of $\sqrt{5}$ cancel in the difference, and each survivor carries exactly one $\sqrt{5}$ to cancel the denominator.

The formula also finishes a count from the previous lesson. Bit strings of length $n$ with no two consecutive 1s number $F_{n + 2}$ , so length $20$ has $F_{22} = 17 711$ of them among $1 048 576$ strings, and each extra bit multiplies the count by about $1.618$ , where unrestricted strings double.

The nearest integer

Since $| ψ | < 1$ , the powers $ψ^{n}$ shrink towards zero, alternating in sign: $ψ^{10} \approx 0.008$ . So the second term of Binet's formula, $\frac{ψ^{n}}{\sqrt{5}}$ , has size at most $\frac{1}{\sqrt{5}} \approx 0.447$ for every $n \geq 0$ , which is less than $\frac{1}{2}$ . The number $\frac{φ^{n}}{\sqrt{5}}$ is therefore within a half of the integer $F_{n}$ :

F_{n} is the nearest integer to \frac{φ^{n}}{\sqrt{5}}

This holds even at $n = 0$ , where $0.447$ rounds to $0$ , and the approximation tightens fast: $\frac{φ^{10}}{\sqrt{5}} \approx 55.0036$ against $F_{10} = 55$ , and $\frac{φ^{30}}{\sqrt{5}} \approx 832 040.0000002$ against $F_{30} = 832 040$ . It is the same shape as the derangement count of an earlier lesson, an exact count equal to a simple expression rounded, and for the same reason: an error term known to be below a half.

The fading term also explains the ratios. In $F_{n + 1} / F_{n}$ the $ψ$ terms vanish in the limit, so the ratio tends to $φ$ , overshooting and undershooting in turn as $ψ^{n}$ changes sign: $\frac{89}{55} \approx 1.61818$ , then $\frac{144}{89} \approx 1.61798$ . In any order $2$ recurrence with distinct real roots, the root of larger size sets the growth and the other only decides the rounding.

A repeated root

The fit needed $r_{1} \neq r_{2}$ . The recurrence $a_{n} = 6 a_{n - 1} - 9 a_{n - 2}$ has characteristic equation $(r - 3)^{2} = 0$ and the single root $3$ , so $A \times 3^{n}$ is the only family on offer, and one constant cannot meet two initial conditions. A second solution is missing.

Nearby recurrences show where it hides. With distinct roots $r$ and $s$ , linearity makes $\frac{s^{n} - r^{n}}{s - r}$ a solution. As $s$ approaches $r$ the recurrence approaches the one with a double root, and this solution approaches the derivative of $x^{n}$ at $r$ , which is $n r^{n - 1}$ . Dividing by the constant $r$ gives the candidate $n r^{n}$ : the old solution with an extra factor $n$ .

The limit only suggests it, so check. A double root means $x^{2} - c_{1} x - c_{2} = (x - r)^{2}$ , so $c_{1} = 2 r$ and $c_{2} = - r^{2}$ , and then

c_{1} (n - 1) r^{n - 1} + c_{2} (n - 2) r^{n - 2} = r^{n} (2 n - 2 - n + 2) = n r^{n}

So the general solution is $a_{n} = (A + B n) r^{n}$ , fitted by $A = a_{0}$ and $(A + B) r = a_{1}$ , and the induction argument shows it is every solution. At higher orders a root of multiplicity $m$ contributes $r^{n}, n r^{n}, \dots, n^{m - 1} r^{n}$ .

Example. Solve $a_{n} = 6 a_{n - 1} - 9 a_{n - 2}$ with $a_{0} = 1$ and $a_{1} = 6$ .

The double root is $3$ , so $a_{n} = (A + B n) 3^{n}$ . From $a_{0} = 1$ , $A = 1$ ; from $a_{1} = 6$ , $3 (1 + B) = 6$ , so $B = 1$ and $a_{n} = (n + 1) 3^{n}$ . The recurrence gives $a_{2} = 36 - 9 = 27$ and $a_{3} = 162 - 54 = 108$ , and the formula gives $3 \times 9 = 27$ and $4 \times 27 = 108$ .

Now you. Solve $a_{n} = 10 a_{n - 1} - 25 a_{n - 2}$ with $a_{0} = 2$ and $a_{1} = 15$ , and find $a_{6}$ .

Answer

The equation $r^{2} - 10 r + 25 = (r - 5)^{2}$ has the double root $5$ , so $a_{n} = (A + B n) 5^{n}$ with $A = 2$ and $5 (2 + B) = 15$ , so $B = 1$ and $a_{n} = (n + 2) 5^{n}$ . Check: the recurrence gives $a_{2} = 150 - 50 = 100 = 4 \times 25$ . So $a_{6} = 8 \times 15 625 = 125 000$ .

Adding a forcing term

The Tower of Hanoi recurrence $T_{n} = 2 T_{n - 1} + 1$ , the fewest moves for $n$ discs, is not homogeneous: the $+ 1$ is a forcing term, added whatever the earlier terms are. In general $a_{n} = c_{1} a_{n - 1} + \dots + c_{k} a_{n - k} + f (n)$ , and linearity still does the work. If $p_{n}$ is one solution, a particular solution, and $a_{n}$ is any other, subtracting their recurrences cancels $f (n)$ , so $a_{n} - p_{n}$ solves the homogeneous recurrence. Every solution is therefore $p_{n}$ plus the general homogeneous solution, with the constants fitted last, to the whole formula.

A particular solution is guessed from the shape of the forcing term, with unknown coefficients: a constant for a constant, a polynomial of degree $d$ for a polynomial of degree $d$ . For Hanoi, $p = 2 p + 1$ gives $p = - 1$ , the homogeneous part has root $2$ , so $T_{n} = A \times 2^{n} - 1$ , and $T_{0} = 0$ gives $A = 1$ . That is $T_{n} = 2^{n} - 1$ , as unrolling found, with no series to sum.

Example. A procedure given an input of size $n$ does $n$ steps of work and then calls itself twice on size $n - 1$ ; size $0$ costs nothing. Find the total work $a_{n}$ .

The recurrence is $a_{n} = 2 a_{n - 1} + n$ with $a_{0} = 0$ . The forcing term has degree $1$ , so try $p_{n} = α n + β$ . Substituting, $α n + β = 2 α (n - 1) + 2 β + n$ , and matching coefficients gives $α = 2 α + 1$ and $β = 2 β - 2 α$ , so $α = - 1$ and $β = - 2$ . Then $a_{n} = A \times 2^{n} - n - 2$ , and $a_{0} = 0$ gives $A = 2$ :

a_{n} = 2^{n + 1} - n - 2

Check: the recurrence gives $1, 4, 11$ for $n = 1, 2, 3$ , and the formula gives $4 - 3$ , $8 - 4$ and $16 - 5$ . At size $10$ the work is $2036$ steps.

Now you. Solve $a_{n} = a_{n - 1} + 2 a_{n - 2} + 4$ with $a_{0} = a_{1} = 1$ , and find $a_{10}$ .

Answer

A constant $p$ needs $p = 3 p + 4$ , so $p = - 2$ . The roots of $r^{2} - r - 2 = 0$ are $2$ and $- 1$ , so $a_{n} = A \times 2^{n} + B (- 1)^{n} - 2$ . The conditions give $A + B = 3$ and $2 A - B = 3$ , so $A = 2$ , $B = 1$ and $a_{n} = 2^{n + 1} + (- 1)^{n} - 2$ . Check: the recurrence gives $a_{2} = 7$ and $a_{3} = 13$ , as does the formula. So $a_{10} = 2048 + 1 - 2 = 2047$ .

The guess fails in one case, for the reason the double root did. The regions cut by $n$ lines in general position satisfy $R_{n} = R_{n - 1} + n$ , whose homogeneous part has root $1$ , so constants already solve it and $α n + β$ cannot produce the $+ n$ . Multiply the guess by $n$ , as with a repeated root: $p_{n} = n (α n + β)$ gives $2 α n - α + β = n$ , so $α = β = \frac{1}{2}$ and $R_{n} = 1 + \frac{n (n + 1)}{2}$ , the formula the previous lesson reached by guessing.

How far the method reaches

At any order the steps are the same: find the $k$ roots of the characteristic equation, write one term per root (with extra factors of $n$ for a repeated one), add a particular solution if there is a forcing term, and fit $k$ initial conditions. Bit strings with no three consecutive 1s obey $c_{n} = c_{n - 1} + c_{n - 2} + c_{n - 3}$ , whose cubic has one real root near $1.839$ and two complex ones of size below $1$ , so those counts grow like ${1.839}^{n}$ . Complex roots need no new idea; the answer comes out real.

The method needs both halves of its name. The derangement recurrence $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ has a coefficient that grows with $n$ , and trying $r^{n}$ leaves $n$ in the equation. The Catalan numbers, which count the ways to bracket a product, obey a recurrence in which terms multiply each other, so superposition fails. A tool that turned the counting argument itself into algebra would reach further, and the next lesson builds one: the generating function.

Generating functions

A counting problem usually asks for a whole sequence of answers, one for each size, and it would help to handle the sequence as a single object that can be added, multiplied and solved for.

The previous lesson solved every linear recurrence with constant coefficients by the characteristic equation: substitute $r^{n}$ , find the roots, fit the initial conditions. That method says nothing about a count built from independent choices, such as the ways to pay 50p in coins, and fails outright when earlier terms are multiplied together. This lesson packs a sequence into a power series, its generating function, so that operations on counts become algebra. It recovers Binet's formula without a guess, and finds the Catalan numbers, which no characteristic equation can reach.

A sequence as a power series

Given a sequence $a_{0}, a_{1}, a_{2}, \dots$ , its generating function is

A (x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3} + \dots

The power of $x$ is a label: the coefficient of $x^{n}$ is the $n$ th term, and nothing else is stored. The row $1, 3, 3, 1$ of Pascal's triangle becomes $(1 + x)^{3}$ , the binomial theorem read backwards. The notation $[x^{n}] A (x)$ means the coefficient of $x^{n}$ in $A (x)$ , so $[x^{2}] (1 + x)^{3} = 3$ .

Two series are added term by term and multiplied as polynomials are, so the coefficient of $x^{n}$ in $A (x) B (x)$ is $a_{0} b_{n} + a_{1} b_{n - 1} + \dots + a_{n} b_{0}$ . That is a finite sum: each coefficient of a sum or product needs only finitely many terms of the inputs, so every operation is ordinary arithmetic.

That is why convergence does not matter here. A series in this sense is a formal power series: an infinite list of coefficients written in a convenient notation, with $x$ never replaced by a number. The series $1 + x + 2 x^{2} + 6 x^{3} + 24 x^{4} + \dots$ , whose coefficients are the factorials $n!$ , converges for no $x$ other than $0$ , yet it is a perfectly good formal series and can be added and multiplied like any other. An identity between formal series means only that the two coefficient lists agree, place by place; nothing is ever summed.

Division needs one condition. If $A (x)$ has a nonzero constant term, there is exactly one series $B (x)$ with $A (x) B (x) = 1$ , found one coefficient at a time: the constant term of the product fixes $b_{0}$ , the coefficient of $x$ then fixes $b_{1}$ , and so on. So fractions like $\frac{x}{1 - x - x^{2}}$ below are genuine series, not symbols awaiting a value of $x$ .

The geometric series and its relatives

The most important series has every coefficient equal to $1$ . Multiply it by $1 - x$ :

(1 - x) (1 + x + x^{2} + x^{3} + \dots) = 1 + (x - x) + (x^{2} - x^{2}) + \dots = 1

Every coefficient after the constant cancels, and each cancellation involves only two terms, so this is a formal identity with no condition on $x$ . Therefore

\frac{1}{1 - x} = 1 + x + x^{2} + x^{3} + \dots

The same cancellation works with $c x$ in place of $x$ , for any constant $c$ , so $\frac{1}{1 - c x}$ generates the powers $1, c, c^{2}, c^{3}, \dots$ . With $c = 2$ it generates $2^{n}$ ; with $c = - 1$ it generates $1, - 1, 1, - 1, \dots$ . Putting $x^{2}$ in place of $x$ gives $\frac{1}{1 - x^{2}} = 1 + x^{2} + x^{4} + \dots$ , which has a $1$ at every even power and a $0$ at every odd one, and in general $\frac{1}{1 - x^{c}}$ marks the multiples of $c$ .

Multiplying by $x$ shifts a sequence one place to the right, so $\frac{x^{3}}{1 - x}$ is $x^{3} + x^{4} + \dots$ . A finite sequence is a polynomial: $1 + x + x^{2} + x^{3}$ equals $\frac{1 - x^{4}}{1 - x}$ , the finite geometric sum.

These pieces are enough to read off many coefficients. For example, $[x^{8}] (\frac{x^{2}}{1 - 3 x} + \frac{5}{1 - x})$ is the coefficient of $x^{6}$ in $\frac{1}{1 - 3 x}$ , which is $3^{6} = 729$ , plus $5$ , giving $734$ . Each problem below turns a count into a product or quotient of such pieces, then reads the coefficients back.

Multiplying counts combined choices

Multiplying series has a meaning in counting. Suppose there are $a_{k}$ ways to make a choice of size $k$ from one source and $b_{j}$ ways from a second, independent source. A combined choice of total size $n$ takes some size $k$ from the first and the remaining $n - k$ from the second, in $a_{k} b_{n - k}$ ways by the product rule. Adding over $k$ by the sum rule gives

c_{n} = \sum_{k = 0}^{n} a_{k} b_{n - k}

which is exactly the coefficient of $x^{n}$ in $A (x) B (x)$ . This sum is the convolution of the two sequences, and it is the whole reason generating functions count: exponents add, so $x^{k}$ from one factor meets $x^{n - k}$ from the other on $x^{n}$ .

One die generates $x + x^{2} + \dots + x^{6}$ , the exponent recording the score. In its square the coefficient of $x^{7}$ collects $x^{1} x^{6}$ up to $x^{6} x^{1}$ , the six ways to throw $7$ with two dice, and the cube gives the $27$ ways to throw $10$ with three.

Now take $k$ copies of $\frac{1}{1 - x}$ , each standing for an unlimited supply of one kind of object, with the exponent counting how many are taken. The coefficient of $x^{n}$ in $\frac{1}{(1 - x)^{k}}$ counts the ways to write $n = n_{1} + n_{2} + \dots + n_{k}$ with every $n_{i} \geq 0$ , which is a selection of $n$ objects from $k$ kinds with repetition. Stars and bars, from an earlier lesson (arrange $n$ stars and $k - 1$ dividing bars in a row), counts these as $(\binom{n + k - 1}{k - 1})$ . So

\frac{1}{(1 - x)^{k}} = \sum_{n \geq 0} (\binom{n + k - 1}{k - 1}) x^{n}

and in particular $\frac{1}{(1 - x)^{2}}$ generates the numbers $n + 1$ .

Example. A shop sells lemon, cherry and mint sweets. How many bags of $10$ sweets contain an even number of cherry and at most one mint?

Each flavour becomes a factor recording the allowed amounts. Lemon may be any number, $\frac{1}{1 - x}$ ; cherry must be even, $\frac{1}{1 - x^{2}}$ ; mint is $0$ or $1$ , $1 + x$ . The bags are counted by the product

\frac{1}{1 - x} \cdot \frac{1}{1 - x^{2}} \cdot (1 + x) = \frac{1}{(1 - x)^{2}}

because $1 - x^{2} = (1 - x) (1 + x)$ and the factor $1 + x$ cancels. So there are $n + 1$ bags of $n$ sweets, and $11$ bags of $10$ . A direct check agrees: with no mint the cherries number $0, 2, \dots, 10$ , six ways, and with one mint they number $0, 2, \dots, 8$ out of nine, five ways.

Now you. A basket of fruit holds an even number of apples, a multiple of $5$ bananas, at most $4$ oranges and at most $1$ pear. How many baskets of $20$ fruit are there?

Answer

The factors are $\frac{1}{1 - x^{2}}$ , $\frac{1}{1 - x^{5}}$ , $\frac{1 - x^{5}}{1 - x}$ for the oranges (the finite sum $1 + x + \dots + x^{4}$ ) and $1 + x$ . The $1 - x^{5}$ cancels, and $\frac{1 + x}{1 - x^{2}} = \frac{1}{1 - x}$ , so the product is $\frac{1}{(1 - x)^{2}}$ again and there are $21$ baskets.

Making change

In how many ways can 50p be paid using 1p, 2p, 5p, 10p and 20p coins, with any number of each? Order does not matter: two 20p and a 10p is one way, whichever coin is handed over first. Each coin type is an unlimited supply whose contribution comes in multiples of its value, so the 5p coins contribute $1 + x^{5} + x^{10} + \dots = \frac{1}{1 - x^{5}}$ , and the answer is the coefficient of $x^{50}$ in

P (x) = \frac{1}{(1 - x) (1 - x^{2}) (1 - x^{5}) (1 - x^{10}) (1 - x^{20})}

Its coefficients have no tidy closed form, but they are fast to compute. Suppose $A (x)$ counts the ways using some coins, and $B (x) = \frac{A (x)}{1 - x^{c}}$ adds a coin worth $c$ . Then $B (x) (1 - x^{c}) = A (x)$ , and comparing coefficients of $x^{n}$ gives $b_{n} - b_{n - c} = a_{n}$ , that is,

b_{n} = a_{n} + b_{n - c}

with $b_{n} = a_{n}$ for $n < c$ . In words, a payment either uses no coin worth $c$ or uses one that can be removed. So each new coin is one pass along a row, adding the entry $c$ places back.

Start with 1p coins alone, which give one way for every amount. Adding 2p coins gives $1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6$ for amounts $0$ to $10$ , the value $⌊ n / 2 ⌋ + 1$ from choosing how many 2p coins to use. Adding 5p coins then gives $1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10$ . Carried on to 50p, the rows end at $26$ with 1p and 2p only, then $146$ with 5p, $341$ with 10p, and finally

[x^{50}] P (x) = 450

A brute force count by computer agrees. Allowing a 50p coin as well adds exactly one way, the coin itself, for $451$ .

Example. In how many ways can 10p be made from 1p, 2p and 5p coins?

The last entry of the 1p, 2p and 5p row is $10$ , from the step $b_{10} = a_{10} + b_{5} = 6 + 4$ : six ways with no 5p coin, and four ways to make the rest once one 5p coin is set aside. Listing confirms it: with two 5p coins there is one way, with one 5p coin the remaining 5p takes $0$ , $1$ or $2$ of the 2p coins, three ways, and with none the 10p takes $0$ to $5$ of the 2p coins, six ways, and $1 + 3 + 6 = 10$ .

Now you. In how many ways can 20p be made from 1p, 2p, 5p and 10p coins?

Answer

Extend the 1p and 2p row to $20$ , where it ends at $11$ , then add 5p coins to get $1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 16, 18, 20, 22, 24, 26, 29$ . Adding 10p coins changes each entry from $10$ on by adding the new entry ten places back: $b_{10} = 10 + 1 = 11$ and $b_{20} = 29 + b_{10} = 29 + 11 = 40$ . There are $40$ ways.

Fibonacci by partial fractions

A recurrence becomes an equation for its generating function. Let $F (x) = \sum F_{n} x^{n}$ for the Fibonacci numbers, with $F_{0} = 0$ , $F_{1} = 1$ and $F_{n} = F_{n - 1} + F_{n - 2}$ . Shifting by one and two places gives $x F (x)$ and $x^{2} F (x)$ , whose coefficients of $x^{n}$ are $F_{n - 1}$ and $F_{n - 2}$ . So in $F (x) - x F (x) - x^{2} F (x)$ the coefficient of $x^{n}$ is $F_{n} - F_{n - 1} - F_{n - 2} = 0$ for every $n \geq 2$ , and only the first two terms survive: the constant $F_{0} = 0$ and $(F_{1} - F_{0}) x = x$ . Hence

F (x) = \frac{x}{1 - x - x^{2}}

The whole sequence is now one fraction. To read its coefficients, factor the denominator as $(1 - φ x) (1 - ψ x)$ . Expanding, this needs $φ + ψ = 1$ and $φ ψ = - 1$ , so $φ$ and $ψ$ are the roots of $t^{2} = t + 1$ : the golden ratio $φ = \frac{1 + \sqrt{5}}{2}$ and $ψ = \frac{1 - \sqrt{5}}{2}$ , with $φ - ψ = \sqrt{5}$ . Then split the fraction into partial fractions, a sum of the simple kind whose coefficients are known:

\frac{1}{1 - φ x} - \frac{1}{1 - ψ x} = \frac{(1 - ψ x) - (1 - φ x)}{(1 - φ x) (1 - ψ x)} = \frac{(φ - ψ) x}{1 - x - x^{2}}

Dividing by $φ - ψ = \sqrt{5}$ gives $F (x)$ . Each piece is a geometric series, $\frac{1}{1 - φ x}$ generating $φ^{n}$ , so

F_{n} = \frac{φ^{n} - ψ^{n}}{\sqrt{5}}

which is Binet's formula from the previous lesson. There it came from guessing that solutions look like $r^{n}$ ; here nothing was guessed, and the powers appear because each factor of the denominator is a geometric series. A forcing term, which needed a separate particular solution before, is just another series on the right.

Example. Solve the Tower of Hanoi recurrence $T_{n} = 2 T_{n - 1} + 1$ , $T_{0} = 0$ , with a generating function.

For $n \geq 1$ the coefficient of $x^{n}$ in $T (x) - 2 x T (x)$ is $T_{n} - 2 T_{n - 1} = 1$ , and the constant term is $T_{0} = 0$ . So $(1 - 2 x) T (x) = x + x^{2} + \dots = \frac{x}{1 - x}$ , and

T (x) = \frac{x}{(1 - x) (1 - 2 x)} = \frac{1}{1 - 2 x} - \frac{1}{1 - x}

where the split checks because $(1 - x) - (1 - 2 x) = x$ . Reading coefficients, $T_{n} = 2^{n} - 1$ , as unrolling found.

Now you. Solve $a_{n} = a_{n - 1} + 6 a_{n - 2}$ with $a_{0} = 1$ and $a_{1} = 8$ by a generating function, and find $a_{6}$ .

Answer

$(1 - x - 6 x^{2}) A (x) = a_{0} + (a_{1} - a_{0}) x = 1 + 7 x$ , and $1 - x - 6 x^{2} = (1 - 3 x) (1 + 2 x)$ . Writing $\frac{1 + 7 x}{(1 - 3 x) (1 + 2 x)} = \frac{P}{1 - 3 x} + \frac{Q}{1 + 2 x}$ needs $P + Q = 1$ and $2 P - 3 Q = 7$ , so $P = 2$ and $Q = - 1$ . So $a_{n} = 2 \cdot 3^{n} - (- 2)^{n}$ , and $a_{6} = 1458 - 64 = 1394$ , which the recurrence confirms: $14, 62, 146, 518, 1394$ .

The Catalan numbers

How many ways can $n$ pairs of brackets be written so that they match? With three pairs there are five: $((()))$ , $(() ())$ , $(()) ()$ , $() (())$ and $() () ()$ . Call the number $C_{n}$ , with $C_{0} = 1$ for the empty string. A nonempty matched string opens with a bracket, and that bracket closes somewhere, so the string is $(A) B$ where $A$ and $B$ are matched strings. If the whole has $n + 1$ pairs and $A$ has $k$ , then $B$ has $n - k$ , and

C_{n + 1} = \sum_{k = 0}^{n} C_{k} C_{n - k}

This recurrence multiplies earlier terms together, so no characteristic equation applies. But the sum is a convolution, the coefficient of $x^{n}$ in $C (x)^{2}$ . Multiplying by $x$ to shift it into place and adding back $C_{0}$ gives

C (x) = 1 + x C (x)^{2}

a quadratic in $C (x)$ . The quadratic formula gives $C (x) = \frac{1 \pm \sqrt{1 - 4 x}}{2 x}$ , and the sign is forced: with the plus sign the numerator has constant term $2$ , so dividing by $2 x$ would leave a term $\frac{1}{x}$ . Taking the minus sign, the formal square root $\sqrt{1 - 4 x}$ is the one series with constant term $1$ whose square is $1 - 4 x$ , and Newton's generalisation of the binomial theorem to the power $\frac{1}{2}$ gives it:

\sqrt{1 - 4 x} = 1 - 2 x - 2 x^{2} - 4 x^{3} - 10 x^{4} - 28 x^{5} - \dots

Subtracting from $1$ and dividing by $2 x$ gives $C (x) = 1 + x + 2 x^{2} + 5 x^{3} + 14 x^{4} + \dots$ , matching the count of five for three pairs. The general coefficient of $x^{m}$ in the root, for $m \geq 1$ , is $(\binom{1 / 2}{m}) (- 4)^{m}$ . Its numerator $\frac{1}{2} (\frac{1}{2} - 1) \dots (\frac{1}{2} - m + 1)$ is $(- 1)^{m - 1}$ times $1 \cdot 3 \cdot 5 \dots (2 m - 3)$ over $2^{m}$ , and the odd product equals $\frac{(2 m - 2)!}{2^{m - 1} (m - 1)!}$ . Multiplying by $(- 4)^{m}$ and dividing by $m!$ leaves $- \frac{2}{m} (\binom{2 m - 2}{m - 1})$ . Put $m = n + 1$ , negate and halve, and

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})

So $C_{4} = \frac{70}{5} = 14$ and $C_{10} = \frac{184 756}{11} = 16 796$ . The same numbers count the ways to cut a convex polygon with $n + 2$ sides into triangles, which Euler worked out in 1751; they are named after Eugène Catalan, who met them counting bracketings in 1838, and a later lesson meets them again counting binary trees.

The end of counting

Generating functions close the counting half of the course because they absorb what came before. The binomial theorem is the generating function $(1 + x)^{n}$ ; stars and bars is the coefficient of $\frac{1}{(1 - x)^{k}}$ ; a linear recurrence is a rational function taken apart by partial fractions; and a count built from independent pieces, like a pile of coins, is a product. The limits are honest ones: many generating functions, $P (x)$ for coins among them, have no closed formula for their coefficients, and then the method becomes an efficient way to compute rather than a formula.

Everything so far has asked how many. The second half of the course asks what the integers themselves are made of, beginning with the most basic relation between two of them: whether one divides the other. The next lesson proves that division always leaves a well defined remainder, and turns that fact into Euclid's algorithm for the greatest common divisor, one of the oldest algorithms still in use.

Divisibility and the Euclidean algorithm

Finding the largest number that divides both $6188$ and $4709$ by factoring them means discovering that $4709 = 17 \times 277$ , and factoring is slow work that gets slower very quickly as numbers grow.

The previous lesson closed the counting half of the course; this one opens the second half, on the structure of the integers. Recall that $a ∣ b$ means $b = a k$ for some integer $k$ , and that a number dividing $b$ and $c$ divides every combination $b x + c y$ . This lesson proves that division leaves a well defined remainder, turns that into Euclid's algorithm for the greatest common divisor, which needs no factoring, shows why it is fast, and runs it backwards.

Division with remainder

Dividing $17$ by $5$ gives $3$ with remainder $2$ , and school arithmetic takes for granted that the answer always exists and is the only one. Both halves need proof, because everything here rests on them.

The division algorithm. For integers $a$ and $b$ with $b > 0$ there are unique integers $q$ and $r$ with $a = b q + r$ and $0 \leq r < b$ . The number $q$ is the quotient and $r$ the remainder, written $a mod b$ .

For existence, let $S$ be the set of non-negative numbers of the form $a - b k$ , with $k$ any integer. It is not empty, since $k = - | a |$ gives $a + b | a | \geq 0$ . The well-ordering principle, that every non-empty set of non-negative integers has a least element, is induction in another form, and it gives a smallest member of $S$ , say $r = a - b q$ . Then $r \geq 0$ . If $r \geq b$ , then $r - b = a - b (q + 1)$ would be a smaller member of $S$ , which is impossible. So $0 \leq r < b$ .

For uniqueness, suppose $a = b q + r = b q^{'} + r^{'}$ with both remainders between $0$ and $b - 1$ . Then $b (q - q^{'}) = r^{'} - r$ , which lies strictly between $- b$ and $b$ . The only multiple of $b$ there is $0$ , so $r = r^{'}$ and $q = q^{'}$ .

The condition $0 \leq r < b$ matters for negative $a$ : $- 17 = 5 \times (- 4) + 3$ , so $- 17 mod 5 = 3$ . Programming languages often disagree. In C and JavaScript -17 % 5 gives $- 2$ , because they round the quotient towards zero, and code that assumes remainders are never negative breaks on exactly this case.

The greatest common divisor

For integers $a$ and $b$ , not both zero, the greatest common divisor $\gcd (a, b)$ is the largest integer dividing both. It exists because $1$ is a common divisor and no divisor of a non-zero number exceeds its size. So $\gcd (12, 18) = 6$ , $\gcd (8, 15) = 1$ , and $\gcd (a, 0) = | a |$ , since every integer divides $0$ . Numbers whose $\gcd$ is $1$ are coprime.

Listing divisors fails for large numbers, and factoring first only moves the difficulty, since no fast method of factoring is known; a later lesson rests a whole cryptosystem on that fact. The way round it is one observation about remainders.

The key lemma. If $a = b q + r$ for integers $q$ and $r$ , then $a$ and $b$ have exactly the same common divisors as $b$ and $r$ . In particular $\gcd (a, b) = \gcd (b, r)$ .

The proof is divisibility of combinations and nothing else. If $d ∣ a$ and $d ∣ b$ , then $d$ divides $a - b q$ , which is $r$ . If $d ∣ b$ and $d ∣ r$ , then $d$ divides $b q + r$ , which is $a$ . So the two pairs share one set of common divisors, and one set has one largest member. The lemma does not need $r$ to be the remainder, or even positive; any $q$ will do, a freedom used below.

With $r = a mod b$ it reads $\gcd (a, b) = \gcd (b, a mod b)$ , and it replaces a pair by a strictly smaller one, since $a mod b < b$ .

Euclid's algorithm

Apply the lemma over and over. Divide $a$ by $b$ , divide $b$ by the remainder, and keep dividing each divisor by the remainder it left, until a remainder is $0$ . The last non-zero remainder $g$ is the greatest common divisor: the final pair is $(g, 0)$ , $\gcd (g, 0) = g$ , and the lemma says the $\gcd$ never changed on the way. The process stops because the remainders are a strictly decreasing sequence of non-negative integers.

This is Propositions 1 and 2 of Book VII of Euclid's Elements, written around 300 BC. Euclid works with lengths, taking the smaller from the larger until it no longer fits, which is division done by repeated subtraction. Donald Knuth called it the granddaddy of all algorithms, the oldest nontrivial one still in use, and it still runs inside the software that reduces fractions and generates encryption keys.

Example. Find $\gcd (6188, 4709)$ .

Each row divides $a$ by $b$ , and the next row moves $b$ and the remainder up one place:

$a$	$b$	quotient	remainder
$6188$	$4709$	$1$	$1479$
$4709$	$1479$	$3$	$272$
$1479$	$272$	$5$	$119$
$272$	$119$	$2$	$34$
$119$	$34$	$3$	$17$
$34$	$17$	$2$	$0$

The last non-zero remainder is $17$ , so $\gcd (6188, 4709) = 17$ , after six divisions and without meeting the prime $277$ . Check: $6188 = 17 \times 364$ and $4709 = 17 \times 277$ , and since $277$ is prime and does not divide $364$ , nothing larger is shared.

Now you. Find $\gcd (5767, 4453)$ , and count the divisions.

Answer

$5767 = 1 \times 4453 + 1314$ , $4453 = 3 \times 1314 + 511$ , $1314 = 2 \times 511 + 292$ , $511 = 1 \times 292 + 219$ , $292 = 1 \times 219 + 73$ , $219 = 3 \times 73 + 0$ . Six divisions, and $\gcd (5767, 4453) = 73$ . Check: $5767 = 73 \times 79$ and $4453 = 73 \times 61$ .

Euclid on symbols

The algorithm does not need numbers. Whenever one expression is a multiple of another plus something simpler, the lemma applies, and a question about infinitely many pairs becomes a few lines of algebra.

Example. Prove that $\frac{21 n + 4}{14 n + 3}$ is in lowest terms for every positive integer $n$ . This was the first problem of the first International Mathematical Olympiad, held in Romania in 1959.

Lowest terms means the $\gcd$ of top and bottom is $1$ . Divide as if the expressions were numbers: $21 n + 4 = 1 \times (14 n + 3) + (7 n + 1)$ and $14 n + 3 = 2 \times (7 n + 1) + 1$ . By the lemma twice, $\gcd (21 n + 4, 14 n + 3) = \gcd (14 n + 3, 7 n + 1) = \gcd (7 n + 1, 1) = 1$ . At $n = 7$ the fraction is $\frac{151}{101}$ , and both are prime.

Now you. Show that $\gcd (n + 3, 2 n + 1)$ is always $1$ or $5$ , and say for which $n$ it is $5$ .

Answer

Write $2 n + 1 = 2 (n + 3) - 5$ . The lemma allows any quotient, so $\gcd (2 n + 1, n + 3) = \gcd (n + 3, - 5) = \gcd (n + 3, 5)$ , which is $1$ or $5$ . It is $5$ exactly when $5 ∣ n + 3$ , that is for $n = 2, 7, 12, \dots$ ; at $n = 7$ the pair is $10$ and $15$ .

Why it is fast

Six divisions for four digit numbers is typical, and there is a quick reason. If a remainder is at most half the divisor before it, the next is smaller still; if it is more than half, the next quotient is $1$ and the next remainder is the difference, less than half. Either way every two divisions at least halve the numbers, so the work grows with the number of digits, not with the size of the numbers.

The exact worst case was found by Gabriel Lamé in 1844, and it is the Fibonacci numbers, $F_{0} = 0$ , $F_{1} = 1$ and $F_{n} = F_{n - 1} + F_{n - 2}$ , the sequence that earlier lessons on recurrences solved with Binet's formula. Run the algorithm on $F_{n + 2}$ and $F_{n + 1}$ . Since $F_{n + 2} = 1 \times F_{n + 1} + F_{n}$ with $F_{n} < F_{n + 1}$ , every quotient is $1$ and every remainder is the previous Fibonacci number, until $(3, 2)$ leaves $1$ and $(2, 1)$ finishes with quotient $2$ . That is exactly $n$ divisions, shrinking as slowly as possible, and it ends at $1$ : consecutive Fibonacci numbers are coprime.

Lamé's theorem. If the algorithm on $a > b > 0$ takes $n$ divisions, then $b \geq F_{n + 1}$ and $a \geq F_{n + 2}$ .

Read the run from the bottom up. The last non-zero remainder is at least $1 = F_{2}$ . The number above it is a larger multiple of it, so at least $2 = F_{3}$ . Every other number is the one below it times a quotient of at least $1$ , plus the one below that, so it is at least the sum of the two. That is the Fibonacci recurrence with $\geq$ in place of $=$ , and induction up the run gives the bounds $F_{4}, F_{5}, \dots$ , reaching $F_{n + 1}$ at $b$ and $F_{n + 2}$ at $a$ . Consecutive Fibonacci numbers meet every bound exactly, so no smaller pair takes as long.

The counts check out. The pair $(144, 89) = (F_{12}, F_{11})$ takes $10$ divisions, and a computer search over every pair with $b < 100$ finds nothing longer; with $b < 1000$ the longest run is $15$ , at $(1597, 987)$ . Binet's formula makes $F_{n + 1}$ grow like ${1.618}^{n}$ , and ${1.618}^{5} \approx 11.09$ exceeds $10$ , so each extra digit of $b$ allows fewer than five more divisions: at most five times the number of digits of $b$ . For a $100$ digit $b$ the true maximum is $479$ , since $F_{480}$ is the largest Fibonacci number below $10^{100}$ .

Running it backwards

Each division can be solved for its remainder, and that makes the $\gcd$ more than the largest common divisor: it is a combination of the two numbers.

Bézout's identity. For integers $a$ and $b$ , not both zero, there are integers $x$ and $y$ with $a x + b y = \gcd (a, b)$ .

The proof is the algorithm. The first two numbers of the run are combinations of $a$ and $b$ , trivially: $a = 1 \times a + 0 \times b$ and $b = 0 \times a + 1 \times b$ . Each later number is the one two places above minus a quotient times the one just above, and that is again a combination. By induction every remainder is a combination of $a$ and $b$ , the last non-zero one included. The name is Étienne Bézout's, for his 1779 work on polynomials, though Claude Bachet de Méziriac stated the integer version in 1624.

A computer carries $x$ and $y$ forwards like this, row by row. By hand it is easier to start at the bottom and substitute upwards, which is why the method, called extended Euclid, is described as running the algorithm backwards.

Example. Find integers $x$ and $y$ with $252 x + 198 y = \gcd (252, 198)$ .

The run is $252 = 1 \times 198 + 54$ , $198 = 3 \times 54 + 36$ , $54 = 1 \times 36 + 18$ and $36 = 2 \times 18$ , so the $\gcd$ is $18$ . Solve the last useful division for $18$ , then replace each remainder by the division that produced it:

18 = 54 - 36 = 54 - (198 - 3 \times 54) = 4 \times 54 - 198

4 \times 54 - 198 = 4 (252 - 198) - 198 = 4 \times 252 - 5 \times 198

So $x = 4$ and $y = - 5$ . Check: $1008 - 990 = 18$ .

Now you. Find integers $x$ and $y$ with $97 x + 35 y = 1$ .

Answer

The run is $97 = 2 \times 35 + 27$ , $35 = 1 \times 27 + 8$ , $27 = 3 \times 8 + 3$ , $8 = 2 \times 3 + 2$ , $3 = 1 \times 2 + 1$ , so the $\gcd$ is $1$ . Substituting upwards, $1 = 3 - 2 = 3 \times 3 - 8 = 3 \times 27 - 10 \times 8 = 13 \times 27 - 10 \times 35 = 13 \times 97 - 36 \times 35$ . So $x = 13$ and $y = - 36$ , and indeed $1261 - 1260 = 1$ .

What Bézout's identity buys

Write $g = \gcd (a, b) = a x + b y$ . Any common divisor $d$ divides $a x + b y$ , so $d ∣ g$ : the $\gcd$ is greatest in the stronger sense that every common divisor divides it. The common divisors of $252$ and $198$ are exactly the divisors of $18$ .

It also settles which numbers are combinations. Since $g$ divides $a$ and $b$ , it divides every $a x + b y$ , and scaling the Bézout combination gives every multiple of $g$ . So $a x + b y = c$ has integer solutions exactly when $g ∣ c$ , and the smallest positive combination is $g$ itself. For instance $252 x + 198 y = 36$ is solved by $x = 8$ , $y = - 10$ , while $252 x + 198 y = 30$ has no solution, since $18$ does not divide $30$ . Solutions are never unique: adding $11$ to $x$ and subtracting $14$ from $y$ changes $252 x + 198 y$ by $2772 - 2772 = 0$ , so $(15, - 19)$ also gives $18$ .

In particular $a$ and $b$ are coprime exactly when $1$ is a combination of them, since a common divisor of both divides any combination. A later lesson builds division in modular arithmetic on exactly this.

Its first real consequence, though, is about primes. A divisor of a product need not divide a factor: $6$ divides $36 = 4 \times 9$ but divides neither $4$ nor $9$ . For a prime it must, and a prime $p$ that does not divide $a$ is coprime to it, so $p x + a y = 1$ for some integers, which is the lever. That is Euclid's lemma, Proposition 30 of the same Book VII, and the next lesson proves it from Bézout's identity in three lines and builds on it the fundamental theorem of arithmetic: every integer greater than $1$ factors into primes in exactly one way.

Primes and factorisation

Every whole number greater than $1$ can be broken into primes, and the real question is whether it can be broken in only one way.

The previous lesson ran Euclid's algorithm backwards to get Bézout's identity: for integers $a$ and $b$ , not both zero, there are integers $x$ and $y$ with $a x + b y = \gcd (a, b)$ . This lesson proves Euclid's lemma from Bézout, uses it to prove that factorisation into primes is unique, then turns to finding primes and counting them.

Primes, and why every number has one

An integer $p > 1$ is prime if its only positive divisors are $1$ and $p$ , and an integer $n > 1$ that is not prime is composite, a product $n = a b$ with $1 < a, b < n$ . The number $1$ is neither: if it counted as prime, $6 = 2 \times 3 = 1 \times 2 \times 3$ would already be two factorisations.

Every integer $n > 1$ has a prime divisor, because its smallest divisor $d > 1$ is prime: a divisor $c$ of $d$ with $1 < c < d$ would divide $n$ too, contradicting the choice of $d$ . So the least divisor of $91$ above $1$ is $7$ , which is prime, and $91 = 7 \times 13$ .

That fact carries Euclid's proof that the primes never run out, recalled here from Proof and Logic rather than taught again: for any finite list of primes, their product plus $1$ leaves remainder $1$ on division by each, so its prime divisor is missing from the list. The proof, in Book IX of Euclid's Elements around 300 BC, says nothing about how the primes are spread out, a question the end of this lesson takes up.

Euclid's lemma

Euclid's lemma says: if $p$ is prime and $p ∣ a b$ , then $p ∣ a$ or $p ∣ b$ . (Here $p ∣ a b$ reads " $p$ divides $a b$ ".) Composite numbers fail it: $6 ∣ 4 \times 9$ , yet $6$ divides neither $4$ nor $9$ , because the factors $2$ and $3$ of $6$ went to different places.

The proof is short. Suppose $p ∣ a b$ and $p$ does not divide $a$ . The only positive divisors of $p$ are $1$ and $p$ , so $\gcd (p, a) = 1$ . Bézout's identity gives integers $x$ and $y$ with

p x + a y = 1

Multiply through by $b$ to get $p b x + a b y = b$ . The first term is a multiple of $p$ , and so is the second, since $p ∣ a b$ . So $p$ divides their sum, which is $b$ .

The lemma extends to any number of factors by induction: if $p ∣ a_{1} a_{2} \dots a_{k}$ , write the product as $a_{1} \cdot (a_{2} \dots a_{k})$ , and either $p ∣ a_{1}$ or $p$ divides the shorter product. In particular, if a prime $p$ divides a product of primes $q_{1} q_{2} \dots q_{k}$ , it divides some $q_{j}$ , and since the only divisor of $q_{j}$ above $1$ is $q_{j}$ itself, $p = q_{j}$ .

Example. Prove that $\sqrt{3}$ is irrational.

Suppose $\sqrt{3} = \frac{a}{b}$ with $a$ and $b$ positive integers sharing no common factor. Squaring gives $a^{2} = 3 b^{2}$ , so $3 ∣ a \cdot a$ , and Euclid's lemma gives $3 ∣ a$ . Write $a = 3 c$ ; then $9 c^{2} = 3 b^{2}$ , so $b^{2} = 3 c^{2}$ , and the same step gives $3 ∣ b$ . Now $3$ divides both, contradicting lowest terms. The proof for $\sqrt{2}$ in Proof and Logic used parity at this step; Euclid's lemma works for every prime.

Now you. Prove that $\sqrt{15}$ is irrational.

Answer

Suppose $\sqrt{15} = \frac{a}{b}$ in lowest terms, so $a^{2} = 15 b^{2}$ . Then $3 ∣ a^{2}$ , so $3 ∣ a$ by Euclid's lemma. Writing $a = 3 c$ gives $9 c^{2} = 15 b^{2}$ , that is $3 c^{2} = 5 b^{2}$ . So $3 ∣ 5 b^{2}$ , and since $3$ does not divide $5$ the lemma gives $3 ∣ b^{2}$ and then $3 ∣ b$ . Both $a$ and $b$ are multiples of $3$ , a contradiction.

The fundamental theorem of arithmetic

Theorem. Every integer $n > 1$ is a product of primes, and this product is unique apart from the order of the factors.

Existence is proved by strong induction, where the hypothesis covers every smaller case at once. The number $2$ is prime. Take $n > 2$ and assume every integer from $2$ to $n - 1$ is a product of primes. If $n$ is prime there is nothing to do. Otherwise $n = a b$ with $1 < a, b < n$ , both $a$ and $b$ are products of primes by hypothesis, and writing one list after the other expresses $n$ . Ordinary induction would not do, since $a$ and $b$ can be anywhere below $n$ .

Uniqueness is where Euclid's lemma enters. Suppose

p_{1} p_{2} \dots p_{r} = q_{1} q_{2} \dots q_{s}

with every $p_{i}$ and $q_{j}$ prime, and argue by induction on $r$ . The prime $p_{1}$ divides the right side, so by the extended lemma $p_{1} = q_{j}$ for some $j$ . Reorder so that this one is $q_{1}$ and cancel it, leaving $p_{2} \dots p_{r} = q_{2} \dots q_{s}$ , a shorter equation of the same kind. By the inductive hypothesis its sides are the same primes in some order, and so were the originals. (When $r = 1$ , cancelling leaves $1 = q_{2} \dots q_{s}$ , which forces $s = 1$ .)

Collecting repeated primes gives the standard form $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}$ with $p_{1} < p_{2} < \dots < p_{k}$ and every exponent at least $1$ , so $360 = 2^{3} \cdot 3^{2} \cdot 5$ . Two numbers are equal exactly when their standard forms agree, which is the sense in which the primes are the atoms of the integers. Euclid had the lemma, but the first clear statement and proof of the whole theorem is in Gauss's Disquisitiones Arithmeticae of 1801.

Why uniqueness is not obvious

Uniqueness can feel too obvious to need proof, since factorising $360$ by any route ends at the same primes. To see that it is a real theorem, look at a system where the existence proof works word for word and uniqueness fails.

Take the even numbers $2 ℕ = {2, 4, 6, 8, \dots}$ and call one "prime" there if it is not a product of two even numbers. Such a product is a multiple of $4$ , so the primes of this system are $2, 6, 10, 14, 18, \dots$ , the even numbers that are not multiples of $4$ . The strong induction goes through unchanged, so every even number is a product of these primes. But

36 = 6 \times 6 = 2 \times 18

and $2$ , $6$ and $18$ are all prime in $2 ℕ$ . What failed is Euclid's lemma: $6$ divides $2 \times 18$ in this system, yet divides neither $2$ nor $18$ , because $18 = 6 \times 3$ and $3$ is not in the system. And the lemma failed because its proof did: $2 ℕ$ has no $1$ , so no Bézout combination can equal $1$ .

The same thing happens in systems mathematicians needed. Among the numbers $a + b \sqrt{- 5}$ with $a$ and $b$ integers, $6 = 2 \times 3 = (1 + \sqrt{- 5}) (1 - \sqrt{- 5})$ , and none of those four factors splits further. In 1847 Gabriel Lamé announced a proof of Fermat's last theorem that quietly assumed unique factorisation in a system of this kind, and it emerged that Ernst Kummer had already shown in 1844 that it can fail there. For the ordinary integers the theorem holds, and the reason is the division algorithm, through Euclid's algorithm and Bézout.

Computing with factorisations

In standard form, divisibility becomes a comparison of exponents. If $n = p_{1}^{e_{1}} \dots p_{k}^{e_{k}}$ , then $d ∣ n$ exactly when $d = p_{1}^{f_{1}} \dots p_{k}^{f_{k}}$ with $0 \leq f_{i} \leq e_{i}$ for every $i$ . Conversely, if $n = d m$ , the standard forms of $d$ and $m$ together factorise $n$ , so by uniqueness no prime appears in $d$ more often than in $n$ .

Each divisor is then a choice of exponent for each prime, $e_{i} + 1$ options for $p_{i}$ , so by the product rule the number of positive divisors is

d (n) = (e_{1} + 1) (e_{2} + 1) \dots (e_{k} + 1)

For the gcd and lcm, write both numbers over the same primes, allowing exponent $0$ . A common divisor may take at most the smaller exponent of each prime and a common multiple needs at least the larger, so the gcd takes minimum exponents and the lcm maximum ones. Since $\min (e, f) + \max (e, f) = e + f$ , this proves $\gcd (a, b) \cdot lcm (a, b) = a b$ .

For large numbers Euclid's algorithm is far faster, since nobody knows a fast way to factorise, a gap a later lesson on RSA turns into a lock. By hand, the standard forms show everything at once.

Example. Find the number of divisors of $360$ , and $\gcd (360, 756)$ and $lcm (360, 756)$ .

Factorise: $360 = 2^{3} \cdot 3^{2} \cdot 5$ and $756 = 2^{2} \cdot 3^{3} \cdot 7$ . So $d (360) = 4 \cdot 3 \cdot 2 = 24$ . Over the primes $2, 3, 5, 7$ the exponents are $(3, 2, 1, 0)$ and $(2, 3, 0, 1)$ . Minimums give $\gcd = 2^{2} \cdot 3^{2} = 36$ , and maximums give $lcm = 2^{3} \cdot 3^{3} \cdot 5 \cdot 7 = 7560$ . Check: $36 \times 7560 = 272 160 = 360 \times 756$ .

Now you. Find the number of divisors of $1008$ , and $\gcd (1008, 840)$ and $lcm (1008, 840)$ .

Answer

$1008 = 2^{4} \cdot 3^{2} \cdot 7$ and $840 = 2^{3} \cdot 3 \cdot 5 \cdot 7$ . So $d (1008) = 5 \cdot 3 \cdot 2 = 30$ . The exponents over $2, 3, 5, 7$ are $(4, 2, 0, 1)$ and $(3, 1, 1, 1)$ , giving $\gcd = 2^{3} \cdot 3 \cdot 7 = 168$ and $lcm = 2^{4} \cdot 3^{2} \cdot 5 \cdot 7 = 5040$ , and $168 \times 5040 = 1008 \times 840$ .

The sieve of Eratosthenes

To list the primes up to a bound, the method credited to Eratosthenes of Cyrene, the third century BC scholar who also measured the Earth, crosses out composites instead of testing each number. Write out $2, 3, \dots, n$ . The first number, $2$ , is prime; cross out its multiples. The next survivor, $3$ , is prime, since no smaller prime divides it; cross out its multiples. Each number that survives to its turn is prime, and its multiples go.

The sieve can stop early. If $n = a b$ is composite with $a \leq b$ , then $a^{2} \leq a b = n$ , so $a \leq \sqrt{n}$ : every composite up to $n$ has a prime factor no bigger than $\sqrt{n}$ . Once the primes up to $\sqrt{n}$ have been used, every composite is gone. For the same reason the pass for $p$ can start at $p^{2}$ : smaller multiples of $p$ have a smaller prime factor too.

Run to $100$ , the sieve needs only $2$ , $3$ , $5$ and $7$ . The pass for $2$ crosses out the $49$ even numbers from $4$ to $100$ ; the pass for $3$ removes $16$ new ones, the odd multiples of $3$ from $9$ to $99$ ; the pass for $5$ removes only $25, 35, 55, 65, 85, 95$ ; and the pass for $7$ only $49, 77, 91$ . That is $74$ composites out of the $99$ numbers from $2$ to $100$ , leaving the $25$ primes.

Example. Find the primes between $100$ and $130$ .

Since $\sqrt{130} < 12$ , only $2, 3, 5, 7, 11$ are needed. The pass for $2$ leaves the fifteen odd numbers $101, 103, \dots, 129$ . The pass for $3$ removes $105, 111, 117, 123, 129$ ; the pass for $5$ removes $115$ and $125$ ; the pass for $7$ removes $119 = 7 \times 17$ ; and the pass for $11$ removes $121 = 11^{2}$ . The survivors are $101, 103, 107, 109, 113$ and $127$ , six primes.

Now you. Find the primes between $130$ and $160$ .

Answer

$\sqrt{160} < 13$ , so sieve with $2, 3, 5, 7, 11$ . Of the odd numbers from $131$ to $159$ , the pass for $3$ removes $135, 141, 147, 153, 159$ , the pass for $5$ removes $145$ and $155$ , the pass for $7$ removes $133 = 7 \times 19$ , and the pass for $11$ removes $143 = 11 \times 13$ . The primes are $131, 137, 139, 149, 151, 157$ .

How the primes thin out

Up to $100$ a quarter of the numbers are prime, from $101$ to $160$ only twelve of sixty. Write $π (x)$ for the number of primes up to $x$ (a name here, unrelated to $3.14159 \dots$ ). A computer sieve gives the counts below, set against $\frac{x}{\ln x}$ , with $\ln$ the natural logarithm.

$x$	$π (x)$	$x / \ln x$	ratio
100	25	21.7	1.151
1,000	168	144.8	1.161
10,000	1,229	1,085.7	1.132
1,000,000	78,498	72,382.4	1.084
1,000,000,000	50,847,534	48,254,942.4	1.054

The ratio drifts down towards $1$ , slowly. Carl Friedrich Gauss noticed the pattern in tables of primes around 1792, aged fifteen, and Adrien-Marie Legendre published a similar formula in 1798, but neither could prove it. In 1896 Jacques Hadamard and Charles de la Vallée Poussin, independently, proved the prime number theorem:

lim_{x \to \infty} \frac{π (x)}{x / \ln x} = 1

Both proofs used complex analysis, building on Bernhard Riemann's 1859 work on the zeta function. The theorem has a plain reading: near $x$ , roughly one number in $\ln x$ is prime. Near a million that is one in $14$ , near a billion one in $21$ . Up to a billion the average gap between primes is $10^{9} / 50 847 534 \approx 19.7$ , just under $\ln (10^{9}) \approx 20.7$ , the same slow convergence as in the table.

Locally the primes are irregular. Gaps can be as long as desired: for $n \geq 2$ the $n - 1$ numbers $n! + 2, \dots, n! + n$ are all composite, since $k$ divides $n! + k$ for each $k$ from $2$ to $n$ . Yet primes two apart, like $101$ and $103$ , keep appearing, and whether they do forever is unknown.

Divisibility is a question about remainders

Everything in this lesson has asked whether one number divides another, and that is a question about a remainder: $a ∣ b$ exactly when dividing $b$ by $a$ leaves remainder $0$ . The remainder of a product depends only on the remainders of its factors. Numbers leaving remainders $3$ and $5$ on division by $7$ are $7 s + 3$ and $7 t + 5$ , and their product is $7 (7 s t + 5 s + 3 t) + 15$ , which leaves the same remainder as $15$ , namely $1$ .

In that language Euclid's lemma says: if neither $a$ nor $b$ leaves remainder $0$ on division by a prime $p$ , neither does $a b$ . Nonzero remainders multiply without ever producing $0$ . For a composite divisor this fails, since $2 \times 3$ leaves remainder $0$ on division by $6$ : a divisor of a product that divides neither factor, as $6$ was in $2 ℕ$ . So the natural setting for divisibility is the remainders themselves, and the next lesson makes them into a number system with its own addition and multiplication, where some elements have inverses and equations can be solved.

Modular arithmetic

To know what day of the week it will be in $1000$ days there is no need to count them, because only the remainder of $1000$ on division by $7$ matters, and the problem is to turn that shortcut into arithmetic that can be trusted.

The previous lesson ended by noticing that divisibility questions are really questions about remainders. This lesson makes the remainders into a number system. It uses Bézout's identity from an earlier lesson: $a x + b y = \gcd (a, b)$ always has an integer solution, found by running Euclid's algorithm backwards.

Congruence

Fix a positive integer $n$ , the modulus. Two integers $a$ and $b$ are congruent modulo $n$ , written

a \equiv b (mod n)

when $n ∣ a - b$ . So $17 \equiv 2 (mod 5)$ , since $17 - 2 = 15$ , and $- 17 \equiv 3 (mod 5)$ , since $- 17 - 3 = - 20$ . This is the same as leaving the same remainder: if $a = n q + r$ and $b = n q^{'} + r^{'}$ with $0 \leq r, r^{'} < n$ , then $a - b = n (q - q^{'}) + (r - r^{'})$ , and $r - r^{'}$ lies strictly between $- n$ and $n$ , so $n ∣ a - b$ exactly when $r = r^{'}$ .

Proof and Logic showed that congruence modulo $n$ is an equivalence relation, so it splits the integers into classes. Write $[a]$ for the class of $a$ , the set of all integers congruent to it. Modulo $5$ the class $[2]$ is ${\dots, - 8, - 3, 2, 7, 12, \dots}$ , and there are exactly five classes, $[0], [1], [2], [3], [4]$ , one for each possible remainder. The set of the $n$ classes is written $ℤ_{n}$ .

A class has many names: $[2]$ , $[7]$ and $[- 3]$ are the same class modulo $5$ . That freedom lets a large number be swapped for a small one, and it is also a danger, because anything defined through a representative must come out the same whichever one is chosen.

Adding and multiplying classes

The natural definitions are $[a] + [b] = [a + b]$ and $[a] [b] = [a b]$ , and they are only well defined if the answer does not depend on which names were picked for the inputs.

Theorem. If $a \equiv a^{'}$ and $b \equiv b^{'} (mod n)$ , then $a + b \equiv a^{'} + b^{'}$ and $a b \equiv a^{'} b^{'} (mod n)$ .

For the sum, $(a + b) - (a^{'} + b^{'}) = (a - a^{'}) + (b - b^{'})$ , a sum of two multiples of $n$ . For the product, add and subtract $a b^{'}$ :

a b - a^{'} b^{'} = a (b - b^{'}) + b^{'} (a - a^{'})

and both terms on the right are multiples of $n$ . So $ℤ_{n}$ has an addition and a multiplication, which inherit the commutative, associative and distributive laws from the integers. Repeating the product rule gives $a^{k} \equiv b^{k} (mod n)$ , so any calculation built from sums and products may be reduced at any stage.

The days of the week are $ℤ_{7}$ . A year of $365$ days is $52$ weeks and $1$ day, so $365 \equiv 1 (mod 7)$ and a date moves one weekday later each ordinary year, and two after a leap day. The question in the first line is now easy: $1000 = 7 \times 142 + 6$ , so $1000 \equiv 6 \equiv - 1 (mod 7)$ , and $1000$ days after a Sunday is a Saturday.

Example. Apollo 11 landed on the Moon on Sunday 20 July 1969. On what day of the week did the fiftieth anniversary, 20 July 2019, fall?

The fifty years contain the leap days of 1972, 1976 and so on to 2016, which is twelve of them (2000 was a leap year). So the gap is $50 \times 365 + 12$ days. Modulo $7$ , replace $365$ by $1$ :

50 \times 365 + 12 \equiv 50 + 12 = 62 = 7 \times 8 + 6 \equiv 6 (mod 7)

Six days after Sunday is Saturday, which a computer's calendar confirms.

Now you. The United States Declaration of Independence is dated Thursday 4 July 1776. On what day of the week does its 250th anniversary, 4 July 2026, fall? Remember that in the Gregorian calendar 1800 and 1900 were not leap years, while 2000 was.

Answer

The leap years from 1780 to 2024 number $\frac{2024 - 1780}{4} + 1 = 62$ , less 1800 and 1900, so $60$ leap days. The gap is $250 \times 365 + 60 \equiv 250 + 60 = 310 \equiv 2 (mod 7)$ , since $308 = 7 \times 44$ . Two days after Thursday is Saturday.

Divisibility tests from $10 \equiv 1$ and $10 \equiv - 1$

A number written in decimal with digits $d_{k} \dots d_{1} d_{0}$ is $d_{0} + 10 d_{1} + 10^{2} d_{2} + \dots + 10^{k} d_{k}$ . Since $10 \equiv 1 (mod 9)$ , every power $10^{j} \equiv 1^{j} = 1$ , and the whole number is congruent to $d_{0} + d_{1} + \dots + d_{k}$ . So a number and its digit sum leave the same remainder on division by $9$ , and by $3$ too, since also $10 \equiv 1 (mod 3)$ . The digits of $123 456 789$ sum to $45$ , a multiple of $9$ , so $9$ divides it.

Modulo $11$ , instead, $10 \equiv - 1$ , so $10^{j} \equiv (- 1)^{j}$ , and a number is congruent modulo $11$ to its alternating digit sum $d_{0} - d_{1} + d_{2} - \dots$ , starting from the units. For $918 082$ this is $2 - 8 + 0 - 8 + 1 - 9 = - 22$ , so $11$ divides it, and indeed $918 082 = 11 \times 83 462$ .

Both tests give more than a yes or no: they give the remainder. The alternating sum of $123 456 789$ is $9 - 8 + 7 - 6 + 5 - 4 + 3 - 2 + 1 = 5$ , so it leaves remainder $5$ on division by $11$ .

Inverses and zero divisors

Addition in $ℤ_{n}$ can always be undone, since $[- a]$ cancels $[a]$ . Multiplication is another matter. A class $[a]$ has a multiplicative inverse if some $[x]$ has $[a] [x] = [1]$ , that is $a x \equiv 1 (mod n)$ . Modulo $7$ every non-zero class has one: $2 \times 4 = 8$ , $3 \times 5 = 15$ and $6 \times 6 = 36$ are all $\equiv 1$ . Modulo $10$ only $1, 3, 7, 9$ do.

Theorem. $[a]$ has an inverse modulo $n$ exactly when $\gcd (a, n) = 1$ .

The congruence $a x \equiv 1 (mod n)$ says $a x - 1 = n y$ for some integer $y$ , that is $a x + n (- y) = 1$ . So an inverse exists exactly when $1$ is an integer combination of $a$ and $n$ . If $\gcd (a, n) = 1$ , Bézout's identity supplies the combination. If $\gcd (a, n) = g > 1$ , then $g$ divides every combination $a x + n y$ and cannot divide $1$ . The proof is also the method: the $x$ from extended Euclid is the inverse. An earlier lesson found $13 \times 97 - 36 \times 35 = 1$ , which read modulo $97$ says $35 \times (- 36) \equiv 1$ , so the inverse of $35$ is $[- 36] = [61]$ . Check: $35 \times 61 = 2135 = 22 \times 97 + 1$ .

When $n = r s$ is composite, with $1 < r, s < n$ , then $[r] [s] = [0]$ although neither factor is $[0]$ , as in $2 \times 5 \equiv 0 (mod 10)$ . A non-zero class that multiplies some non-zero class to $[0]$ is a zero divisor, and it has no inverse: if $r a \equiv 0$ with $a$ not congruent to $0$ and $x r \equiv 1$ , then $a \equiv x r a \equiv 0$ . In fact, if $\gcd (a, n) = g > 1$ then $a \times \frac{n}{g} = \frac{a}{g} \times n \equiv 0$ , so every non-zero class is either invertible or a zero divisor, never both.

This is why cancellation is unsafe: $2 \times 3 \equiv 2 \times 8 (mod 10)$ , yet $3$ and $8$ are not congruent modulo $10$ . Cancelling $a$ is multiplying by its inverse, so it is allowed exactly when $\gcd (a, n) = 1$ . Modulo a prime $p$ every non-zero class is coprime to $p$ and so invertible: $ℤ_{p}$ allows division by anything non-zero, like the rationals. That is Euclid's lemma from the previous lesson in new clothes: modulo a prime, a product of non-zero classes is never zero.

Solving $a x \equiv b (mod n)$

A linear congruence $a x \equiv b (mod n)$ says $a x - n y = b$ for some integer $y$ , so it is solvable exactly when $b$ is a combination of $a$ and $n$ , which by Bézout means exactly when $g = \gcd (a, n)$ divides $b$ . When $g = 1$ there is one solution class, $x \equiv a^{- 1} b$ . When $g > 1$ and $g ∣ b$ , write $a = g a^{'}$ , $b = g b^{'}$ , $n = g n^{'}$ . Then $n ∣ a x - b$ exactly when $n^{'} ∣ a^{'} x - b^{'}$ , and since $\gcd (a^{'}, n^{'}) = 1$ that has one solution $x_{0}$ modulo $n^{'}$ . Modulo $n$ it splits into the $g$ classes $x_{0}, x_{0} + n^{'}, \dots, x_{0} + (g - 1) n^{'}$ .

Example. Solve $28 x \equiv 12 (mod 100)$ .

Here $\gcd (28, 100) = 4$ , which divides $12$ , so there are four solutions modulo $100$ . Dividing through gives $7 x \equiv 3 (mod 25)$ . For the inverse of $7$ run Euclid: $25 = 3 \times 7 + 4$ , $7 = 1 \times 4 + 3$ , $4 = 1 \times 3 + 1$ . Backwards, $1 = 4 - 3 = 2 \times 4 - 7 = 2 \times 25 - 7 \times 7$ , so $7^{- 1} \equiv - 7 \equiv 18 (mod 25)$ . Then $x \equiv 18 \times 3 = 54 \equiv 4 (mod 25)$ , and modulo $100$ the solutions are $4, 29, 54, 79$ . Check one: $28 \times 29 = 812 \equiv 12$ . By contrast $28 x \equiv 10 (mod 100)$ has no solution, since $4$ does not divide $10$ .

Now you. Solve $21 x \equiv 15 (mod 57)$ .

Answer

$\gcd (21, 57) = 3$ divides $15$ , so there are three solutions. Dividing by $3$ gives $7 x \equiv 5 (mod 19)$ . Since $7 \times 11 = 77 = 4 \times 19 + 1$ , the inverse of $7$ is $11$ , and $x \equiv 55 \equiv 17 (mod 19)$ . Modulo $57$ : $x \equiv 17, 36, 55$ . Check: $21 \times 17 = 357 = 6 \times 57 + 15$ .

The Chinese remainder theorem

The Sunzi Suanjing, a Chinese arithmetic manual written between the third and fifth centuries AD, asks: there are things whose number is unknown; counted by threes, two are left; by fives, three are left; by sevens, two are left. How many things? In congruences, find $x$ with $x \equiv 2 (mod 3)$ , $x \equiv 3 (mod 5)$ and $x \equiv 2 (mod 7)$ .

Theorem. If $n_{1}, \dots, n_{k}$ are pairwise coprime and $N = n_{1} n_{2} \dots n_{k}$ , then for any $a_{1}, \dots, a_{k}$ the system $x \equiv a_{i} (mod n_{i})$ has a solution, and it is unique modulo $N$ .

The proof builds the solution. Let $N_{i} = \frac{N}{n_{i}}$ , the product of the other moduli. It is coprime to $n_{i}$ , since a prime dividing both would divide some $n_{j}$ with $j \neq i$ as well as $n_{i}$ . So $N_{i}$ has an inverse $M_{i}$ modulo $n_{i}$ . Put

x = a_{1} N_{1} M_{1} + a_{2} N_{2} M_{2} + \dots + a_{k} N_{k} M_{k}

Modulo $n_{i}$ , every term except the $i$ th vanishes, since its $N_{j}$ contains the factor $n_{i}$ , while $N_{i} M_{i} \equiv 1$ , so $x \equiv a_{i}$ . For uniqueness, if $x$ and $x^{'}$ both work, then every $n_{i}$ divides $x - x^{'}$ . The $n_{i}$ share no prime, so by unique factorisation their product $N$ divides $x - x^{'}$ too.

Example. Solve Sunzi's problem.

$N = 105$ . For $n_{1} = 3$ : $N_{1} = 35 \equiv 2 (mod 3)$ , whose inverse is $2$ . For $n_{2} = 5$ : $N_{2} = 21 \equiv 1$ , inverse $1$ . For $n_{3} = 7$ : $N_{3} = 15 \equiv 1$ , inverse $1$ . So

x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233

and $233 - 2 \times 105 = 23$ . Check: $23 = 7 \times 3 + 2 = 4 \times 5 + 3 = 3 \times 7 + 2$ . So the answer is $23$ , as the Sunzi Suanjing says, or any $23 + 105 t$ .

Now you. Find the smallest positive $x$ with $x \equiv 3 (mod 5)$ , $x \equiv 4 (mod 7)$ and $x \equiv 5 (mod 11)$ .

Answer

$N = 385$ . $N_{1} = 77 \equiv 2 (mod 5)$ , inverse $3$ ; $N_{2} = 55 \equiv 6 (mod 7)$ , inverse $6$ ; $N_{3} = 35 \equiv 2 (mod 11)$ , inverse $6$ . Then $x = 3 \times 77 \times 3 + 4 \times 55 \times 6 + 5 \times 35 \times 6 = 693 + 1320 + 1050 = 3063$ , and $3063 - 7 \times 385 = 368$ . Check: $368 = 73 \times 5 + 3 = 52 \times 7 + 4 = 33 \times 11 + 5$ .

Coprimality matters. The system $x \equiv 1 (mod 4)$ , $x \equiv 2 (mod 6)$ has no solution, since the first makes $x$ odd and the second even. The theorem also counts: the $N$ classes modulo $N$ and the $N$ lists of remainders correspond one to one, so a number modulo $105$ is the same information as its three remainders modulo $3$ , $5$ and $7$ .

The ISBN check digit

Ten-digit International Standard Book Numbers, standardised in 1970, end in a check digit chosen so that, with the digits $d_{1}, \dots, d_{10}$ weighted $10$ down to $1$ ,

10 d_{1} + 9 d_{2} + 8 d_{3} + \dots + 2 d_{9} + d_{10} \equiv 0 (mod 11)

The second edition of Concrete Mathematics by Graham, Knuth and Patashnik has ISBN 0-201-55802-5, and the weighted sum is $0 + 18 + 0 + 7 + 30 + 25 + 32 + 0 + 4 + 5 = 121 = 11^{2}$ . A check digit of $10$ is printed as X.

A single wrong digit is always caught. Changing the digit with weight $w$ from $d$ to $d^{'}$ changes the sum by $w (d^{'} - d)$ , where $1 \leq w \leq 10$ and $d^{'} - d$ is non-zero and at most $10$ in size. Neither factor is a multiple of the prime $11$ , so by Euclid's lemma the product is not either, and the sum stops being $\equiv 0$ . Swapping two adjacent digits $a$ and $b$ , with weights $w$ and $w - 1$ , changes the sum by $w b + (w - 1) a - w a - (w - 1) b = b - a$ , again non-zero modulo $11$ when $a \neq b$ .

A composite modulus has zero divisors, and they let errors through. The thirteen-digit ISBN that replaced ISBN-10 on 1 January 2007 works modulo $10$ with weights alternating $1$ and $3$ , so swapping adjacent digits that differ by $5$ changes the sum by $2 \times 5 \equiv 0$ and goes unnoticed.

Powers repeat

Take powers of $3$ modulo $7$ : $3, 2, 6, 4, 5, 1$ , and then, since $3^{6} \equiv 1$ , the list starts again. Powers of $2$ go $2, 4, 1$ and repeat after three steps. Every sequence of powers modulo $n$ must eventually repeat, because there are only $n$ classes, but these return to $1$ , and the lengths $6$ and $3$ both divide $6 = 7 - 1$ . The next lesson explains the pattern with Fermat's little theorem and Euler's generalisation, computes huge powers by repeated squaring, and uses the inverses found here to build RSA, a lock anyone can close and only one person can open.

Fermat, Euler and RSA

Powers modulo a prime return to $1$ on a fixed rhythm, and the problem is to explain that rhythm well enough to compute enormous powers in a handful of steps and to build a secret code on them.

The previous lesson made remainders into a number system and ended by noticing that powers in it repeat. This lesson uses two of its results: $[a]$ has an inverse modulo $n$ exactly when $\gcd (a, n) = 1$ , found by running Euclid's algorithm backwards, and the Chinese remainder theorem, by which a number modulo $p q$ is determined by its remainders modulo $p$ and $q$ . It also uses Euler's totient $φ (n)$ from an earlier lesson, the count of integers from $1$ to $n$ coprime to $n$ (the letter $φ$ here is the totient again, not the golden ratio it stood for in the lesson on linear recurrences).

Powers modulo a prime

Here are the powers of every non-zero class modulo $7$ , each entry the previous one times $a$ , reduced.

$a$	$a^{1}$	$a^{2}$	$a^{3}$	$a^{4}$	$a^{5}$	$a^{6}$
1	1	1	1	1	1	1
2	2	4	1	2	4	1
3	3	2	6	4	5	1
4	4	2	1	4	2	1
5	5	4	6	2	3	1
6	6	1	6	1	6	1

The last column is all $1$ s: every $a$ not divisible by $7$ has $a^{6} \equiv 1 (mod 7)$ . And each row returns to $1$ for the first time after $1$ , $3$ , $6$ , $3$ , $6$ or $2$ steps, all divisors of $6$ . The powers of $2$ cycle through $2, 4, 1$ , while those of $3$ and $5$ pass through every non-zero class before coming home.

Modulo $11$ likewise $2^{10} = 1024 = 93 \times 11 + 1$ . For a composite the obvious analogue fails: $3^{9} = 19 683 \equiv 3 (mod 10)$ , not $1$ .

Fermat's little theorem

Pierre de Fermat stated the pattern, without proof, in a letter to Bernard Frénicle de Bessy dated 18 October 1640. Leibniz wrote one down in unpublished notes before 1683, and Euler published the first in 1736.

Theorem (Fermat). If $p$ is prime and $p$ does not divide $a$ , then $a^{p - 1} \equiv 1 (mod p)$ .

Consider the $p - 1$ numbers $a, 2 a, 3 a, \dots, (p - 1) a$ . None is $\equiv 0 (mod p)$ , since by Euclid's lemma a prime dividing $k a$ divides $k$ or $a$ , and it divides neither. No two are congruent either: if $i a \equiv j a$ , multiply both sides by the inverse of $a$ , which exists because $\gcd (a, p) = 1$ , to get $i \equiv j$ . So they are the classes $1, 2, \dots, p - 1$ in some order, and multiplying all of them together both ways gives

a \times 2 a \times \dots \times (p - 1) a \equiv 1 \times 2 \times \dots \times (p - 1) (mod p)

The left side is $a^{p - 1} (p - 1)!$ . Every factor of $(p - 1)!$ is coprime to $p$ , so $(p - 1)!$ is invertible modulo $p$ , and cancelling it leaves $a^{p - 1} \equiv 1$ . For $p = 7$ and $a = 3$ the products $3, 6, 9, 12, 15, 18$ reduce to $3, 6, 2, 5, 1, 4$ , a shuffle of $1$ to $6$ , exactly as the proof says.

Multiplying by $a$ gives $a^{p} \equiv a (mod p)$ , true for every integer $a$ , since when $p ∣ a$ both sides are $0$ . The converse is false. The composite $341 = 11 \times 31$ satisfies $2^{340} \equiv 1 (mod 341)$ , and $561 = 3 \times 11 \times 17$ satisfies $a^{560} \equiv 1$ for every $a$ coprime to it, the first of the numbers Robert Carmichael described in 1910. Failing the test does prove compositeness: $2^{90} \equiv 64 (mod 91)$ , so $91$ is not prime, and no factor was needed to show it.

Euler's generalisation

Modulo $10$ the powers of $3$ run $3, 9, 7, 1$ , back to $1$ after four steps, and $4 = φ (10)$ , counting $1, 3, 7, 9$ . Fermat's proof used only that multiplying by $a$ keeps the classes $1, \dots, p - 1$ distinct and non-zero, and that their product can be cancelled. Modulo a composite $n$ the classes coprime to $n$ behave the same way, and Euler saw in 1763 that the proof goes through.

Theorem (Euler). If $\gcd (a, n) = 1$ , then $a^{φ (n)} \equiv 1 (mod n)$ .

The proof is Fermat's with new classes. Let $r_{1}, \dots, r_{φ (n)}$ be the integers from $1$ to $n$ coprime to $n$ . Each $a r_{i}$ is coprime to $n$ too, since a prime dividing $n$ and $a r_{i}$ would divide $a$ or $r_{i}$ . The products are distinct modulo $n$ , since $a$ is invertible. So they are the $r_{i}$ reshuffled, and multiplying everything gives $a^{φ (n)} R \equiv R$ , where $R$ is the product of the $r_{i}$ . Being coprime to $n$ , $R$ cancels. Modulo $10$ with $a = 3$ , the products $3, 9, 21, 27$ reduce to $3, 9, 1, 7$ , the same four classes shuffled.

For a prime, $φ (p) = p - 1$ and Euler's theorem is Fermat's. The formula from inclusion and exclusion, $φ (n) = n$ times $1 - \frac{1}{p}$ for each prime $p$ dividing $n$ , supplies the exponent: $φ (100) = 100 \times \frac{1}{2} \times \frac{4}{5} = 40$ , and for distinct primes $φ (p q) = (p - 1) (q - 1)$ .

The hypothesis $\gcd (a, n) = 1$ cannot be dropped: powers of $2$ are even, so none is $\equiv 1 (mod 10)$ . And $φ (n)$ is an exponent that always works, not always the smallest: modulo $100$ , $3^{20}$ is already $\equiv 1$ .

Reducing huge exponents

If $a^{m} \equiv 1 (mod n)$ , powers of $a$ repeat with period $m$ : writing $k = m q + s$ with $0 \leq s < m$ gives

a^{k} = (a^{m})^{q} a^{s} \equiv 1^{q} a^{s} = a^{s} (mod n)

Euler's theorem always provides such an $m$ , namely $φ (n)$ . The base is reduced modulo $n$ and the exponent modulo $φ (n)$ , and confusing the two is the commonest error here.

The last digit of a number is its remainder modulo $10$ . For $3^{2026}$ , with $φ (10) = 4$ and $2026 = 4 \times 506 + 2$ , the last digit is that of $3^{2}$ , which is $9$ .

Example. Find the last two digits of $3^{2026}$ .

Work modulo $100$ , where $\gcd (3, 100) = 1$ and $φ (100) = 40$ . Since $2026 = 40 \times 50 + 26$ , the task is $3^{26} (mod 100)$ . Build it up: $3^{5} = 243 \equiv 43$ , then $3^{10} \equiv 43^{2} = 1849 \equiv 49$ , then $3^{20} \equiv 49^{2} = 2401 \equiv 1$ . So in fact the period is $20$ , and $3^{26} \equiv 3^{6} = 729 \equiv 29$ . The last two digits are $29$ .

Now you. Find the last two digits of $13^{2026}$ .

Answer

Again reduce the exponent modulo $40$ : the task is $13^{26} (mod 100)$ . Then $13^{2} = 169 \equiv 69$ , $13^{4} \equiv 69^{2} = 4761 \equiv 61$ , $13^{5} \equiv 61 \times 13 = 793 \equiv 93$ , $13^{10} \equiv 93^{2} = 8649 \equiv 49$ and $13^{20} \equiv 49^{2} \equiv 1$ . So $13^{26} \equiv 13^{6} = 13^{4} \times 13^{2} \equiv 61 \times 69 = 4209 \equiv 9$ , and the last two digits are $09$ .

Repeated squaring

Reducing the exponent needs $φ (n)$ , and RSA needs $a^{k} (mod n)$ with $k$ hundreds of digits long, and multiplying by $a$ one step at a time would take $k - 1$ multiplications, more than there are atoms in the universe. Squaring doubles the exponent with each multiplication, $a^{2}$ , $a^{4} = (a^{2})^{2}$ , $a^{8}$ and so on, reduced modulo $n$ each time. Any exponent is a sum of powers of $2$ , its binary expansion, so multiply together the squares matching its $1$ bits.

An exponent with $b$ binary digits needs $b - 1$ squarings, and if it has $w$ ones, $w - 1$ further multiplications to combine them: at most $2 (b - 1)$ in all. For a $2048$ bit exponent, around $10^{616}$ in size, that is at most $4094$ multiplications.

Example. Compute $3^{100} (mod 101)$ by repeated squaring, and count the multiplications.

In binary $100 = 1100100_{2} = 64 + 32 + 4$ . Square six times, reducing modulo $101$ : $3^{2} = 9$ , $3^{4} = 81$ , $3^{8} \equiv 81^{2} = 6561 \equiv 97$ , $3^{16} \equiv 97^{2} \equiv (- 4)^{2} = 16$ , $3^{32} \equiv 256 \equiv 54$ , $3^{64} \equiv 54^{2} = 2916 \equiv 88$ . Then combine: $3^{64} \times 3^{32} \equiv 88 \times 54 = 4752 \equiv 5$ , and $5 \times 3^{4} = 405 \equiv 1$ . So $3^{100} \equiv 1$ , in $6 + 2 = 8$ multiplications instead of $99$ , as Fermat predicts for the prime $101$ .

Now you. Compute $5^{45} (mod 101)$ by repeated squaring, and count the multiplications.

Answer

$45 = 101101_{2} = 32 + 8 + 4 + 1$ . The squares are $5^{2} = 25$ , $5^{4} = 625 \equiv 19$ , $5^{8} \equiv 361 \equiv 58$ , $5^{16} \equiv 3364 \equiv 31$ , $5^{32} \equiv 961 \equiv 52$ . Then $52 \times 58 = 3016 \equiv 87$ , $87 \times 19 = 1653 \equiv 37$ and $37 \times 5 = 185 \equiv 84$ . So $5^{45} \equiv 84$ , in $5 + 3 = 8$ multiplications.

The RSA cryptosystem

Every cipher before 1976 needed a key agreed in secret, since whoever could lock could unlock. That year Whitfield Diffie and Martin Hellman proposed separating the two: a public key anyone can use to encrypt, and a private key that only its owner uses to decrypt. Ron Rivest, Adi Shamir and Leonard Adleman at MIT found a way to do it in 1977, named RSA from their initials. Clifford Cocks at GCHQ, the British signals intelligence agency, had found the same system in 1973, but it stayed classified until 1997.

To make keys, choose two primes $p$ and $q$ and let $n = p q$ , so $φ (n) = (p - 1) (q - 1)$ . Choose an exponent $e$ coprime to $φ (n)$ , and compute its inverse $d$ modulo $φ (n)$ with extended Euclid, so that $e d \equiv 1 (mod φ (n))$ . Publish $(n, e)$ and keep $d$ secret. A message is a number $0 \leq m < n$ . Anyone encrypts it as $c \equiv m^{e} (mod n)$ , and the key holder decrypts by computing $c^{d} (mod n)$ , which will turn out to be $m$ .

The classic small key takes $p = 61$ and $q = 53$ . Then $n = 3233$ and $φ (n) = 60 \times 52 = 3120$ . Take $e = 17$ , which is prime and does not divide $3120$ . Euclid's algorithm runs $3120 = 183 \times 17 + 9$ , $17 = 1 \times 9 + 8$ , $9 = 1 \times 8 + 1$ , and backwards

1 = 9 - 8 = 2 \times 9 - 17 = 2 \times 3120 - 367 \times 17

so $17^{- 1} \equiv - 367 \equiv 2753 (mod 3120)$ . Check: $17 \times 2753 = 46 801 = 15 \times 3120 + 1$ . The public key is $(3233, 17)$ and the private key is $d = 2753$ .

Example. Encrypt the message $m = 65$ with the public key $(3233, 17)$ , and decrypt it.

Here $17 = 10001_{2} = 16 + 1$ , so square four times modulo $3233$ : $65^{2} = 4225 \equiv 992$ , $65^{4} \equiv 992^{2} \equiv 1232$ , $65^{8} \equiv 1232^{2} \equiv 1547$ and $65^{16} \equiv 1547^{2} \equiv 789$ . Then $c \equiv 789 \times 65 = 51 285 \equiv 2790$ , in five multiplications. Decryption computes $2790^{2753} (mod 3233)$ . In binary $2753 = 101011000001_{2}$ , twelve digits with five ones, so it takes $11$ squarings and $4$ multiplications, and the result is $65$ again.

Now you. Build a key from $p = 7$ and $q = 13$ with $e = 5$ . Find $d$ , encrypt $m = 10$ , and decrypt the result.

Answer

$n = 91$ and $φ (n) = 72$ . Euclid gives $72 = 14 \times 5 + 2$ and $5 = 2 \times 2 + 1$ , so $1 = 5 - 2 \times (72 - 14 \times 5) = 29 \times 5 - 2 \times 72$ and $d = 29$ . To encrypt: $10^{2} = 100 \equiv 9$ , $10^{4} \equiv 81$ , $10^{5} \equiv 810 \equiv 82$ , so $c = 82$ . To decrypt, $29 = 16 + 8 + 4 + 1$ and the squares of $82$ are $82^{2} \equiv 81$ , $82^{4} \equiv 9$ , $82^{8} \equiv 81$ , $82^{16} \equiv 9$ . Then $9 \times 81 = 729 \equiv 1$ , $1 \times 9 = 9$ and $9 \times 82 = 738 \equiv 10$ , the message.

Why decryption works

Since $e d \equiv 1 (mod φ (n))$ , write $e d = 1 + k φ (n)$ for some integer $k \geq 0$ . Decrypting computes $c^{d} \equiv (m^{e})^{d} = m^{e d}$ , and when $\gcd (m, n) = 1$ Euler's theorem finishes it:

m^{e d} = m \times {(m^{φ (n)})}^{k} \equiv m \times 1^{k} = m (mod n)

Since $0 \leq m < n$ , the remainder is $m$ itself. For the key above, $e d = 46 801 = 1 + 15 \times 3120$ .

If $m$ shares a factor with $n$ , Euler's theorem says nothing, and the Chinese remainder theorem steps in: check modulo $p$ and $q$ separately. Suppose $p ∣ m$ but $q$ does not. Modulo $p$ both $m^{e d}$ and $m$ are $0$ . Modulo $q$ , Fermat gives $m^{q - 1} \equiv 1$ , and $e d = 1 + k (p - 1) (q - 1)$ , so $m^{e d} = m \times (m^{q - 1})^{k (p - 1)} \equiv m$ . The two numbers agree modulo $p$ and modulo $q$ , so by the uniqueness half of the theorem they agree modulo $p q = n$ . (If both primes divide $m$ , then $m = 0$ .) With the key above, $m = 61$ encrypts to $610$ , and $610^{2753} \equiv 61 (mod 3233)$ .

Secure only while factoring is hard

An attacker sees $n$ , $e$ and $c$ . The route to $d$ is through $φ (n)$ , and finding $φ (n)$ is exactly as hard as factoring $n$ . The primes give $(p - 1) (q - 1)$ , and conversely $φ (n) = p q - (p + q) + 1$ , so knowing it gives $p + q = n - φ (n) + 1$ , and with $p q = n$ the primes are the roots of $t^{2} - (p + q) t + n = 0$ . For the toy key, $p + q = 3233 - 3120 + 1 = 114$ , and $t^{2} - 114 t + 3233 = 0$ has roots $61$ and $53$ .

Multiplying two primes takes an instant, and no known method on an ordinary computer undoes it in time polynomial in the number of digits. That asymmetry is the whole lock. The best general method, the number field sieve, factored RSA-250, a 250 digit (829 bit) challenge number, in February 2020, after roughly 2700 core-years of computation by Fabrice Boudot, Paul Zimmermann and four colleagues. Recommended keys are $2048$ bits and up, $617$ digits or more, far beyond that reach. Nobody has proved that factoring is hard, so the security is an empirical bet, and in 1994 Peter Shor gave an algorithm that factors in polynomial time on a large quantum computer, which no machine built so far is anywhere near big enough to run.

The integers are one kind of discrete structure, rich enough to protect the traffic of the internet. Another is the network (cities and roads, bridges over a river, people and friendships), where all that matters is what is joined to what, and the next lesson models it with graphs.

Graphs

Whether a walk through a city can cross each of its bridges exactly once depends only on which pieces of land each bridge joins, and the problem is to find a language in which questions like that can be stated precisely and then settled by proof.

The previous lesson ended with the integers as one kind of discrete structure. Networks are another (cities and roads, computers and cables, people and friendships), and in them only what is joined to what matters. The object that keeps exactly that information is a graph. Algorithms and Data Structures shows how to store and search one; this lesson proves what is true of every graph, using two ideas from Proof and Logic: bijections, and equivalence relations, which cut a set into disjoint classes.

Vertices and edges

A simple graph $G = (V, E)$ is a finite set $V$ of vertices together with a set $E$ of edges, where each edge is a two element subset ${u, v}$ of $V$ . Two vertices joined by an edge are adjacent, or neighbours, and the edge is incident to both. A graph is fully described by its edge list: ${1, 2}, {2, 3}, {3, 1}, {3, 4}$ is a triangle with a tail.

The complete graph $K_{n}$ has $n$ vertices and every possible edge, so it has $(\binom{n}{2}) = \frac{n (n - 1)}{2}$ edges: a round robin tournament among $20$ football clubs is $K_{20}$ with $190$ edges. The cycle $C_{n}$ has vertices $1, \dots, n$ and edges ${1, 2}, {2, 3}, \dots, {n, 1}$ . The complete bipartite graph $K_{m, n}$ has $m$ vertices on one side and $n$ on the other, and every edge joining the two sides, so $m n$ edges. A multigraph also allows several edges between the same two vertices (and loops), so that two bridges between the same banks stay two edges. The river problem needs this; otherwise "graph" means simple graph.

Degree and the handshake lemma

The degree $\deg (v)$ of a vertex is the number of edges incident to it. In $K_{n}$ every vertex has degree $n - 1$ ; in $C_{n}$ every vertex has degree $2$ ; in the triangle with a tail the degrees are $2, 2, 3, 1$ . A graph in which every vertex has the same degree $k$ is $k$ -regular.

Handshake lemma. In any graph, $\sum_{v \in V} \deg (v) = 2 | E |$ .

Count, in two ways, the pairs $(v, e)$ with $e$ an edge incident to the vertex $v$ . Vertex $v$ is in $\deg (v)$ of them, giving the sum on the left; each edge has two ends and is in two of them, giving $2 | E |$ . In the triangle with a tail, $2 + 2 + 3 + 1 = 8 = 2 \times 4$ . At a party, summing the handshakes of every guest counts each handshake twice, hence the name.

Corollary. Every graph has an even number of vertices of odd degree.

The even degrees sum to an even number, so the odd degrees must too, which takes an even number of them. At any party, the number of guests who shook an odd number of hands is even. A degree list with an odd sum belongs to no graph, but an even sum is not enough: no simple graph has degrees $3, 3, 1, 1$ , since on four vertices each vertex of degree $3$ is adjacent to every other, giving the last two degree at least $2$ .

Example. A lab wants to cable $15$ computers so that each is connected directly to exactly $3$ others. Can it be done? And if each is to be connected to exactly $4$ others, how many cables are needed?

With every degree $3$ the degree sum would be $15 \times 3 = 45$ , which is odd, but it must equal $2 | E |$ , so no such network exists. With every degree $4$ the sum is $60$ , so $30$ cables, and a ring joining each computer to the two nearest on either side achieves it.

Now you. A graph has $9$ edges and every vertex has degree $3$ . How many vertices does it have? Could a graph have exactly $7$ vertices, all of degree $3$ ?

Answer

The degree sum is $2 \times 9 = 18$ , and it is also $3 n$ , so $n = 6$ . For $7$ vertices of degree $3$ the sum would be $21$ , which is odd, so no such graph exists.

Isomorphism

The edge list ${a, c}, {c, e}, {e, b}, {b, d}, {d, a}$ draws as a five pointed star, yet renaming $a, c, e, b, d$ as $1, 2, 3, 4, 5$ turns it into exactly $C_{5}$ . Two graphs $G$ and $H$ are isomorphic if there is a bijection $f$ from the vertices of $G$ to the vertices of $H$ such that ${u, v}$ is an edge of $G$ exactly when ${f (u), f (v)}$ is an edge of $H$ . It is a renaming, and isomorphic graphs are, for every question here, the same graph.

Showing two graphs are isomorphic takes one bijection, checked edge by edge. Showing they are not means ruling out all $n!$ bijections at once, and the tool is an invariant, a property every isomorphism preserves: the numbers of vertices and edges, the list of degrees (neighbours of $v$ go one to one onto neighbours of $f (v)$ ), the number of triangles. If one invariant differs, the graphs are not isomorphic; if the ones you tried agree, nothing follows.

Example. The prism $P$ has vertices $a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}$ and edges forming the triangles $a_{1} a_{2} a_{3}$ and $b_{1} b_{2} b_{3}$ together with ${a_{1}, b_{1}}, {a_{2}, b_{2}}, {a_{3}, b_{3}}$ . Show that $P$ is not isomorphic to $K_{3, 3}$ .

The obvious invariants agree: both graphs have $6$ vertices and $9$ edges, and both are $3$ -regular. The prism contains a triangle, $a_{1} a_{2} a_{3}$ . The graph $K_{3, 3}$ contains none: every edge crosses from one side to the other, so any closed route alternates sides and has even length, and a triangle would need three. An isomorphism would carry the prism's triangle to a triangle in $K_{3, 3}$ , so no isomorphism exists.

Now you. Let $G$ be the hexagon $C_{6}$ on vertices $1, \dots, 6$ with the extra edge ${1, 4}$ , and let $H$ be $C_{6}$ with the extra edge ${1, 3}$ . Check that the vertex counts, edge counts and degree lists agree, then show that $G$ and $H$ are not isomorphic.

Answer

Both have $6$ vertices and $7$ edges, and both have degrees $3, 3, 2, 2, 2, 2$ . The graph $H$ contains the triangle $1, 2, 3$ . The graph $G$ has none: no two neighbours of any vertex are adjacent (those of $1$ are $2, 4, 6$ , those of $4$ are $1, 3, 5$ ). So they are not isomorphic.

Walks, paths and connectedness

A walk is a sequence of vertices $v_{0}, v_{1}, \dots, v_{k}$ in which each consecutive pair is an edge; it has length $k$ , the number of edges used, and it is closed if $v_{k} = v_{0}$ . A trail is a walk that uses no edge twice, and a path is a walk that repeats no vertex. A cycle is a closed walk of length at least $3$ whose vertices are distinct apart from the return to the start.

A walk from $u$ to $v$ always contains a path from $u$ to $v$ : in a shortest such walk, a repeat $v_{i} = v_{j}$ with $i < j$ could be cut out to leave a shorter walk, so there is none.

Write $u \sim v$ when there is a walk from $u$ to $v$ . This is an equivalence relation: reflexive by the walk of length $0$ , symmetric because a walk read backwards is a walk, and transitive because a walk from $u$ to $v$ followed by one from $v$ to $w$ is a walk from $u$ to $w$ . Two paths joined end to end may meet and stop being a path, which is why the relation uses walks.

The equivalence classes of $\sim$ are the connected components of the graph. Equivalence classes partition a set, so every vertex lies in exactly one component, and no edge joins two components, since its ends are related. A graph is connected if it has exactly one component. The graph with edges ${1, 2}, {2, 3}, {4, 5}$ on vertices $1, \dots, 6$ has three components, ${1, 2, 3}$ , ${4, 5}$ and ${6}$ .

Deleting an edge that lies on a cycle never disconnects a graph. If ${x, y}$ lies on a cycle, the rest of the cycle is a path from $x$ to $y$ , and any walk that used the edge can take that detour instead.

The bridges of Königsberg

Königsberg, in Prussia (now Kaliningrad), stood where the river Pregel flows round the island of Kneiphof, and seven bridges joined its four land masses. Could a walk cross every bridge exactly once? Leonhard Euler answered in a paper presented to the St Petersburg Academy in 1735 and printed in its volume for 1736, Solutio problematis ad geometriam situs pertinentis.

Euler labelled the island $A$ , the north and south banks $B$ and $C$ , and the eastern land between the two arms of the river $D$ . Two bridges joined $A$ to $B$ , two joined $A$ to $C$ , and one each joined $A$ to $D$ , $B$ to $D$ and $C$ to $D$ . With a vertex per land mass and an edge per bridge, this multigraph has degrees

\deg (A) = 5, \deg (B) = 3, \deg (C) = 3, \deg (D) = 3

and the handshake lemma checks the count: $5 + 3 + 3 + 3 = 14 = 2 \times 7$ .

Euler's multigraph of Königsberg: the island A, the north and south banks B and C, and the eastern land D, with one edge per bridge. Two edges join A to each bank, and single edges join D to A, B and C, so A has degree 5 and the other three have degree 3.

Euler's argument was a count. A route crossing all seven bridges passes through a sequence of eight land masses. A land mass with $k$ bridges, $k$ odd, must appear in that sequence $\frac{k + 1}{2}$ times, since every visit except possibly the first or last uses up two of its bridges. So $A$ appears $3$ times and each of $B$ , $C$ , $D$ appears $2$ times, which is $9$ appearances in a sequence of $8$ . No such walk exists. Euler saw that only the parity of the degrees mattered and stated the general rule, but the proof that the right parities guarantee a walk came 137 years later.

Euler's theorem

An Euler trail uses every edge of the graph, and an Euler circuit is a closed one.

Theorem. A connected multigraph has an Euler circuit exactly when every vertex has even degree. It has an Euler trail that is not closed exactly when it has exactly two vertices of odd degree, and then every such trail starts at one of them and ends at the other.

Necessity. Each pass of an Euler circuit through a vertex arrives along one edge and leaves along another, and the first departure pairs with the final arrival. Every edge is used once, so the edges at each vertex split into pairs and every degree is even. On a trail from $u$ to $v \neq u$ the first edge at $u$ and the last at $v$ are left unpaired, so exactly $u$ and $v$ are odd. Königsberg, with four odd vertices, has neither.

Sufficiency. Suppose every degree is even. Start at a vertex $v$ and walk, never reusing an edge, until stuck. Arriving at any $w \neq v$ , the walk has used an odd number of edges at $w$ (a pair per earlier pass plus the one just used), and $\deg (w)$ is even, so it can leave again. So it gets stuck only at $v$ , as a closed trail $T$ . If $T$ misses some edges, some vertex $u$ of $T$ has an unused edge, since otherwise nothing would join $T$ to the unused edges and the graph would be disconnected. The unused edges still have even degree at every vertex, because $T$ used an even number at each, so the same argument builds a closed trail $T^{'}$ from $u$ out of them. Splice it in: follow $T$ to $u$ , go round $T^{'}$ , finish $T$ . The closed trail is longer, and repeating uses every edge. This is Carl Hierholzer's argument, published in 1873, two years after his death.

For two odd vertices $u$ and $v$ , add a new edge ${u, v}$ (a multigraph allows it). Every degree is now even, so there is an Euler circuit, and deleting the new edge from it leaves an Euler trail between $u$ and $v$ .

Example. Find an Euler circuit of $K_{5}$ .

Every degree is $4$ , so one exists. Start at $1$ and walk $1, 2, 3, 1$ until stuck. Vertex $1$ has unused edges, so walk from it: $1, 4, 2, 5, 1$ . Splice at $1$ to get $1, 4, 2, 5, 1, 2, 3, 1$ . The edges ${3, 4}, {4, 5}, {5, 3}$ remain, forming the closed trail $3, 4, 5, 3$ , and vertex $3$ is on the circuit, so splice at $3$ :

1, 4, 2, 5, 1, 2, 3, 4, 5, 3, 1

That is ten edges, all different, and $K_{5}$ has $(\binom{5}{2}) = 10$ .

Now you. German children draw das Haus vom Nikolaus in one stroke without lifting the pen. It is the graph with edges ${1, 2}, {2, 3}, {3, 4}, {4, 1}, {1, 3}, {2, 4}, {3, 5}, {4, 5}$ : a square with both diagonals and a roof. Where must the drawing start, and what is one way to draw it?

Answer

The degrees are $\deg (1) = 3$ , $\deg (2) = 3$ , $\deg (3) = 4$ , $\deg (4) = 4$ , $\deg (5) = 2$ . Exactly two are odd, so an Euler trail exists and it must start at $1$ or $2$ and end at the other. One is $1, 2, 3, 4, 1, 3, 5, 4, 2$ , which uses all eight edges once.

Hamilton's question

Change one word: instead of every edge once, ask for a cycle through every vertex once. Such a cycle is a Hamilton cycle, after William Rowan Hamilton, who in 1857 invented the icosian game: find a route along the edges of a dodecahedron through all twenty of its corners, returning to the start. He sold it to a London games maker in 1859 for £25. The puzzle is not hard, but the question behind it has never been answered as Euler answered his.

Euler's criterion is one pass over the degrees. Deciding whether a graph has a Hamilton cycle is NP-complete (one of Richard Karp's 1972 list), so no efficient test is known, and finding one would settle the P versus NP problem. What exists instead are sufficient conditions.

Dirac's theorem (1952). A simple graph with $n \geq 3$ vertices in which every vertex has degree at least $\frac{n}{2}$ has a Hamilton cycle.

The bound cannot be lowered. Take $K_{k, k + 1}$ , with $n = 2 k + 1$ vertices and smallest degree $k$ , just below $\frac{n}{2}$ . A cycle alternates sides, so it visits equally many vertices on each, and cannot visit all $k + 1$ on the larger side. The condition is also far from necessary: $C_{100}$ is itself a Hamilton cycle, with every degree $2$ .

Cycles are where the difficulty lives, and they are also what a connected graph can spare: since deleting an edge on a cycle never disconnects a graph, any connected graph can be stripped, one cycle edge at a time, to a connected graph with no cycles at all. Those are the simplest connected graphs, and the next lesson studies them as trees.

Trees

A connected graph with no cycles is the leanest way to join a set of points, and the problem is to recognise such graphs and count them.

The previous lesson set up the language. Graphs here are simple (no loops or repeated edges), and by the handshake lemma the degrees (edge counts at each vertex) sum to twice the number of edges. A path is a sequence of distinct vertices each joined to the next, a cycle is a path of at least three vertices whose ends are also joined, and a graph is connected when every two vertices are joined by a path. That lesson ended on the simplest connected graphs, the ones without cycles.

Trees, forests and leaves

A tree is a connected graph with no cycles. A graph with no cycles, connected or not, is a forest, and its connected pieces are trees. A leaf is a vertex of degree $1$ . On ${1, 2, 3, 4, 5}$ the edges $12$ , $13$ , $34$ and $35$ form a tree with leaves $2$ , $4$ and $5$ .

Theorem. Every tree with at least two vertices has at least two leaves.

Take a longest path $v_{0}, v_{1}, \dots, v_{k}$ in the tree. One exists because the graph is finite, and $k \geq 1$ because a connected graph on two or more vertices has an edge. Suppose $v_{0}$ had a neighbour $w$ other than $v_{1}$ . If $w = v_{i}$ for some $i \geq 2$ , then $v_{0}, v_{1}, \dots, v_{i}$ is a cycle, which a tree does not have. If $w$ is off the path, then $w, v_{0}, \dots, v_{k}$ is a longer path, contradicting the choice. So $v_{0}$ is a leaf, and by the same argument so is $v_{k}$ , a different vertex.

A path on $n$ vertices has exactly two leaves, so the bound is sharp; a star, one centre joined to all the others, has $n - 1$ .

Every tree has n - 1 edges

If $v$ is a leaf of a tree $T$ , then $T - v$ ( $T$ with $v$ and its edge deleted) is still a tree. Deleting creates no cycle, and a path between two other vertices never passes through $v$ , since an interior vertex of a path has two neighbours and $v$ has one.

Theorem. A tree with $n$ vertices has exactly $n - 1$ edges.

By induction on $n$ , starting from one vertex and no edges. If trees on $n - 1$ vertices have $n - 2$ edges, a tree $T$ on $n \geq 2$ vertices has a leaf, and removing it takes one edge and leaves a tree on $n - 1$ vertices. So $T$ has $n - 1$ edges.

Adding over components, a forest with $n$ vertices and $c$ components has $n - c$ edges. And since a tree's degrees sum to $2 n - 2$ , averaging just under $2$ , every vertex of degree above $2$ must be paid for by leaves.

Example. A tree has one vertex of degree $4$ , two of degree $3$ , and every other vertex is a leaf. How many leaves does it have?

With $L$ leaves there are $n = 3 + L$ vertices and $2 + L$ edges. The degree sum is $4 + 3 + 3 + L = 10 + L$ , and it equals $2 (2 + L) = 4 + 2 L$ , so $L = 6$ . In general the same algebra gives $L = 2 + \sum (d - 2)$ over the vertices of degree $d \geq 3$ , here $2 + 2 + 1 + 1 = 6$ .

Now you. A tree has one vertex of degree $5$ , two of degree $3$ , one of degree $2$ , and every other vertex is a leaf. How many leaves does it have, and how many vertices?

Answer

$7$ leaves and $11$ vertices. The degree sum is $13 + L$ and there are $3 + L$ edges, so $13 + L = 6 + 2 L$ and $L = 7$ . The shortcut agrees: $2 + 3 + 1 + 1 + 0 = 7$ .

Five ways to say tree

For a graph $G$ on $n$ vertices, these are equivalent: (1) $G$ is connected and acyclic; (2) $G$ is connected with $n - 1$ edges; (3) $G$ is acyclic with $n - 1$ edges; (4) every two vertices are joined by exactly one path; (5) $G$ is minimally connected, meaning connected but disconnected by deleting any one edge. The proofs link each to the definition, (1), in both directions.

One fact does much of the work: deleting an edge $x y$ that lies on a cycle never disconnects a graph, because any path that used $x y$ can detour from $x$ to $y$ the long way round the cycle.

(1) gives (2) and (3) by the edge count. For (3) to (1): an acyclic graph is a forest, so with $c$ components it has $n - c$ edges, and $n - c = n - 1$ forces $c = 1$ . For (2) to (1): if $G$ is connected with $n - 1$ edges, delete edges on cycles, one at a time, until none remain. The graph stays connected, so it ends as a tree on $n$ vertices with $n - 1$ edges; it started with $n - 1$ , so nothing was deleted and $G$ had no cycle.

(1) gives (4). There is a path from $u$ to $v$ ; if there were two, $P$ and $Q$ , let $x$ be the last vertex before they part, and $y$ the first vertex after $x$ on $P$ that lies on $Q$ again (both end at $v$ , so there is one). The stretches of $P$ and $Q$ between $x$ and $y$ meet only at their ends and form a cycle. Conversely, a graph satisfying (4) is connected, and has no cycle, since a cycle through $u$ and $v$ would offer two paths between them, one each way round.

(1) gives (5): if deleting $u v$ from a tree left $u$ and $v$ joined by a path, that path plus $u v$ would be a cycle. Conversely (5) gives (1), since by the fact above a graph with a cycle has an edge whose deletion keeps it connected.

A graph on $n$ vertices is thus a tree once it passes any two of three tests: connected, acyclic, $n - 1$ edges.

Spanning trees

A spanning tree of a graph $G$ is a subgraph that is a tree and contains every vertex of $G$ .

Theorem. Every connected graph has a spanning tree.

While the graph has a cycle, delete an edge of that cycle. The graph stays connected, by the fact above, and keeps every vertex, and since edges run out the process stops at a spanning tree. So a connected graph with $n$ vertices and $m$ edges has $m \geq n - 1$ , and reaching a spanning tree takes exactly $m - n + 1$ deletions, whichever cycles are broken. Finding the cheapest one when edges carry costs is an algorithmic question, answered in Algorithms and Data Structures; the question here is how many there are.

Cayley's formula

A labelled tree on ${1, \dots, n}$ is a tree with those vertices, two counting as different when their edge sets differ: the paths $1, 2, 3$ and $2, 1, 3$ are different. They are the spanning trees of the complete graph $K_{n}$ , in which every pair is joined.

For $n = 2$ there is one, the edge $12$ . For $n = 3$ a tree is a path fixed by its middle vertex, so there are three. For $n = 4$ there are two shapes. A star is fixed by its centre, giving $4$ . A path on four vertices is one of the $4! = 24$ orderings, each read in both directions, giving $12$ . That makes $16$ . A second count confirms it: by characterisation (3), three of the $6$ edges of $K_{4}$ form a tree unless they are one of the $4$ triangles, leaving $(\binom{6}{3}) - 4 = 16$ .

The counts $1, 3, 16$ are $2^{0}$ , $3^{1}$ and $4^{2}$ . Carl Wilhelm Borchardt proved in 1860, via a determinant, that the pattern continues, and Arthur Cayley stated it in 1889 in "A theorem on trees".

Cayley's formula. There are $n^{n - 2}$ labelled trees on $n$ vertices.

Example. Count the labelled trees on ${1, \dots, 5}$ by shape, and compare with $5^{3} = 125$ .

The five degrees are each at least $1$ and sum to $8$ , so their excess over $1$ is $3$ , split as $3$ , as $2 + 1$ or as $1 + 1 + 1$ . The degree sequences are $4, 1, 1, 1, 1$ (a star: $5$ trees, one per centre), $2, 2, 2, 1, 1$ (a path: $\frac{5!}{2} = 60$ ) and $3, 2, 1, 1, 1$ . In the last, the degree $2$ vertex must neighbour the degree $3$ one, or those would lie in separate components. Choose the degree $3$ vertex ( $5$ ways), its degree $2$ neighbour ( $4$ ways) and the leaf hanging from that neighbour ( $3$ ways): $60$ . The total is $5 + 60 + 60 = 125$ .

Now you. Delete the edge $12$ from $K_{4}$ . How many spanning trees does the remaining graph have?

Answer

$8$ . The $16$ trees have $3$ edges each, $48$ in all, and the $6$ edges of $K_{4}$ are alike under relabelling, so each lies in $\frac{48}{6} = 8$ trees. The other $8$ avoid $12$ .

Prüfer's code

The number $n^{n - 2}$ counts the sequences of length $n - 2$ with entries from ${1, \dots, n}$ , and Heinz Prüfer found a bijection with them in 1918. To encode a labelled tree, repeat while more than two vertices remain: remove the leaf with the smallest label, and write down the label of its neighbour.

The code records degrees. A vertex $v$ is written once for each neighbour removed as a leaf, and it keeps exactly one neighbour to the end (when it is removed itself, or as one of the final two), so it appears $\deg (v) - 1$ times. The leaves are precisely the labels missing from the code.

So the first vertex removed is the smallest label missing from the code, its neighbour is the first entry, and the rest of the code is the code of the smaller tree. Decoding therefore runs: for each entry in turn, join it to the smallest label not yet crossed off and not among the entries still to come, and cross that label off; finally join the two labels left over. A tree is determined by its code.

Every sequence is a code, by induction on $n$ . For $n = 2$ the empty sequence codes the single edge. Given $a_{1}, \dots, a_{n - 2}$ , let $b$ be the smallest label missing from it. By induction $a_{2}, \dots, a_{n - 2}$ is the code of a tree $T^{'}$ on the other $n - 1$ labels; attach $b$ to $a_{1}$ . The leaves of the new tree are the labels missing from the whole sequence, so encoding removes $b$ first, writes $a_{1}$ , and continues as for $T^{'}$ . So encoding is a bijection, which proves Cayley's formula.

Example. Encode the tree on ${1, \dots, 7}$ with edges $16$ , $24$ , $34$ , $46$ , $56$ , $67$ , then decode the result.

The leaves are $1, 2, 3, 5, 7$ . Remove $1$ and write $6$ ; remove $2$ , write $4$ ; remove $3$ , write $4$ . Now $4$ is a leaf, and the smallest: remove it, write $6$ . Remove $5$ , write $6$ . Vertices $6$ and $7$ remain, and the code is $6, 4, 4, 6, 6$ : vertex $6$ , of degree $4$ , appears three times. To decode, $1$ is the smallest label missing from the code: join it to $6$ . With $4, 4, 6, 6$ to come, join $2$ to $4$ , then $3$ to $4$ . With $6, 6$ to come, $4$ is free: join it to $6$ , then $5$ to $6$ , and finally the leftover $6$ and $7$ .

Now you. Decode the Prüfer code $3, 3, 5, 1$ into a tree on ${1, \dots, 6}$ , and check by encoding it again.

Answer

The edges are $23$ , $34$ , $35$ , $15$ and $16$ : join $2$ to $3$ , then $4$ to $3$ , then $3$ (now free) to $5$ , then $5$ to $1$ , and finally the leftover $1$ and $6$ . Encoding removes the leaves $2$ and $4$ (writing $3, 3$ ), then $3$ (writing $5$ ), then $5$ (writing $1$ ).

Rooted binary trees

Choosing one vertex of a tree as its root gives the tree a direction. Each other vertex $v$ has a unique path to the root, by characterisation (4), and the next vertex on it is the parent of $v$ , which makes $v$ one of its children. A binary tree is a rooted tree in which every vertex has no children or exactly two, a left and a right, and left differs from right. The vertices with children are internal. With $n$ internal vertices there are $2 n$ children, and every vertex but the root is a child, so there are $2 n + 1$ vertices and $n + 1$ leaves.

Let $B_{n}$ count binary trees with $n$ internal vertices. A lone root gives $B_{0} = 1$ , then $B_{1} = 1$ and $B_{2} = 2$ . For $n = 3$ the root's left subtree holds $2$ , $1$ or $0$ of the other internal vertices, giving $2 + 1 + 2 = 5$ shapes. Read each internal vertex as a multiplication and the five ways to multiply $a, b, c, d$ appear: $((a b) c) d$ , $(a (b c)) d$ , $(a b) (c d)$ , $a ((b c) d)$ and $a (b (c d))$ . In general the left subtree has some $k$ internal vertices and the right $n - 1 - k$ , chosen independently, so

B_{n} = \sum_{k = 0}^{n - 1} B_{k} B_{n - 1 - k}

This is the recurrence $C_{n + 1} = \sum_{k = 0}^{n} C_{k} C_{n - k}$ that the lesson on generating functions set up for the Catalan numbers, and both start at $1$ . So $B_{n} = C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})$ , giving $B_{3} = \frac{20}{4} = 5$ as listed and $B_{5} = 42$ .

Trees, then, are characterised, counted and coded, and they are easy to draw on paper without crossings: root at the top, each generation of children in a row below. Five towns each joined directly to every other, the complete graph $K_{5}$ , resist every attempt to be drawn that way. The last questions of the course are geometric: which graphs can be drawn in the plane without crossings, and how few colours their regions need so that neighbours always differ. The final lesson answers both, starting from a formula of Euler's.

Planarity and colouring

Some graphs can be drawn on paper with no two edges crossing and some cannot, and the problem is to tell which is which, then to find how few colours are needed so that neighbouring regions of a map never share one.

The previous lesson proved that a tree, a connected graph with no cycles, on $V$ vertices has exactly $V - 1$ edges, and that every connected graph contains a spanning tree, a tree using all of its vertices and some of its edges. Both facts are used below. Graphs here are simple (no loops, no repeated edges), $K_{n}$ is the complete graph on $n$ vertices, and $K_{m, n}$ joins each of $m$ vertices to each of $n$ others. So far a graph has been pure combinatorics, a list of what is joined to what. The question now is geometric, and the answer starts from a formula Euler sent to Christian Goldbach in 1750.

Drawings, faces and the outer face

A plane drawing of a graph puts each vertex at a point and each edge along a curve between its ends, so that curves meet only at shared ends. A graph is planar if it has a plane drawing, and a graph together with one is a plane graph. $K_{4}$ drawn as a square with both diagonals has a crossing, but moving one vertex inside the triangle of the other three removes it, so $K_{4}$ is planar although that first drawing is not a plane one.

A plane drawing cuts the rest of the plane into regions called faces. Exactly one is unbounded, the outer face, surrounding the whole drawing. The cycle $C_{4}$ has two faces, inside and outside. $K_{4}$ with one vertex in the middle has four: three small triangles and the outer face. A tree has only one, since no cycle encloses anything.

The degree of a face is the length of the walk around its boundary, and an edge with the same face on both sides, such as every edge of a tree, is walked twice and counts twice. Then every edge contributes exactly $2$ , one for each side, so the face degrees of a plane graph add up to $2 E$ . It is the handshake lemma again, counting edge and face incidences instead of edge and vertex ones.

Polyhedra supply plane graphs. Puncture one face of a convex polyhedron and stretch the surface flat through the hole: the vertices and edges become a plane graph, and the punctured face becomes the outer face. The cube becomes a small square inside a large one with corners joined: $8$ vertices, $12$ edges and $6$ faces.

Euler's formula

Theorem (Euler). A connected plane graph with $V$ vertices, $E$ edges and $F$ faces has $V - E + F = 2$ .

The proof is by induction on the number of edges outside a spanning tree. Let $T$ be a spanning tree of the connected plane graph $G$ , drawn as it sits inside $G$ . It has $V - 1$ edges and one face, so for $T$ the count is $V - (V - 1) + 1 = 2$ . Now put the other edges of $G$ back one at a time. Each new edge ${u, v}$ joins two vertices already connected by a path in the tree, so it closes a cycle, a closed curve separating the plane into an inside and an outside. The face the new edge runs through is cut in two and no other face changes. Each step adds one edge and one face, so $V - E + F$ stays $2$ , and when every edge is back the graph is $G$ .

That a closed curve without self-crossings splits the plane into exactly two regions is the Jordan curve theorem. It looks obvious and is hard to prove for arbitrary curves (Camille Jordan's 1887 proof was later judged incomplete), but for curves made of straight segments, which is all a drawing needs, it is elementary, and here it is taken on trust.

The cube has $8 - 12 + 6 = 2$ . The dodecahedron has $12$ pentagonal faces; each edge lies on $2$ of them, so $E = \frac{12 \times 5}{2} = 30$ , and each vertex on $3$ , so $V = \frac{12 \times 5}{3} = 20$ . Then $20 - 30 + 12 = 2$ . Connectedness matters: two separate triangles have $6 - 6 + 3 = 3$ , and in general a plane graph with $c$ components has $V - E + F = 1 + c$ .

Example. A connected plane graph has every vertex of degree $3$ , and every face is a pentagon or a hexagon. Show that it has exactly $12$ pentagons, however many hexagons it has.

Let there be $p$ pentagons and $h$ hexagons, so $F = p + h$ . Face degrees sum to $2 E$ , so $2 E = 5 p + 6 h$ , and vertex degrees sum to $2 E$ , so $3 V = 2 E$ . Multiply Euler's formula by $6$ and substitute $6 V = 4 E$ to get $6 F - 2 E = 12$ , that is $6 p + 6 h - 5 p - 6 h = 12$ , so $p = 12$ . The hexagons cancel. The dodecahedron is the case $h = 0$ , and a football, $12$ pentagons and $20$ hexagons, has $E = \frac{60 + 120}{2} = 90$ and $V = 60$ , with $60 - 90 + 32 = 2$ .

Now you. A connected plane graph has every vertex of degree $3$ , and every face is a square or a hexagon. How many squares does it have?

Answer

Exactly $6$ . With $s$ squares and $h$ hexagons, $2 E = 4 s + 6 h$ and $3 V = 2 E$ , and the same steps give $6 F - 2 E = 12$ , so $6 s + 6 h - 4 s - 6 h = 12$ and $s = 6$ . The cube is the case $h = 0$ ; with $h = 8$ it is the truncated octahedron, with $E = 36$ , $V = 24$ and $24 - 36 + 14 = 2$ .

Too many edges to be planar

Theorem. A simple planar graph with $V \geq 3$ vertices has $E \leq 3 V - 6$ .

Take a plane drawing, and suppose first it is connected. A face of degree $1$ or $2$ would need a loop, a repeated edge, or a graph that is a single edge, all ruled out. So every face has degree at least $3$ , and counting edge and face incidences gives $2 E \geq 3 F$ . Euler's formula with $F \leq \frac{2 E}{3}$ gives $2 = V - E + F \leq V - \frac{E}{3}$ , which rearranges to $E \leq 3 V - 6$ . A disconnected planar graph can have edges added between components, staying planar, until it is connected, and the bound for the larger graph covers the smaller.

$K_{5}$ has $V = 5$ and $E = 10$ , while $3 V - 6 = 9$ . So $K_{5}$ is not planar: five towns each joined directly to every other cannot have their roads laid flat without a crossing.

If a graph has no triangles, every face has degree at least $4$ , so $2 E \geq 4 F$ and the same algebra gives $E \leq 2 V - 4$ . The graph $K_{3, 3}$ has no triangles, since every edge crosses between the sides and so every cycle is even. It has $V = 6$ and $E = 9 > 8$ , so it is not planar. This is the three utilities puzzle: three houses each to be joined to gas, water and electricity with no two pipes crossing, which cannot be done. Notice that $K_{3, 3}$ passes the first test, $9 \leq 12$ : the bounds are necessary conditions only.

Example. Show that for every simple graph $G$ on $11$ vertices, $G$ or its complement (same vertices, joined exactly where $G$ has no edge) is not planar.

Between them $G$ and its complement contain every pair once, so their edges number $(\binom{11}{2}) = 55$ . If both were planar each would have at most $3 \times 11 - 6 = 27$ edges, $54$ in all. Since $55 > 54$ , one of them has at least $28$ edges and is not planar.

Now you. The Petersen graph has as vertices the ten two element subsets of ${1, 2, 3, 4, 5}$ , two joined when they are disjoint. Every vertex has degree $3$ , and its shortest cycle has length $5$ . Show that it is not planar, although it satisfies both bounds above.

Answer

$V = 10$ and $E = \frac{10 \times 3}{2} = 15$ , and indeed $15 \leq 24$ and $15 \leq 16$ . With no cycle shorter than $5$ , every face of a plane drawing would have degree at least $5$ , so $2 E \geq 5 F$ and $F \leq 6$ . But Euler's formula forces $F = 2 - 10 + 15 = 7$ . So no plane drawing exists.

Subdividing an edge, replacing it by a path through new vertices of degree $2$ , changes no picture, so a graph containing a subdivided $K_{5}$ or $K_{3, 3}$ is not planar. Kazimierz Kuratowski proved in 1930 that these are the only obstructions.

Theorem (Kuratowski). A graph is planar if and only if it contains no subdivision of $K_{5}$ or of $K_{3, 3}$ .

The hard direction, that a graph avoiding both can always be drawn, is beyond this course. The Petersen graph contains a subdivided $K_{3, 3}$ , as it must.

Colourings and the chromatic number

A proper colouring gives each vertex a colour so that adjacent vertices differ, and the chromatic number $χ (G)$ is the fewest colours that allow one. $K_{n}$ needs $n$ . An even cycle alternates two colours; an odd cycle cannot, since alternating around it brings the start back with the wrong colour, so $χ (C_{n}) = 3$ for odd $n$ . Showing $χ (G) = k$ takes two halves: a colouring with $k$ colours, and a reason $k - 1$ fail.

Maps become graphs through their dual: a vertex inside each country, two joined when they share a stretch of border, not just a point. Each dual edge crosses only the border it stands for, so the dual of a map is planar, and colouring countries so that neighbours differ is properly colouring the vertices of a planar graph.

The same idea schedules. Make each exam a vertex and join two when some student sits both. A proper colouring assigns time slots with no student in two rooms at once, and $χ$ is the fewest slots possible.

Example. Six exams $A, B, C, D, E, F$ have clashes $A B$ , $B C$ , $C D$ , $D E$ , $E A$ , $F A$ and $F C$ . How many slots are needed?

$A, B, C, D, E$ form a cycle of length $5$ , which is odd, so at least $3$ . Three suffice: $A$ and $C$ in slot $1$ , $B$ and $D$ in slot $2$ , $E$ in slot $3$ , and $F$ , whose clashes $A$ and $C$ are both in slot $1$ , in slot $2$ . Every clashing pair is split: $A B$ is $1, 2$ ; $B C$ is $2, 1$ ; $C D$ is $1, 2$ ; $D E$ is $2, 3$ ; $E A$ is $3, 1$ ; $F A$ and $F C$ are $2, 1$ . So $χ = 3$ .

Now you. A seventh exam $G$ clashes with each of $A, B, C, D$ and $E$ . How many slots are needed now?

Answer

$4$ . The five exams of the odd cycle already use three slots between them, and $G$ clashes with all of them, so it needs a fourth; putting it there and keeping the rest works. The graph contains no $K_{4}$ , so a large chromatic number does not need a large complete subgraph.

No efficient method is known for the chromatic number in general. Computing it was among the problems Richard Karp showed NP-complete in 1972, the same class as the Hamilton cycle question, and even deciding whether $3$ colours suffice is that hard.

Two colours and odd cycles

Two colours, by contrast, are completely understood. A graph is bipartite if its vertices split into two sides with every edge crossing between them, which is the same thing as a proper colouring with two colours.

Theorem. A graph is two colourable if and only if it has no cycle of odd length.

If it is two colourable, colours alternate around any cycle, so returning to the start takes an even number of steps.

Conversely, suppose there is no odd cycle, and treat each connected component separately. Take a spanning tree, choose a root $r$ , and colour each vertex by the parity of its depth $d$ , its distance from $r$ along the tree. Tree edges join consecutive depths, so they are fine. Suppose another edge ${u, v}$ joined two vertices of the same colour, and let $w$ be the last vertex shared by the tree paths from $r$ to $u$ and to $v$ . The tree path from $u$ to $v$ through $w$ has length $d (u) + d (v) - 2 d (w)$ , which is even because $d (u)$ and $d (v)$ have the same parity. Adding ${u, v}$ closes a cycle of odd length, a contradiction.

The proof is also an algorithm: colour by depth, and either every edge checks out or a clashing edge exhibits an odd cycle. Two colours are decided quickly; three is the hard problem.

Six colours suffice

Lemma. Every simple planar graph has a vertex of degree at most $5$ .

With $V \leq 2$ this is clear. Otherwise the degrees sum to $2 E \leq 6 V - 12$ , so the average degree is below $6$ , and some vertex is at or below the average.

Theorem. Every planar graph can be properly coloured with $6$ colours.

By induction on $V$ . A graph with at most $6$ vertices gets a different colour on each. For larger $G$ , delete a vertex $v$ of degree at most $5$ . What remains is planar, so by induction it has a $6$ colouring. The neighbours of $v$ use at most $5$ colours, so a sixth is free for $v$ .

Alfred Kempe published a proof in 1879 that four colours suffice, handling a $v$ of degree $4$ or $5$ by swapping colours along two coloured chains of vertices to free one up. It stood for eleven years until Percy Heawood found, in 1890, a case the swaps miss. Heawood salvaged what Kempe's chains do prove, the five colour theorem.

Four colours and a proof by computer

In 1852 Francis Guthrie, colouring a map of the counties of England, noticed that four colours were enough and asked whether that was always so. His brother Frederick passed the question to Augustus De Morgan, who wrote of it to William Rowan Hamilton that October. Four cannot be lowered, since $K_{4}$ is planar and needs four.

Theorem (four colour theorem). Every planar graph can be properly coloured with $4$ colours.

Kenneth Appel and Wolfgang Haken at the University of Illinois proved it in 1976. By hand they showed that a smallest counterexample would have to contain one of almost two thousand configurations. A computer then checked that none of them can occur in a smallest counterexample, which took about 1,200 hours of machine time, and no person has checked that part through. Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas gave a simpler proof in 1997 with $633$ configurations, and in 2005 Georges Gonthier checked the whole argument in the Coq proof assistant, a program that verifies every logical step down to the axioms.

A proof is an argument that each step follows from the last, and nothing requires the checker to be human. The worry in 1976 was a bug nobody could see, and some mathematicians declined to call it a proof. Independent programs agreeing, then a formal proof whose trust rests on a small checking kernel rather than on the whole computation, have settled it for most. What the computer does not give is understanding: it confirms that four colours suffice without a short reason why, and none is known.

What has been built

The course began with questions of how many. The sum and product rules, bijections, binomial coefficients and inclusion and exclusion count without listing, and Probability rests on them, since a probability over equally likely outcomes is one count divided by another. Recurrences and generating functions describe a count through smaller ones, which is how Algorithms and Data Structures measures the running time of a program that calls itself. Divisibility, primes and congruences built RSA from Fermat's theorem, the starting point of Cryptography, and the same questions about primes pursued further are Number Theory. Graphs, trees and colourings proved what is true of networks, and Algorithms and Data Structures turns those proofs into methods for searching them and finding their shortest paths and spanning trees. Through all of it the method has been the same: find the right thing to count, set up an induction, and prove the answer right.

Discrete Mathematics, from libre.university