<!-- Generated from https://www.teclamairme.com/#group-T6 by readviews.py; never edited by hand. -->

# Glossary cards — Chapter ᚄ(S): The city streets

*Teclam Áirme, the Mathematical Compendium — a copy for AI readers of https://www.teclamairme.com/#group-T6, as of 2026-09-30. Links are relative to https://www.teclamairme.com/fortheaireaders/.*

[Guide for AI readers](index.md) · [The chapter](ch06.md)

*Modular arithmetic, divisibility, partitions, combinatorics, and graph theory: Wilson’s theorem, the Möbius function, gcd and lcm, Ramanujan’s congruence, choosing and coloring. Each card: its symbol, type, one-line headline, the longer note, the reference entries it cites and the cards it links to.*

### the letter Sail — `ᚄ` {#g-og-sail}

*Ogham letter*

Ogham letter name meaning ‘willow’; its kennings run from the pallor of the dead to the beginning of honey.

Sail means ‘willow-tree’, cognate with Latin salix, and is another of the five transparent tree names. The three Old Irish word-oghams, the Bríatharogaim ascribed to Morann mac Moín, to Mac ind Óc, and to Cú Chulainn, give lí ambi, “pallor of a lifeless one”; lúth bech, “sustenance of bees”; and tosach mela, “beginning of honey.” The Auraicept reads the first as a remark about color: the willow “has no colour,” owing to the resemblance of its hue to a dead person. Modern tree lore and ogham divination descend from the medieval plant glosses by way of Robert Graves’s The White Goddess of 1948, which read the letter order as an ancient seasonal calendar of tree magic. Celtic scholarship rejects that reconstruction; the associations in circulation today are modern, not ancient.

Cites: [2.15](ch02-refs.md#r-2.15), [2.16](ch02-refs.md#r-2.16), [2.17](ch02-refs.md#r-2.17), [2.19](ch02-refs.md#r-2.19)

### Wilson’s theorem — `(12! + 1) mod 13` {#g-wilson}

*Integer or rational*

(p − 1)! + 1 is divisible by p exactly when p is prime; 479001601 = 13 × 36846277.

Wilson’s theorem states that (p − 1)! ≡ −1 (mod p) if and only if p is prime. Ibn al-Haytham knew it around 1000; Leibniz, the evidence suggests, knew it a century before Wilson and never published; John Wilson found it and Edward Waring printed it without proof in 1770, later calling it a most elegant property of primes; Lagrange gave the first proof soon after. Here p = 13, and 12! + 1 = 479,001,601 = 13 × 36,846,277, so the remainder is 0. The remainder of an integer division is an integer, which is why it carries the integer tag and hands 0 home directly.

Cites: [6.1](ch06-refs.md#r-6.1), [6.2](ch06-refs.md#r-6.2), [6.23](ch06-refs.md#r-6.23), [6.38](ch06-refs.md#r-6.38)

### Euler’s totient of 13 — `φ(13)` {#g-totient}

*Integer or rational*

Twelve numbers below 13 share no factor with it; this φ is not the golden ratio.

Euler’s totient φ(n), introduced by Euler in 1763, counts the integers from 1 to n that share no factor with n; the symbol φ is Gauss’s, from the Disquisitiones Arithmeticae of 1801. For a prime it is p − 1, so φ(13) = 12. It is the size of the multiplicative group of remainders and the modulus for the two exponents in RSA; the symbol φ is reused in this book, and here it is not the golden ratio of Chapter ᚂ(L).

Cites: [6.29](ch06-refs.md#r-6.29), [6.3](ch06-refs.md#r-6.3)

See also: [Euler’s theorem](ch06-cards.md#g-eulerthm), [golden ratio](ch04-cards.md#g-phi), [RSA](ch06-cards.md#g-rsa)

### Fermat’s little theorem — `2^{12} mod 13` {#g-fermatlittle}

*Integer or rational*

For a prime p that does not divide a, a^(p−1) leaves remainder 1 on division by p, so 4096 mod 13 = 1.

Fermat’s little theorem, stated in a letter to Frénicle de Bessy in 1640 and first proved in print by Euler in 1736, says that a^(p−1) ≡ 1 (mod p) whenever p is prime and does not divide a. So 2¹² = 4096 = 315 × 13 + 1 leaves remainder 1. It is the basis of the Fermat primality test and one of the ideas behind public-key cryptography, though a working cryptosystem needs a great deal more; it is an integer because it is a remainder.

Cites: [6.32](ch06-refs.md#r-6.32), [6.4](ch06-refs.md#r-6.4)

### thirteen is one more than a multiple of four — `13 mod 4` {#g-mod4}

*Integer or rational*

So 13 = 2² + 3² by Fermat’s theorem on sums of two squares.

An odd prime leaves remainder 1 or 3 on division by 4, and Fermat’s theorem on sums of two squares, stated in 1640 and proved by Euler in 1749, says the odd primes that are sums of two squares are exactly those with remainder 1. 13 = 4 × 3 + 1, and 13 = 2² + 3². The remainder is an integer; it is placed here so the denominator asks the same prime a third question.

Cites: [6.34](ch06-refs.md#r-6.34), [6.5](ch06-refs.md#r-6.5)

See also: [Fermat’s theorem on sums of two squares](ch21-cards.md#g-fermat2sq)

### Legendre symbol — `(3/13)` {#g-legsym}

*Integer or rational*

Asks whether 3 is a perfect square in the world of remainders mod 13; it is, because 4² = 16 leaves remainder 3, so the symbol is 1.

The Legendre symbol (a/p), introduced by Legendre in 1797 or 1798, is 1 if a is a nonzero square modulo p, −1 if it is not, and 0 if p divides a. Since 4² = 16 ≡ 3 (mod 13), (3/13) = 1. Gauss’s law of quadratic reciprocity, which he proved in 1796 and called the golden theorem, tells you how (p/q) and (q/p) are related; the symbol is always an integer, and for a nonzero square it is exactly 1.

Cites: [6.34](ch06-refs.md#r-6.34), [6.6](ch06-refs.md#r-6.6)

See also: [quadratic reciprocity](ch06-cards.md#g-qrecip)

### the order of 2 modulo 13 — `ord_{13}(2)` {#g-ord13}

*Integer or rational*

The smallest k with 2^k ≡ 1 (mod 13) is 12, so 2 is a primitive root modulo 13.

The multiplicative order of a modulo n is the least k ≥ 1 with a^k ≡ 1 (mod n); by Fermat’s little theorem it divides p − 1 for a prime p. For a = 2 and p = 13 the powers 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1 run through every nonzero remainder before returning to 1, so the order is 12 and 2 is a primitive root, a notion Euler named; Gauss proved in 1801 that every prime has one. The Carmichael function λ(13) = 12 is the largest order that occurs. An order is a positive integer.

Cites: [6.29](ch06-refs.md#r-6.29), [6.7](ch06-refs.md#r-6.7)

See also: [Fermat’s little theorem](ch06-cards.md#g-fermatlittle)

### RSA — `m^(ed) ≡ m (mod n)` {#g-rsa}

*Function or operator*

Exponentiate modulo the product of two primes; the encrypting and decrypting exponents are inverses modulo the totient, so doing both returns the message.

RSA takes a modulus n = pq for two large primes, a public exponent e, and a private exponent d chosen so that ed ≡ 1 modulo the totient of n; encryption is m ↦ m^e mod n and decryption is the same operation with d, and it works because raising to ed returns the message — Euler’s theorem doing for a composite modulus what Fermat’s little theorem does for a prime one. Rivest, Shamir, and Adleman described it publicly in 1977, in Scientific American’s Mathematical Games column that August; Clifford Cocks had found an equivalent system secretly at GCHQ in 1973, and it stayed classified until 1997. The chapter mentions it to make the opposite point to the usual one: the totient identity is the arithmetic skeleton, and a working cryptosystem needs a great deal more than a skeleton. A scheme, uncolored.

Cites: [6.36](ch06-refs.md#r-6.36)

See also: [Euler’s theorem](ch06-cards.md#g-eulerthm), [Fermat’s little theorem](ch06-cards.md#g-fermatlittle)

### the Möbius function at Kaprekar’s constant — `μ(6174)` {#g-mobius}

*Integer or rational*

6174 = 2·3²·7³ has a repeated prime factor, so μ is 0; this μ is not the Ramanujan–Soldner constant of Chapter ᚐ(A).

The Möbius function μ(n), defined by August Ferdinand Möbius in 1832, is 1 for n = 1, (−1)^k when n is a product of k distinct primes, and 0 when n has a repeated prime factor. Kaprekar’s constant 6174 = 2 × 3² × 7³ has two repeated primes, so μ(6174) = 0. The function inverts sums over divisors, and a bound on the growth of its partial sums is equivalent to the Riemann Hypothesis; its values are integers, hence the integer tag. It is not the Ramanujan–Soldner constant μ of Chapter ᚐ(A).

Cites: [6.26](ch06-refs.md#r-6.26), [6.8](ch06-refs.md#r-6.8)

See also: [Kaprekar’s constant](ch04-cards.md#g-kaprekar), [the Mertens function](ch18-cards.md#g-mertensM), [Ramanujan–Soldner constant](ch17-cards.md#g-mu), [the Riemann Hypothesis](ch18-cards.md#g-rh)

### the gcd–lcm identity — `gcd(12, 18)·lcm(12, 18) − 12·18` {#g-gcdlcm}

*Integer or rational*

0: 6 × 36 = 216 = 12 × 18. For any two positive integers the greatest common divisor times the least common multiple is their product.

Every prime power appears in gcd(a, b) with the smaller of its two exponents and in lcm(a, b) with the larger, so together they carry exactly the exponents of a·b. Euclid’s algorithm (Elements VII.2, about 300 BC) computes the gcd by repeated division and is, in Knuth’s phrase, the oldest nontrivial algorithm that has survived to the present day; the identity then gives the lcm for free. An integer identity and the carrier for divisibility.

Cites: [6.25](ch06-refs.md#r-6.25), [6.37](ch06-refs.md#r-6.37), [6.9](ch06-refs.md#r-6.9)

See also: [the Euclidean algorithm](ch06-cards.md#g-euclidalg)

### the greatest common divisor of 12 and 18 — `gcd(12, 18)` {#g-gcd1218}

*Integer or rational*

6, found by Euclid’s algorithm in two lines: 18 = 12 + 6, 12 = 2·6.

The largest integer dividing both 12 and 18. Euclid’s algorithm replaces the pair by the smaller number and the remainder until the remainder is 0; the last nonzero remainder is the gcd. Lamé proved in 1844 that the number of steps is at most five times the number of decimal digits of the smaller number. An integer.

Cites: [6.10](ch06-refs.md#r-6.10), [6.34](ch06-refs.md#r-6.34), [6.9](ch06-refs.md#r-6.9)

See also: [the Euclidean algorithm](ch06-cards.md#g-euclidalg)

### the least common multiple of 12 and 18 — `lcm(12, 18)` {#g-lcm1218}

*Integer or rational*

36, the first number that both 12 and 18 divide.

The smallest positive integer that both numbers divide; here 36 = 2²·3². Together with the gcd it satisfies gcd·lcm = 12·18. An integer.

Cites: [6.9](ch06-refs.md#r-6.9)

See also: [the gcd–lcm identity](ch06-cards.md#g-gcdlcm)

### the Euclidean algorithm — `a = qb + r` {#g-euclidalg}

*Function or operator*

Divide, keep the remainder, repeat: the gcd is the last nonzero one. Knuth calls it the oldest nontrivial algorithm that has survived to the present day.

To find the greatest common divisor of a and b, divide the larger by the smaller and keep the remainder, then repeat with the smaller and the remainder. The remainders strictly decrease and cannot go below zero, so the process stops, and the last nonzero remainder is the gcd. It is in Book VII of the Elements. For 12 and 18 it takes two lines: 18 = 12 + 6 and 12 = 2 × 6, so the answer is 6. Knuth’s phrase for it is “the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day”. An algorithm, uncolored.

Cites: [6.10](ch06-refs.md#r-6.10), [6.25](ch06-refs.md#r-6.25)

### Ramanujan’s partition congruence, at nine — `p(9) mod 5` {#g-partition5}

*Integer or rational*

p(9) = 30, so the remainder is 0: the n = 1 case of Ramanujan’s congruence p(5n+4) ≡ 0 (mod 5), which holds for every n.

Let p(n) count the ways to write n as an unordered sum of positive integers: p(4) = 5 and p(9) = 30. Ramanujan proved in 1919 that p(5n+4) ≡ 0 (mod 5) for every n ≥ 0, together with a companion congruence modulo 7; the third, modulo 11, is his as well, but its proof reached print only when Hardy drew it out of an unpublished manuscript in 1921. The formula shows the n = 1 instance, 30 mod 5 = 0. It is a celebrated doorway from elementary counting into q-series and modular forms. The displayed remainder is exactly the integer 0.

Cites: [6.11](ch06-refs.md#r-6.11), [6.12](ch06-refs.md#r-6.12), [6.31](ch06-refs.md#r-6.31)

See also: [the partitions of four](ch06-cards.md#g-p4)

### the partitions of four — `p(4)` {#g-p4}

*Integer or rational*

5: 4, 3+1, 2+2, 2+1+1, and 1+1+1+1, the n = 0 case of Ramanujan’s congruence, since 5 is itself a multiple of 5.

The partition function p(n) counts the ways to write n as an unordered sum of positive integers: p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, and p(100) = 190,569,292. Euler found its generating function in the 1740s; Hardy and Ramanujan found its asymptotic size in 1918, and Rademacher an exact series in 1937. An integer.

Cites: [6.11](ch06-refs.md#r-6.11), [6.12](ch06-refs.md#r-6.12), [6.34](ch06-refs.md#r-6.34)

### Ramanujan’s partition congruences — `p(5n+4)≡0(5), p(7n+5)≡0(7), p(11n+6)≡0(11)` {#g-ramanujancong}

*Function or operator*

Srinivasa Ramanujan’s 1919 discovery that the partition function is always divisible by 5, 7, or 11 along three specific arithmetic progressions of n.

Ramanujan found that p(5n+4) is always a multiple of 5, p(7n+5) always a multiple of 7, and p(11n+6) always a multiple of 11, for every nonnegative n, congruences he announced in 1919. Ken Ono and others have since extended the pattern to further prime moduli. The chapter’s own card is the single mod-5 instance at n = 1, p(9) mod 5 = 0; this is the general family it belongs to. A theorem, uncolored.

Cites: [6.42](ch06-refs.md#r-6.42)

See also: [Ramanujan’s partition congruence, at nine](ch06-cards.md#g-partition5)

### two choose five — `C(2, 5)` {#g-binomial}

*Integer or rational*

There are no ways to choose five things from two, so the binomial coefficient is 0.

The binomial coefficient C(n, k), the number of ways to choose k things from n, appears in Pascal’s triangle, written in 1654 and published in 1665 after his death, but known in India, Persia, and China centuries earlier. When k exceeds n there is nothing to choose, so C(2, 5) = 0. Counting results are integers, hence the tag; the display keeps the (n, k) order used in the formula.

Cites: [6.13](ch06-refs.md#r-6.13), [6.34](ch06-refs.md#r-6.34)

See also: [counting notation](ch06-cards.md#g-permfact)

### the smallest nontrivial Ramsey number — `R(3, 3)` {#g-ramsey33}

*Integer or rational*

6: with acquaintance treated as mutual, any six people contain three mutual acquaintances or three mutual strangers; five can avoid both.

Frank Ramsey proved in 1930 that complete disorder is impossible: for any r and s there is a least R(r, s) such that every two-coloring of the edges of a complete graph on that many vertices contains a red clique of size r or a blue one of size s. Model the people as vertices of a complete graph, coloring each edge red for mutual acquaintance and blue for mutual strangers. For six vertices, choose v. By the pigeonhole principle at least three of its five incident edges have the same color; exchange the colors if necessary and call it red. Let a, b, and c be their other endpoints. If any edge among a, b, and c is red, it forms a red triangle with v. Otherwise all three edges among a, b, and c are blue, so they form a blue triangle. Hence six always suffice. For five vertices arranged around a pentagon, color the five sides red and the five diagonals blue. Each color forms a five-cycle, and neither contains a triangle. Thus five do not suffice. Together these bounds prove R(3, 3) = 6. Greenwood and Gleason computed R(3, 4) = 9 and R(4, 4) = 18 in 1955, and R(5, 5) is still only known to lie between 43 and 46; Erdős’s story is that if aliens demanded R(5, 5) we should compute it, but if they demanded R(6, 6) we should attack. A count of vertices, hence the integer tag.

Cites: [6.14](ch06-refs.md#r-6.14), [6.34](ch06-refs.md#r-6.34)

See also: [the pigeonhole principle](ch06-cards.md#g-pigeon), [the next Ramsey number](ch06-cards.md#g-ramsey44)

### the third Catalan number — `C_{3}` {#g-catalan3}

*Integer or rational*

5: the number of ways to bracket four factors, to triangulate a pentagon, or to match three pairs of parentheses.

The Catalan numbers 1, 1, 2, 5, 14, 42, … are C_n = (2n)!/((n + 1)! n!); Euler counted triangulations of polygons with them in 1751, Eugène Catalan attached his name to them through bracketing problems, and Ming Antu had found them in China around 1730. They count more than two hundred families of objects in Stanley’s catalog. Not to be confused with Catalan’s constant G in Chapter ᚃ(F). An ordinary count, hence the integer tag.

Cites: [6.15](ch06-refs.md#r-6.15), [6.34](ch06-refs.md#r-6.34), [6.37](ch06-refs.md#r-6.37)

See also: [Catalan’s constant](ch05-cards.md#g-catalan)

### the third Bell number — `B₃` {#g-bell3}

*Integer or rational*

5: the ways to split three things into nonempty groups, {abc}, {ab}{c}, {ac}{b}, {bc}{a}, {a}{b}{c}.

The Bell numbers 1, 1, 2, 5, 15, 52, … count the partitions of a set of n things into nonempty groups. The earliest known exhaustive enumeration was a medieval Japanese parlor game, genjikō, on the 52 partitions of five incense sticks; Dobiński gave a formula in 1877; Eric Temple Bell wrote about them in 1934 and 1938, saying they had been rediscovered many times, and Becker and Riordan named them for him in 1948. B₃ = 5, the same 5 as the Catalan number beside it, by coincidence. A count, hence an integer.

Cites: [6.16](ch06-refs.md#r-6.16), [6.34](ch06-refs.md#r-6.34)

See also: [the third Catalan number](ch06-cards.md#g-catalan3)

### the derangements of four — `!4` {#g-derange4}

*Integer or rational*

9: the ways to return four hats to four people so that nobody gets their own.

A derangement is a permutation with no fixed point; !n counts them, and !4 = 9 (the sequence runs 1, 0, 1, 2, 9, 44, …). Pierre Rémond de Montmort posed the problem in his Essay d’analyse sur les jeux de hazard in 1708 and solved it in 1713, as did Nicolaus Bernoulli; the name subfactorial is William Allen Whitworth’s. The fraction !n/n! tends to 1/e; the secretary constant of Chapter ᚋ(M) is the same number. A count, hence an integer.

Cites: [6.17](ch06-refs.md#r-6.17), [6.34](ch06-refs.md#r-6.34)

See also: [the secretary-problem constant](ch13-cards.md#g-secretary)

### the binomial theorem — `(x+y)ⁿ = Σ C(n, k) xᵏ yⁿ⁻ᵏ` {#g-binomthm}

*Function or operator*

The binomial theorem expands (x + y)ⁿ into a sum of terms C(n, k) xᵏ yⁿ⁻ᵏ, turning the binomial coefficients into the coefficients of an algebraic expansion.

Each term’s coefficient C(n, k), the number of ways to choose k things from n, is exactly the entry Pascal’s triangle puts in that position, so the triangle is a row-by-row picture of the theorem. Isaac Newton generalized it in 1665 to non-integer exponents, turning the finite sum into an infinite series. The convention 0! = 1, which makes C(n, 0) = C(n, n) = 1, is what makes the expansion’s first and last terms come out right.

Cites: [6.45](ch06-refs.md#r-6.45)

See also: [zero factorial](ch04-cards.md#g-zerofact)

### the chromatic polynomial of a triangle at two colors — `P(K₃, 2)` {#g-chrom}

*Integer or rational*

A triangle cannot be 2-colored, so the count of proper colorings is 0.

The chromatic polynomial P(G, k), introduced for planar graphs by George Birkhoff in 1912 during work on the four-color problem and since extended to all graphs, counts the proper colorings of a graph G with k colors. For the triangle K₃ it is k(k − 1)(k − 2), which is 0 at k = 2: three mutually adjacent vertices need three colors. A count of colorings is an integer.

Cites: [6.18](ch06-refs.md#r-6.18), [6.30](ch06-refs.md#r-6.30)

### the handshaking lemma, for the Petersen graph — `10·3 − 2·15` {#g-handshake}

*Integer or rational*

0: the Petersen graph has ten vertices of degree three and fifteen edges, and the degrees add to twice the edges, as they do in every finite graph.

For a finite undirected graph G = (V, E), adding the degrees of all vertices counts each edge twice, once at each endpoint, so Σ_{v∈V}deg(v) = 2|E|. The Petersen graph (Julius Petersen, 1898), ten vertices each of degree three and fifteen edges, gives 10·3 − 2·15 = 0. The lemma implies that every graph has an even number of odd-degree vertices and sits behind Euler trails and the Königsberg bridges. An integer identity and the carrier for graph theory.

Cites: [6.19](ch06-refs.md#r-6.19)

See also: [the seven bridges of Königsberg](ch06-cards.md#g-konigsberg), [the edges of the Petersen graph](ch06-cards.md#g-petersenE), [the Petersen graph](ch06-cards.md#g-petersengraph)

### the edges of the Petersen graph — `|E(Petersen)|` {#g-petersenE}

*Integer or rational*

15: the ten-vertex, degree-three graph named for Petersen’s paper of 1898, a counterexample to many optimistic predictions about graphs in general.

Julius Petersen drew the graph in 1898 as the smallest bridgeless cubic graph with no three-edge coloring of its edges, though the same drawing had appeared twelve years earlier in a paper of A. B. Kempe, as the ten lines of the Desargues configuration; it has ten vertices, fifteen edges, girth five, is not planar, has no Hamiltonian cycle, and turns up as the smallest counterexample so often that a whole book (Holton and Sheehan, 1993) is devoted to it. An integer.

Cites: [6.19](ch06-refs.md#r-6.19), [6.24](ch06-refs.md#r-6.24), [6.37](ch06-refs.md#r-6.37), [6.38](ch06-refs.md#r-6.38)

### the chromatic polynomial of a triangle at three colors — `P(K₃, 3)` {#g-chromK33}

*Integer or rational*

6: with three colors a triangle can be properly colored in 3·2·1 ways, the same count as its symmetries.

The chromatic polynomial of the triangle is k(k − 1)(k − 2): the first vertex has k choices, the next k − 1, the last k − 2. At k = 2 it is 0 (the numerator’s zero); at k = 3 it is 6. Birkhoff introduced the polynomial in 1912 in the hope of proving the four-color theorem by showing P(G, 4) > 0 for every planar graph; Appel and Haken’s proof of 1976 went instead through reducible configurations. An integer.

Cites: [6.18](ch06-refs.md#r-6.18), [6.30](ch06-refs.md#r-6.30)

See also: [the chromatic polynomial of a triangle at two colors](ch06-cards.md#g-chrom)

### congruence notation — `a ≡ b (mod n)` {#g-congr}

*Function or operator*

Gauss’s 1801 notation for two integers that leave the same remainder on division by n; ≡ reads as congruent.

Carl Friedrich Gauss introduced the congruence a ≡ b (mod n), meaning n divides a − b, at the opening of the Disquisitiones Arithmeticae (1801), choosing ≡ deliberately to look like equality because it behaves like it: congruences can be added, subtracted, and multiplied. Every symbol in this chapter’s modular-arithmetic brace is a statement in that notation. It is a relation, not a value, hence the operator tag.

Cites: [6.20](ch06-refs.md#r-6.20), [6.29](ch06-refs.md#r-6.29)

### the integers modulo 13 — `ℤ/13ℤ` {#g-zmod13}

*Function or operator*

The thirteen remainders 0 to 12 with clock arithmetic; because 13 is prime, every nonzero remainder has a reciprocal, so it is a field.

ℤ/nℤ is the ring of remainders modulo n, written ℤ_n by some authors; it has n elements, and it is a field exactly when n is prime, because then every nonzero remainder has a multiplicative inverse (the pairing trick in Wilson’s proof). ℤ/13ℤ is the world every term of this chapter’s modular-arithmetic brace is computed in. Finite fields of every prime-power order exist and are unique, a theorem of E. H. Moore (1893). It is a structure rather than a value, so it is tagged as a tool.

Cites: [6.20](ch06-refs.md#r-6.20), [6.34](ch06-refs.md#r-6.34)

See also: [Wilson’s theorem](ch06-cards.md#g-wilson)

### the Chinese remainder theorem — `x ≡ 2 (mod 3), x ≡ 3 (mod 5) ⇒ x ≡ 8 (mod 15)` {#g-crt}

*Function or operator*

Congruences to coprime moduli can always be solved together, with a unique answer modulo the product.

The Chinese remainder theorem says that if the moduli n₁, …, n_k are pairwise coprime, any system x ≡ a_i (mod n_i) has exactly one solution modulo n₁⋯n_k. The oldest known instance is in Sunzi’s Suanjing (3rd to 5th century AD): a number that leaves 2 on division by 3, 3 by 5, and 2 by 7 is 23. Qin Jiushao gave the general algorithm in 1247, and Gauss restated it in 1801. It is the reason ℤ/15ℤ behaves like ℤ/3ℤ × ℤ/5ℤ and the workhorse of RSA decryption. A theorem, hence the tool tag.

Cites: [6.21](ch06-refs.md#r-6.21), [6.37](ch06-refs.md#r-6.37)

See also: [congruence notation](ch06-cards.md#g-congr), [RSA](ch06-cards.md#g-rsa)

### quadratic reciprocity — `(p/q)(q/p) = (−1)^((p−1)/2 · (q−1)/2)` {#g-qrecip}

*Function or operator*

Gauss’s golden theorem: whether p is a square modulo q decides whether q is a square modulo p, up to a sign that depends only on the two primes modulo 4.

The law of quadratic reciprocity, conjectured by Euler and Legendre and first proved by Gauss in 1796 (published 1801; he gave eight proofs, six of them in his lifetime, and privately called it the golden theorem), relates the Legendre symbols (p/q) and (q/p) for odd primes: their product is −1 exactly when both p and q leave remainder 3 on division by 4. With p = 3 and q = 13, (13/3) = (1/3) = 1 and the exponent is 1 × 6 = 6, which is even, so the law predicts (3/13) = 1, which agrees with 4² ≡ 3. It is the start of class field theory. A law, hence the tool tag.

Cites: [6.34](ch06-refs.md#r-6.34), [6.6](ch06-refs.md#r-6.6)

See also: [Legendre symbol](ch06-cards.md#g-legsym)

### Euler’s theorem — `a^φ(n) ≡ 1 (mod n)` {#g-eulerthm}

*Function or operator*

Fermat’s little theorem for any modulus: raise a number coprime to n to the totient of n and the remainder is 1.

Euler’s theorem, published by Euler in 1763, in a paper presented in 1758 that uses the totient without yet naming it, generalizes Fermat’s little theorem from primes to every modulus: if gcd(a, n) = 1 then a^φ(n) ≡ 1 (mod n). With n = 13 it is exactly the bracket 2¹² ≡ 1 in the denominator; with n = 9 it says 2⁶ = 64 ≡ 1 (mod 9). It is the theorem that makes RSA decryption undo encryption. A theorem, hence the tool tag.

Cites: [6.3](ch06-refs.md#r-6.3), [6.37](ch06-refs.md#r-6.37), [6.4](ch06-refs.md#r-6.4)

See also: [Fermat’s little theorem](ch06-cards.md#g-fermatlittle), [RSA](ch06-cards.md#g-rsa)

### floor and ceiling — `⌊13/4⌋, ⌈13/4⌉` {#g-floorceil}

*Function or operator*

Round down and round up: ⌊13/4⌋ = 3 and ⌈13/4⌉ = 4, and 13 mod 4 is 13 − 4⌊13/4⌋ = 1.

The floor ⌊x⌋ is the largest integer not above x and the ceiling ⌈x⌉ the smallest not below it. Gauss wrote [x] for the floor in his third proof of quadratic reciprocity (1808); Kenneth Iverson named floor and ceiling and drew the brackets in A Programming Language (1962), the same book that introduced the notation behind Chapter ᚆ(H)’s Iverson bracket. Every remainder in this chapter is a floor in disguise: a mod n = a − n⌊a/n⌋, so 13 mod 4 = 13 − 4 × 3 = 1. A notation rather than a value, hence the tool tag.

Cites: [6.20](ch06-refs.md#r-6.20), [6.37](ch06-refs.md#r-6.37)

See also: [Iverson bracket](ch08-cards.md#g-iverson), [thirteen is one more than a multiple of four](ch06-cards.md#g-mod4), [quadratic reciprocity](ch06-cards.md#g-qrecip)

### the pigeonhole principle — `n + 1 objects into n boxes` {#g-pigeon}

*Function or operator*

Put more things than boxes and some box holds two: the simplest counting argument, used by Dirichlet in 1842.

If n + 1 objects are placed in n boxes, some box contains at least two. Dirichlet used it in 1842 to approximate irrationals by rationals, and later called it the Schubfachprinzip, and it is the seed of Ramsey theory: R(3, 3) = 6 is proved by a pigeonhole argument. Trivial to state and endlessly useful, it is a principle rather than a value, hence the tool tag.

Cites: [6.14](ch06-refs.md#r-6.14), [6.38](ch06-refs.md#r-6.38)

See also: [the smallest nontrivial Ramsey number](ch06-cards.md#g-ramsey33)

### counting notation — `n!, P(n, k), C(n, k)` {#g-permfact}

*Function or operator*

Factorials count orderings, P(n, k) counts ordered choices, C(n, k) counts unordered ones; 5! = 120 is the size of S₅ in Chapter ᚌ(G).

n! = n(n − 1)⋯1 counts the orderings of n things (the notation is Christian Kramp’s, 1808), P(n, k) = n!/(n − k)! counts ordered selections, and C(n, k) = n!/(k!(n − k)!) counts unordered ones; 0! = 1 by the empty-product convention. The binomial theorem (x + y)ⁿ = Σ C(n, k) xᵏ yⁿ⁻ᵏ ties them to algebra, and Stirling’s approximation n! ≈ √(2πn)(n/e)ⁿ, from Stirling’s work of 1729 and 1730, ties them to the √(2π) of Chapter ᚋ(M). Notation, hence the tool tag.

Cites: [6.22](ch06-refs.md#r-6.22), [6.37](ch06-refs.md#r-6.37)

See also: [the binomial theorem](ch06-cards.md#g-binomthm), [the order of the symmetric group on five letters](ch14-cards.md#g-s5), [the bell curve’s normalizer](ch13-cards.md#g-sqrt2pi), [zero factorial](ch04-cards.md#g-zerofact)

### a Stirling number of the second kind — `{4 2} = 7` {#g-stirling42}

*Integer or rational*

The ways to split four things into exactly two nonempty groups: 7. Summing the Stirling numbers of a row gives the Bell number.

The Stirling numbers of the second kind S(n, k) count the ways to split a set of n things into exactly k nonempty groups. They are written {n k} in a brace notation that Jovan Karamata used in 1935 and Marx and Salmeri in 1962, and that Knuth adopted in 1968; James Stirling introduced them in Methodus Differentialis (1730). S(4, 2) = 7, and S(4, 1) + S(4, 2) + S(4, 3) + S(4, 4) = 1 + 7 + 6 + 1 = 15 = B₄. The numbers of the first kind count permutations by cycles. Key entry only; an integer.

Cites: [6.16](ch06-refs.md#r-6.16), [6.38](ch06-refs.md#r-6.38)

See also: [the third Bell number](ch06-cards.md#g-bell3)

### the next Ramsey number — `R(4, 4) = 18` {#g-ramsey44}

*Integer or rational*

Among eighteen people there are four mutual acquaintances or four mutual strangers, and seventeen are not enough; R(5, 5) is unknown, somewhere from 43 to 46.

Greenwood and Gleason proved R(4, 4) = 18 in 1955; the witness that seventeen are not enough is a two-coloring of the complete graph on seventeen vertices with no monochromatic four-clique. Beyond that the subject collapses: R(5, 5) is only known to lie between 43 (Exoo 1989) and 46 (Angeltveit and McKay 2024), and Erdős’s story is that if aliens demanded R(5, 5) we should compute it, but if they demanded R(6, 6) we should attack. Key entry beside R(3, 3) = 6 in the denominator; an integer.

Cites: [6.14](ch06-refs.md#r-6.14)

See also: [the smallest nontrivial Ramsey number](ch06-cards.md#g-ramsey33)

### the seven bridges of Königsberg — `7 bridges` {#g-konigsberg}

*Function or operator*

Could a walk cross each of Königsberg’s seven bridges exactly once? Euler answered no in 1736, and that paper is where graph theory begins.

Königsberg had seven bridges over the Pregel, and the question was whether a walk could cross each one exactly once. Euler’s answer was no, and the reason is the whole of the method: throw away the map. What the walk needs is not distances or shapes but which land masses touch which bridges, and once you have that, a walk that enters a land mass must also leave it, so every land mass except the two endpoints needs an even number of bridges. Königsberg had four with an odd number, so there is no such walk. The paper is Solutio problematis ad geometriam situs pertinentis, and it is the beginning of graph theory. A theorem, uncolored.

Cites: [6.27](ch06-refs.md#r-6.27), [6.33](ch06-refs.md#r-6.33)

### the Petersen graph — `10 vertices, 15 edges` {#g-petersengraph}

*Non-real object*

A ten-vertex, degree-three graph built from a pentagon and a pentagram, the standard small counterexample that disproves many optimistic conjectures in graph theory.

The Petersen graph joins the five points of a pentagon to the five points of a pentagram, one to one, giving ten vertices each of degree three. Julius Petersen published it in 1898 as the smallest bridgeless cubic graph that cannot be properly edge-colored with three colors, though A. B. Kempe had already drawn the same graph in 1886. It has since served as graph theory’s standard counterexample to optimistic conjectures. An object, uncolored.

Cites: [6.39](ch06-refs.md#r-6.39)