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

# Chapter ᚄ(S): The city streets

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

[Guide for AI readers](index.md) · [Its glossary cards](ch06-cards.md) · [Its references](ch06-refs.md) · [Previous chapter](ch05.md) · [Next chapter](ch07.md)

*A footnote such as [r-6.3] is reference entry 6.3 and links to it. Section 6 of 28; chapters are named by their Ogham letter, never by number.*

## Into the city

ᚄ – [Sail](ch06-cards.md#g-og-sail): associated with the willow tree, Section 6

## Chapter ᚄ(S): The city streets

> “Mathematics is the queen of the sciences and number theory is the queen of mathematics.”

> — Carl Friedrich Gauss · as reported by Wolfgang Sartorius von Waltershausen, *Gauss zum Gedächtniss*, 1856 [r-6.35](ch06-refs.md#r-6.35)

Formula: ([(12! + 1) mod 13](ch06-cards.md#g-wilson))/([φ(13)](ch06-cards.md#g-totient) + [2<sup>12</sup> mod 13](ch06-cards.md#g-fermatlittle) + [13 mod 4](ch06-cards.md#g-mod4) + [(3/13)](ch06-cards.md#g-legsym) + [ord<sub>13</sub>(2)](ch06-cards.md#g-ord13)) {brace: [modular arithmetic](ch06.md#ch-T6-modular-arithmetic)} · ([μ(6174)](ch06-cards.md#g-mobius) + ([gcd(12, 18)·lcm(12, 18) − 12·18](ch06-cards.md#g-gcdlcm)))/([gcd(12, 18)](ch06-cards.md#g-gcd1218) + [lcm(12, 18)](ch06-cards.md#g-lcm1218)) {brace: [divisibility](ch06.md#ch-T6-divisibility)} · ([p(9) mod 5](ch06-cards.md#g-partition5))/([p(4)](ch06-cards.md#g-p4)) {brace: [partitions](ch06.md#ch-T6-partitions)} · ([C(2, 5)](ch06-cards.md#g-binomial))/([R(3, 3)](ch06-cards.md#g-ramsey33) + [C<sub>3</sub>](ch06-cards.md#g-catalan3) + [B₃](ch06-cards.md#g-bell3) + [!4](ch06-cards.md#g-derange4)) {brace: [combinatorics](ch06.md#ch-T6-combinatorics)} · ([P(K₃, 2)](ch06-cards.md#g-chrom) + ([10·3 − 2·15](ch06-cards.md#g-handshake)))/([P(K₃, 3)](ch06-cards.md#g-chromK33) + [|E(Petersen)|](ch06-cards.md#g-petersenE)) {brace: [graph theory](ch06.md#ch-T6-graph-theory)}

Key concepts: Modular arithmetic, divisibility, partitions, combinatorics, and graph theory. It includes symbols you may not have seen before, such as: [φ](ch06-cards.md#g-totient), [μ](ch06-cards.md#g-mobius), [C(n, k)](ch06-cards.md#g-binomial), and [P(G, k)](ch06-cards.md#g-chrom). Zero here is a division with nothing left over, two counts that cancel, or a count of ways that is simply empty: you cannot choose five things from two.

The paths open into busy city streets bustling with activity; our bicycles will allow us to keep up. We have spent some time recognizing individual numbers; here we begin asking what we can do with them. Count possible routes, examine the crossings, or let a number line come back around like a clock. There is even a casino on the corner, where we will stop to count possible hands.

The five braces name five activities: keeping remainders, finding factors, breaking a total into parts, counting choices, and studying connections. Mathematicians call them modular arithmetic, divisibility, partitions, combinatorics, and graph theory. Each has its own way to make zero mean something.

Field notes

### [modular arithmetic](ch06.md#ch-T6-modular-arithmetic) {#ch-T6-modular-arithmetic}

On an ordinary twelve-hour clock, 11 + 3 lands on 2. For this brace I have chosen [a clock with thirteen positions, labeled 0 through 12](ch06-cards.md#g-zmod13), where numbers differing by a multiple of 13 share a position. Gauss gave this arithmetic its language of [congruences](ch06-cards.md#g-congr): 14 ≡ 1 modulo 13. Every term here asks a question about the same number, 13, chosen for three properties the terms below put to work: it is prime, it is one more than a multiple of four, and doubling around its clock reaches every nonzero position before coming back to 1. [r-6.20](ch06-refs.md#r-6.20)

#### Numerator

[(12! + 1) mod 13](ch06-cards.md#g-wilson) = 0; Wilson’s theorem, a classic: a [factorial](ch06-cards.md#g-permfact) that can tell whether a number is prime.

12! multiplies 1 through 12, and adding one gives 479,001,601 = 13 × 36,846,277. The reason is general: for p > 1, [(p − 1)! + 1 is divisible by p exactly when p is prime](ch06-cards.md#g-wilson). On a prime clock every nonzero position has a partner that multiplies with it to 1 (2 × 7 = 14 ≡ 1). On ours only 1 and 12 are their own partners (12 × 12 = 144 ≡ 1), so in 1 × 2 × … × 12 the other ten pair off into products of 1, leaving 1 × 12 = 12, one step short of zero; adding 1 lands on zero. [r-6.2](ch06-refs.md#r-6.2) [r-6.1](ch06-refs.md#r-6.1) [r-6.38](ch06-refs.md#r-6.38)

#### Denominator

Five questions about 13: which numbers share no factor with it, what powers do on its clock, whether it is a sum of two squares, whether 3 is a square on that clock, and how long doubling takes to return to 1.

[φ(13)](ch06-cards.md#g-totient) = 12; Euler’s totient, a cornerstone of number theory.

It counts [the positive integers below 13 that share no factor with it](ch06-cards.md#g-totient). Since 13 is prime, all twelve qualify. [r-6.3](ch06-refs.md#r-6.3)

[2<sup>12</sup> mod 13](ch06-cards.md#g-fermatlittle) = 1; Fermat’s little theorem, [the totient](ch06-cards.md#g-totient)’s famous partner and one of the ideas behind [RSA encryption](ch06-cards.md#g-rsa).

For a prime p and any a that p does not divide, a<sup>p−1</sup> leaves remainder 1 on division by p. Directly, 4096 = 315 × 13 + 1. The exponent, 12, is φ(13) again, and that is the partnership: Euler later showed that on any clock, prime or not, a number that shares no factor with the clock’s size lands on 1 when raised to the totient, a result now called [Euler’s theorem](ch06-cards.md#g-eulerthm). [r-6.4](ch06-refs.md#r-6.4) [r-6.37](ch06-refs.md#r-6.37)

[13 mod 4](ch06-cards.md#g-mod4) = 1; the remainder that decides whether an odd prime is a [sum of two squares](ch21-cards.md#g-fermat2sq).

[Thirteen is one more than a multiple of four](ch06-cards.md#g-mod4), and indeed 13 = 2² + 3². [r-6.5](ch06-refs.md#r-6.5)

[(3/13)](ch06-cards.md#g-legsym) = 1; the [Legendre](ch05-cards.md#g-legendre) symbol, from the same [Legendre](ch05-cards.md#g-legendre) whose constant opened the previous chapter.

It asks whether 3 is a nonzero square on the thirteen-position clock. It is: 4² = 16 ≡ 3. [Quadratic reciprocity](ch06-cards.md#g-qrecip) predicts as much without searching: it swaps the question for its mirror image, whether 13 is a square on a three-position clock. There 13 lands on 1, and 1 = 1² is a square; because 13 is one more than a multiple of four, the two questions have the same answer. [r-6.6](ch06-refs.md#r-6.6)

[ord<sub>13</sub>(2)](ch06-cards.md#g-ord13) = 12; chosen because 2 turns out to be a primitive root, touring the whole clock.

It is the smallest exponent k for which 2<sup>k</sup> lands on 1 on this clock. Doubling from 2 gives 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1: the twelfth power is the first to return, and on the way the powers visit every nonzero position. [r-6.7](ch06-refs.md#r-6.7)

The first fraction is 0/27: 12 + 1 + 1 + 1 + 12 = 27.

**Fine print.** The prime matters: on a composite clock some nonzero positions have no multiplicative partner, and [Wilson’s pairing](ch06-cards.md#g-wilson) breaks down. An encryption system like [RSA](ch06-cards.md#g-rsa) needs considerably more than [Fermat’s little theorem](ch06-cards.md#g-fermatlittle).

### [divisibility](ch06.md#ch-T6-divisibility) {#ch-T6-divisibility}

Two questions about factors: does a number repeat a prime, and what do two numbers share? The second has two answers that work as a pair: the greatest common divisor (gcd), the largest number that divides both, and the least common multiple (lcm), the smallest positive number that both divide. [r-6.9](ch06-refs.md#r-6.9)

#### Numerator

[μ(6174)](ch06-cards.md#g-mobius) = 0; [Kaprekar’s constant](ch04-cards.md#g-kaprekar), back from Chapter ᚂ(L), meets a function built to catch repeated primes.

[μ(n)](ch06-cards.md#g-mobius) is 0 whenever n repeats a prime factor; otherwise it is 1 or −1, depending on whether n has an even or an odd number of prime factors. Here 6174 = 2 × 3² × 7³ repeats both 3 and 7. [r-6.8](ch06-refs.md#r-6.8)

[gcd(12, 18)·lcm(12, 18) − 12·18](ch06-cards.md#g-gcdlcm) = 0; a fundamental identity, turned into a zero by subtraction.

The gcd is 6 and the lcm is 36, so this is 216 − 216. It holds for any two positive integers. Here 12 = 2² × 3 and 18 = 2 × 3²; the gcd takes the smaller power of each prime (2 × 3 = 6) and the lcm the larger (2² × 3² = 36), so between them they carry exactly the prime factors of 12 × 18. [r-6.9](ch06-refs.md#r-6.9)

#### Denominator

[gcd(12, 18)](ch06-cards.md#g-gcd1218) = 6; the shared part of our pair, and an excuse to meet [Euclid’s algorithm](ch06-cards.md#g-euclidalg).

Divide and keep the remainder: 18 = 12 + 6, then 12 = 2 × 6. The last nonzero remainder is the gcd, found without factoring either number by a method in use for more than two thousand years. [r-6.10](ch06-refs.md#r-6.10) [r-6.37](ch06-refs.md#r-6.37)

[lcm(12, 18)](ch06-cards.md#g-lcm1218) = 36; the other half of [the identity](ch06-cards.md#g-gcdlcm) above.

[36 is the smallest positive number that both 12 and 18 divide](ch06-cards.md#g-lcm1218).

The second fraction is 0/42: 6 + 36 = 42 (good old [42](ch04-cards.md#g-fortytwo), ha ha ha).

### [partitions](ch06.md#ch-T6-partitions) {#ch-T6-partitions}

A partition writes a number as a sum of positive integers, ignoring order: 3 + 1 and 1 + 3 are the same partition. The function p(n) counts them. [r-6.11](ch06-refs.md#r-6.11)

#### Numerator

[p(9) mod 5](ch06-cards.md#g-partition5) = 0; one beat of [Ramanujan’s famous congruence](ch06-cards.md#g-ramanujancong).

p(9) = 30, a multiple of 5. Ramanujan proved that [p(5n + 4) is always a multiple of 5](ch06-cards.md#g-ramanujancong) ([p(4) = 5](ch06-cards.md#g-p4), p(9) = 30, p(14) = 135), an exact rhythm in counts that look irregular. We use n = 1. [r-6.11](ch06-refs.md#r-6.11) [r-6.12](ch06-refs.md#r-6.12)

#### Denominator

[p(4)](ch06-cards.md#g-p4) = 5; small enough to list, and the rhythm’s first beat (n = 0).

4; 3 + 1; 2 + 2; 2 + 1 + 1; 1 + 1 + 1 + 1.

The third fraction is 0/5.

### [combinatorics](ch06.md#ch-T6-combinatorics) {#ch-T6-combinatorics}

Ah… the casino on the corner. Let’s pop in for a quick look. Every table in here runs on counting choices: what can be picked, arranged, grouped, or shuffled, from the hands a dealer can deal to the hats the coat check can hand back wrong.

#### Numerator

[C(2, 5)](ch06-cards.md#g-binomial) = 0; the simplest impossible choice.

A [binomial coefficient](ch06-cards.md#g-binomial) counts selections without replacement and without regard to order, and there is no way to take five different objects from two. [r-6.13](ch06-refs.md#r-6.13)

#### Denominator

Four counting problems: unavoidable patterns, ways to put in brackets, ways to form groups, and ways to return every hat to the wrong person.

[R(3, 3)](ch06-cards.md#g-ramsey33) = 6; the famous party problem: the first guaranteed trio of mutual acquaintances or mutual strangers.

How many guests force three mutual acquaintances or three mutual strangers? Six, assuming acquaintance is mutual; five can avoid both. This count marks the first unavoidable pattern. [The glossary](ch06-cards.md#g-ramsey33) gives the [pigeonhole proof](ch06-cards.md#g-pigeon) and the five-person example. [r-6.14](ch06-refs.md#r-6.14)

[C<sub>3</sub>](ch06-cards.md#g-catalan3) = 5; a Catalan number, from one of combinatorics’ most common sequences.

There are [five ways to fully bracket four ordered factors](ch06-cards.md#g-catalan3), such as ((ab)c)d and (ab)(cd). [r-6.15](ch06-refs.md#r-6.15)

[B₃](ch06-cards.md#g-bell3) = 5; a Bell number, chosen to sit beside [C₃](ch06-cards.md#g-catalan3): a different activity with the same count.

There are [five ways to split three labeled objects into groups](ch06-cards.md#g-bell3): {abc}, {ab}{c}, {ac}{b}, {bc}{a}, and {a}{b}{c}. [r-6.16](ch06-refs.md#r-6.16)

[!4](ch06-cards.md#g-derange4) = 9; derangements, the classic hat-check problem.

There are [nine ways to hand four hats back so that nobody gets their own](ch06-cards.md#g-derange4). [r-6.17](ch06-refs.md#r-6.17)

The fourth fraction is 0/25: 6 + 5 + 5 + 9 = 25.

**Fine print.** [R(3, 3)](ch06-cards.md#g-ramsey33) treats acquaintance as mutual. The derangement sign [!4](ch06-cards.md#g-derange4) goes before the number; the [factorial](ch06-cards.md#g-permfact)’s goes after it. C(n, k) is a [binomial coefficient](ch06-cards.md#g-binomial); C₃ is [the third Catalan number](ch06-cards.md#g-catalan3); a partition of an integer (p(n)) and a partition of a set ([B₃](ch06-cards.md#g-bell3)) are different activities.

### [graph theory](ch06.md#ch-T6-graph-theory) {#ch-T6-graph-theory}

A *graph* records connections as dots, called vertices, and the lines joining them, called edges; distances and bends do not matter. [Euler’s bridge problem](ch06-cards.md#g-konigsberg) asked whether a walk could cross every bridge exactly once, and reducing land to vertices and bridges to edges exposed the structure of the question. [r-6.27](ch06-refs.md#r-6.27)

#### Numerator

[P(K₃, 2)](ch06-cards.md#g-chrom) = 0; the smallest graph that two colors cannot handle.

The [chromatic polynomial](ch06-cards.md#g-chrom) P(G, k) counts the ways to color the vertices of G with k colors so that neighbors differ. In a triangle, the first two corners use up both colors, leaving none for the third. [r-6.18](ch06-refs.md#r-6.18)

[10·3 − 2·15](ch06-cards.md#g-handshake) = 0; the handshaking lemma, a basic law of graphs, shown on the famous [Petersen graph](ch06-cards.md#g-petersengraph).

[The Petersen graph](ch06-cards.md#g-petersengraph) has ten vertices with three edges at each, and [fifteen edges](ch06-cards.md#g-petersenE). Counting edge ends at the vertices gives 30; counting two ends per edge also gives 30. Every finite undirected graph balances this way. [r-6.19](ch06-refs.md#r-6.19)

#### Denominator

[P(K₃, 3)](ch06-cards.md#g-chromK33) = 6; the same triangle, given one more color.

There are [three choices for the first corner, two for the next, and one for the last](ch06-cards.md#g-chromK33).

[|E(Petersen)|](ch06-cards.md#g-petersenE) = 15; the [Petersen graph](ch06-cards.md#g-petersengraph)’s edges, reused from [the handshake](ch06-cards.md#g-handshake) above.

[The Petersen graph](ch06-cards.md#g-petersengraph), named for Julius Petersen’s paper of 1898, is a ten-vertex graph that has disproved many optimistic guesses about graphs. [r-6.24](ch06-refs.md#r-6.24) [r-6.38](ch06-refs.md#r-6.38) Its ten vertices of degree three give 30 edge ends, hence [15 edges](ch06-cards.md#g-petersenE).

The fifth and final fraction is 0/21: 6 + 15 = 21.

**Fine print.** The colorings are counted with labeled vertices, so swapping two colors counts as a new coloring.

What this chapter adds to the formula: 0/27 · 0/42 · 0/5 · 0/25 · 0/21 = 0

The five braces have explained seven zeros, each in its own way: a factorial that lands on its prime, a repeated prime factor, a canceled identity, [a rhythm in the partition counts](ch06-cards.md#g-ramanujancong), an impossible selection, an impossible coloring, and a graph whose handshakes balance. At the casino, we were counting what could happen; counting becomes more interesting when someone else is choosing too.

Let’s pedal across town to the stadium, where the players have ideas of their own about what ought to happen.

Watch and read

- [Wilson’s Theorem (extra footage)](https://www.youtube.com/watch?v=AiplrfFB6h0) Numberphile, James Grime: the theorem behind the numerator, worked by hand

- [What do 5, 13 and 563 have in common?](https://www.youtube.com/watch?v=eZUa5k_VIZg) Numberphile: Wilson’s theorem itself, and the three known Wilson primes

- [Wilson’s theorem](https://en.wikipedia.org/wiki/Wilson%27s_theorem) Wikipedia

- [Modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic) Wikipedia