# References — Chapter ᚄ(S): The city streets *Teclam Áirme, the Mathematical Compendium — a copy for AI readers of https://www.teclamairme.com/#ref-ch-6, as of 2026-09-30. Links are relative to https://www.teclamairme.com/fortheaireaders/.* [Guide for AI readers](index.md) · [The chapter](ch06.md) *Each entry: one plain sentence saying exactly what it is cited for, its status, then every source with a note saying what that source actually carries. "Own computation" / "Own reading" entries are the author's own work, not outside sources.* ### 6.1 {#r-6.1} Wilson’s theorem says (p−1)! + 1 is divisible by p if and only if p is prime; Waring published it in 1770 and Lagrange supplied the first proof in 1771. *Status: confirmed* - [Encyclopedia of Mathematics, Wilson theorem](https://encyclopediaofmath.org/wiki/Wilson_theorem) — states the iff theorem, Waring 1770, and Lagrange’s 1771 proof. - [MacTutor, Chronology for 1760–1780](https://mathshistory.st-andrews.ac.uk/Chronology/16/) — records Lagrange proving Wilson’s theorem in 1771. ### 6.2 {#r-6.2} For p=13, 12! + 1 = 479001601 = 13 × 36846277, so the remainder is 0. *Status: confirmed* - [Wolfram MathWorld, Wilson’s Theorem](https://mathworld.wolfram.com/WilsonsTheorem.html) — gives the factorial congruence and describes it as a necessary and sufficient primality test. Editorial note: Own arithmetic checked: 12! = 479001600; 13 × 36846277 = 479001601. ### 6.3 {#r-6.3} Euler’s totient counts positive integers at most n coprime to n, and phi(13)=12. φ(n) is the order of the multiplicative group of integers modulo n, and RSA’s exponents e and d satisfy ed ≡ 1 (mod φ(n)). *Status: confirmed* - [Wolfram MathWorld, Euler Totient Function](https://mathworld.wolfram.com/TotientFunction.html) — defines the totient and gives phi(p)=p−1 for primes. - [Euler’s totient function, Wikipedia](https://en.wikipedia.org/wiki/Euler%27s_totient_function) — “This function gives the order of the multiplicative group of integers modulo n”; “Setting up an RSA cryptosystem involves choosing large prime numbers p and q, computing n = pq and k = φ(n), and finding two numbers e and d such that ed ≡ 1 (mod k).” ### 6.4 {#r-6.4} Fermat’s little theorem gives 2^12 ≡ 1 (mod 13), with 4096 = 315 × 13 + 1. *Status: confirmed* - [Wolfram MathWorld, Fermat’s Little Theorem](https://mathworld.wolfram.com/FermatsLittleTheorem.html) — states a^(p−1) congruent to 1 modulo p for p not dividing a. ### 6.5 {#r-6.5} An odd prime is a sum of two squares exactly when it is 1 modulo 4; 13 = 2^2 + 3^2. The prime 2 = 1² + 1² is the one exception, the only prime congruent to 2 modulo 4. *Status: confirmed* - [Wolfram MathWorld, Fermat’s 4n+1 Theorem](https://mathworld.wolfram.com/Fermats4nPlus1Theorem.html) — states the prime criterion for sums of two squares: “Fermat’s theorem, sometimes called Fermat’s two-square theorem or simply “Fermat’s theorem,” states that a prime number can be represented in an essentially unique manner (up to the order of addends) in the form” x² + y² “iff” p ≡ 1 (mod 4) or p = 2 (formulas typeset on the page; the old Two-Square Theorem address is now a one-line pointer to this page). - [Fermat’s 4n+1 Theorem, Wolfram MathWorld](https://mathworld.wolfram.com/Fermats4nPlus1Theorem.html) — “The first few primes which are 1 or 2 (mod 4) are 2, 5, 13, 17, 29, 37, 41, 53, 61, ... (OEIS A002313) (with the only prime congruent to 2 mod 4 being 2).” ### 6.6 {#r-6.6} The Legendre symbol is 1 for a nonzero quadratic residue; 4^2 ≡ 3 (mod 13), so (3/13)=1. *Status: confirmed* - [Wolfram MathWorld, Legendre Symbol](https://mathworld.wolfram.com/LegendreSymbol.html) — defines the symbol and its values for quadratic residues. ### 6.7 {#r-6.7} The multiplicative order is the least positive exponent returning 1; ord_13(2)=12, so 2 is a primitive root modulo 13. The Carmichael function λ(13) = 12 is the largest multiplicative order modulo 13. *Status: confirmed* - [Wolfram MathWorld, Multiplicative Order](https://mathworld.wolfram.com/MultiplicativeOrder.html) — defines multiplicative order as the least positive exponent returning 1 modulo n. - [Carmichael function, Wikipedia](https://en.wikipedia.org/wiki/Carmichael_function) — “In algebraic terms, λ(n) is the exponent of the multiplicative group of integers modulo n. As this is a finite abelian group, there must exist an element whose order equals the exponent, λ(n).”; λ(n) and φ(n) “must be equal in the cases where the multiplicative group is cyclic due to the existence of a primitive root, which is the case for odd prime powers.” Editorial note: Own computation checked by the powers 2,4,8,3,6,12,11,9,5,10,7,1 modulo 13. ### 6.8 {#r-6.8} The Mobius function is zero when an integer has a repeated prime factor; 6174=2×3^2×7^3, so mu(6174)=0. 6174 is Kaprekar’s constant, and the Riemann Hypothesis is equivalent to a growth bound on the partial sums of the Möbius function (the Mertens function). *Status: confirmed* - [NIST DLMF §27.2, Functions](https://dlmf.nist.gov/27.2) — defines the Möbius function (27.2.12): μ(n) is 0 unless every prime exponent of n is 1; the value at 6174 is independently factored below. - [6174, Wikipedia](https://en.wikipedia.org/wiki/6174) — “It is a Kaprekar’s Constant.” - [Mertens function, Wikipedia](https://en.wikipedia.org/wiki/Mertens_function) — “However, the Riemann hypothesis is equivalent to a weaker conjecture on the growth of M(x)” Editorial note: Own factorization checked. ### 6.9 {#r-6.9} For positive integers, gcd(a, b) lcm(a, b)=ab; gcd(12, 18)=6 and lcm(12, 18)=36. *Status: confirmed* - [Wolfram MathWorld, Greatest Common Divisor](https://mathworld.wolfram.com/GreatestCommonDivisor.html) — defines gcd and its basic properties (the gcd–lcm product identity is on the Least Common Multiple line below). - [Least Common Multiple, Wolfram MathWorld](https://mathworld.wolfram.com/LeastCommonMultiple.html) — “The smallest m is given by n=1, LCM(a, b)=(ab)/(GCD(a, b)), so GCD(a, b)LCM(a, b)=ab” Editorial note: Own Euclidean computation: 18=12+6 and 12=2×6. ### 6.10 {#r-6.10} The Euclidean algorithm computes a gcd by repeated division. *Status: confirmed* - [Wolfram MathWorld, Euclidean Algorithm](https://mathworld.wolfram.com/EuclideanAlgorithm.html) — describes repeated division as the gcd algorithm. ### 6.11 {#r-6.11} The partition function counts unordered sums of positive integers; p(4)=5, p(9)=30 and p(14)=135. *Status: confirmed* - [NIST DLMF §27.14, Unrestricted Partitions](https://dlmf.nist.gov/27.14) — defines p(n) as unordered sums of positive integers and records Ramanujan’s p(5n+4) congruence. - [Integer partition, Wikipedia](https://en.wikipedia.org/wiki/Integer_partition) — “For instance, p(4) = 5 because the integer 4 has the five partitions 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, and 4.”; “The values of this function for n = 0, 1, 2, … are: 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, …” ### 6.12 {#r-6.12} Ramanujan’s congruence p(5n+4) ≡ 0 (mod 5) holds for every n≥0, so both p(9) mod 5 and p(4) mod 5 are 0. *Status: confirmed* - [NIST DLMF §27.14(v), Divisibility Properties](https://dlmf.nist.gov/27.14.v) — states p(5n+4) congruent to 0 modulo 5 for all n. Editorial note: Own arithmetic checked: 30 mod 5 = 0 and 5 mod 5 = 0. ### 6.13 {#r-6.13} The binomial coefficient counts k-element choices from n elements, and C(2, 5)=0. When k exceeds n, C(n, k) is defined to be 0. *Status: confirmed* - [Wolfram MathWorld, Binomial Coefficient](https://mathworld.wolfram.com/BinomialCoefficient.html) — defines C(n, k) as the number of k-subsets and gives the zero case when k exceeds n. - [Binomial coefficient, Wikipedia](https://en.wikipedia.org/wiki/Binomial_coefficient) — “When n is a nonnegative integer and k is an integer such that k < 0 or k > n, it is common to define” the coefficient to be 0. ### 6.14 {#r-6.14} R(3, 3)=6: among six people there are three mutual acquaintances or three mutual strangers, while five do not suffice. R(4, 4)=18, and R(5, 5) is known only to lie between 43 and 46. The witness for five is K5 drawn as a pentagon in one color and the pentagram inside it in the other; Ramsey proved the general theorem in a paper of 1930. The only two-coloring of seventeen points with no four-clique of one color is the Paley graph of order 17; Erdős’s aliens story, told by Joel Spencer, sets R(5, 5) against R(6, 6). *Status: confirmed* - [Wolfram MathWorld, Ramsey Number](https://mathworld.wolfram.com/RamseyNumber.html) — gives the party-problem definition, R(3, 3)=6 and R(4, 4)=18, credited in its table to Greenwood and Gleason (1955), and the bounds for R(5, 5), 43 from Exoo (1989) and 46 from Angeltveit and McKay (2024). - [Theorem on friends and strangers, Wikipedia](https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers) — “We draw K5 as a pentagon surrounding a star (a pentagram). We color the edges of the pentagon red and the edges of the star blue.”; “In 1930, in a paper entitled ‘On a Problem of Formal Logic,’ Frank Ramsey proved a very general theorem (now known as Ramsey’s theorem) of which this theorem is a simple case.” - [Ramsey’s theorem, Wikipedia](https://en.wikipedia.org/wiki/Ramsey%27s_theorem) — on R(4, 4): “only one (4, 4, 17) graph (the Paley graph of order 17) among 2.46 × 10^26 colourings. It follows that R(4, 4) = 18.”; and, quoting Joel Spencer, “Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and demanding the value of R(5, 5) or they will destroy our planet. In that case, he claims, we should marshal all our computers and all our mathematicians and attempt to find the value. But suppose, instead, that they ask for R(6, 6). In that case, he believes, we should attempt to destroy the aliens.” ### 6.15 {#r-6.15} The third Catalan number is 5 and counts, among other things, bracketings of four factors and triangulations of a pentagon. Stanley’s monograph Catalan Numbers (2015) lists 214 combinatorial interpretations of C_n. *Status: confirmed* - [Wolfram MathWorld, Catalan Number](https://mathworld.wolfram.com/CatalanNumber.html) — lists the sequence and its bracketing and polygon-triangulation interpretations. - [Richard P. Stanley, Catalan Numbers (talk slides, 13 March 2024), author’s MIT page](https://math.mit.edu/~rstan/transparencies/wellesley.pdf) — “R. Stanley, Catalan Numbers, Cambridge University Press, 2015. Includes 214 combinatorial interpretations of Cn and 68 additional problems.” ### 6.16 {#r-6.16} The third Bell number is 5 and counts partitions of a three-element set into nonempty blocks. S(4, 1), S(4, 2), S(4, 3), S(4, 4) = 1, 7, 6, 1, and their sum is the fourth Bell number, B₄ = 15. *Status: confirmed* - [Wolfram MathWorld, Bell Number](https://mathworld.wolfram.com/BellNumber.html) — defines Bell numbers as set partitions and gives B3=5; from n = 1 “the first few Bell numbers” “are 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, ... (OEIS A000110),” so B₄ = 15. - [Stirling numbers of the second kind, Wikipedia](https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind) — “The 15 partitions of a 4-element set ordered in a Hasse diagram”; “There are S(4, 1), ..., S(4, 4) = 1, 7, 6, 1 partitions containing 1, 2, 3, 4 sets.” ### 6.17 {#r-6.17} The number of derangements of four objects is !4=9. *Status: confirmed* - [Wolfram MathWorld, Derangement](https://mathworld.wolfram.com/Derangement.html) — defines derangements, gives the recurrence relations, and lists them from n = 1: “The first few are 0, 1, 2, 9, 44, 265, 1854, ... (OEIS A000166).” ### 6.18 {#r-6.18} The chromatic polynomial counts proper vertex colorings; for a triangle it is k(k−1)(k−2), giving 0 at k=2 and 6 at k=3. An equilateral triangle has six symmetries, the dihedral group D3, the same number as its proper 3-colorings. *Status: confirmed* - [Wolfram MathWorld, Chromatic Polynomial](https://mathworld.wolfram.com/ChromaticPolynomial.html) — defines the chromatic polynomial and gives the triangle polynomial k(k−1)(k−2). - [Dihedral group of order 6, Wikipedia](https://en.wikipedia.org/wiki/Dihedral_group_of_order_6) — the triangle’s symmetries number six: “One way to interpret the dihedral group D3 geometrically is by observing the symmetry of an equilateral triangle.” and “Six transformations are the results.” ### 6.19 {#r-6.19} The handshaking lemma says the sum of degrees is twice the edge count; the Petersen graph has ten degree-three vertices and fifteen edges. Euler first proved the handshaking lemma in his 1736 paper on the Königsberg bridges, where it governs when an Euler path or tour exists. *Status: confirmed* - [Wolfram MathWorld, Handshaking Lemma](https://mathworld.wolfram.com/HandshakingLemma.html) — states that the sum of vertex degrees is twice the number of edges. - [Wolfram MathWorld, Petersen Graph](https://mathworld.wolfram.com/PetersenGraph.html) — records Petersen’s 1898 introduction and the graph’s standard structural properties. - [Handshaking lemma, Wikipedia](https://en.wikipedia.org/wiki/Handshaking_lemma) — ties the lemma to Euler and the bridges: “Leonhard Euler first proved the handshaking lemma in his work on the Seven Bridges of Königsberg” and “Euler stated the fundamental results for this problem in terms of the number of odd vertices in the graph, which the handshaking lemma restricts to be an even number.” ### 6.20 {#r-6.20} Gauss’s congruence notation records equality of remainders modulo n, and modular addition, subtraction and multiplication are well-defined. Gauss introduced the sign ≡ in print in the Disquisitiones Arithmeticae of 1801, article 2. *Status: confirmed* - [Wolfram MathWorld, Modular Arithmetic](https://mathworld.wolfram.com/ModularArithmetic.html) — defines congruence and modular arithmetic. - [Earliest Uses of Symbols of Number Theory, MacTutor](https://mathshistory.st-andrews.ac.uk/Miller/mathsym/nth/) — “The congruent symbol used in number theory ≡ was introduced in print in 1801 by Carl Friedrich Gauss (1777-1855) in Disquisitiones arithmeticae,” citing “Disquisitiones arithmeticae (Leipzig, 1801), art. 2.” ### 6.21 {#r-6.21} The Chinese remainder theorem combines congruences to pairwise coprime moduli into one solution modulo their product. *Status: confirmed* - [Wolfram MathWorld, Chinese Remainder Theorem](https://mathworld.wolfram.com/ChineseRemainderTheorem.html) — states unique simultaneous solutions for pairwise coprime moduli. ### 6.22 {#r-6.22} Factorials count orderings, and binomial coefficients count unordered choices. *Status: confirmed* - [Wolfram MathWorld, Factorial](https://mathworld.wolfram.com/Factorial.html) — defines n! and its counting interpretation. - [Wolfram MathWorld, Binomial Coefficient](https://mathworld.wolfram.com/BinomialCoefficient.html) — defines C(n, k) as the number of k-subsets and gives the zero case when k exceeds n. ### 6.23 {#r-6.23} The historical attribution of Wilson’s theorem is stable, but the dates and priority claims around Ibn al-Haytham, Leibniz, Wilson, Waring and Lagrange are reported differently across reference works. Lagrange’s proof is dated 1771 by the Encyclopedia of Mathematics and MacTutor but 1773 by MathWorld, so the card gives no year for it. Corrections welcome. *Status: judgement* - [Wolfram MathWorld, Wilson’s Theorem](https://mathworld.wolfram.com/WilsonsTheorem.html) — gives the factorial congruence and describes it as a necessary and sufficient primality test, and gives 1773: “It was proved by Lagrange in 1773.” - [Encyclopedia of Mathematics, Wilson theorem](https://encyclopediaofmath.org/wiki/Wilson_theorem) — states the iff theorem, Waring 1770, and Lagrange’s 1771 proof. - [MacTutor, Chronology for 1760–1780](https://mathshistory.st-andrews.ac.uk/Chronology/16/) — records Lagrange proving Wilson’s theorem in 1771. Editorial note: We follow the 1770 Waring / 1771 Lagrange chronology because the Encyclopedia of Mathematics and MacTutor agree on it, while retaining the older attributions only as qualified historical context. ### 6.24 {#r-6.24} The Petersen graph, ten vertices of degree three and fifteen edges, is a standard counterexample in graph theory; Julius Petersen constructed it in 1898 as the smallest bridgeless cubic graph with no three-edge-coloring, and the same graph had already appeared in a paper of A. B. Kempe in 1886. *Status: judgement* - [Wolfram MathWorld, Petersen Graph](https://mathworld.wolfram.com/PetersenGraph.html) — records Petersen’s 1898 introduction and the graph’s standard structural properties. - [Wikipedia, Petersen graph](https://en.wikipedia.org/wiki/Petersen_graph) — gives Petersen’s 1898 construction, quotes Knuth calling the graph “a counterexample to many optimistic predictions about what might be true for graphs in general,” records its first appearance twelve years earlier in Kempe (1886) as the ten lines of the Desargues configuration, and cites Holton and Sheehan, The Petersen Graph (Cambridge, 1993). Editorial note: “The counterexample to nearly every conjecture in graph theory” is a figure of speech: no source states it, and there is no list of conjectures to check it against. The page uses Knuth’s description instead — a counterexample to many optimistic predictions about graphs in general — which is a named claim by a named authority, and which Holton and Sheehan’s book-length study of this one graph bears out. ### 6.25 {#r-6.25} Euclid’s algorithm computes a gcd by repeated division, and Knuth calls it the oldest nontrivial algorithm that has survived to the present day. It is Proposition 2 of Book VII of the Elements, which r-12.12 dates to Euclid’s lifetime, about 325 to 265 BC. *Status: confirmed* - [Wolfram MathWorld, Euclidean Algorithm](https://mathworld.wolfram.com/EuclideanAlgorithm.html) — describes repeated division as the gcd algorithm. - [Wikipedia, Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) — quotes Donald Knuth, The Art of Computer Programming, Vol. 2, 2nd edition (1981), p. 318, calling the algorithm “the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day.” Editorial note: No source states the unqualified superlative “the oldest algorithm still in daily use,” and there is no register of ancient algorithms against which to check it. Knuth’s qualified form is what the page claims instead, in his own words. ### 6.26 {#r-6.26} The Mobius function is 0 when its argument is divisible by the square of a prime and (-1)^k otherwise, where k is the number of prime factors; A. Mobius introduced it in 1832. *Status: confirmed* - [Encyclopedia of Mathematics, Mobius function](https://encyclopediaofmath.org/wiki/M%C3%B6bius_function) — defines mu(1)=1, mu(n)=0 if n is divisible by the square of a prime and mu(n)=(-1)^k otherwise, and states that the function was introduced by A. Mobius in 1832. Editorial note: Added because r-6.8’s only source is a DLMF inversion-formula section that uses the Mobius function without defining it; this entry carries the zero-on-repeated-prime-factor definition the chapter and the mobius card both state, and the 1832 date the prose gives. ### 6.27 {#r-6.27} Euler answered the Konigsberg bridge problem in the negative in 1736, and that paper is the beginning of graph theory. *Status: confirmed* - [Wolfram MathWorld, Koenigsberg Bridge Problem](https://mathworld.wolfram.com/KoenigsbergBridgeProblem.html) — states that the problem “was answered in the negative by Euler (1736),” that the work “represented the beginning of graph theory,” and cites Euler, Solutio problematis ad geometriam situs pertinentis, Comment. Acad. Sci. U. Petrop. 8, 128-140, 1736. ### 6.29 {#r-6.29} Gauss, born on 30 April 1777, published the Disquisitiones Arithmeticae in the summer of 1801, aged twenty-four; the theory of congruences, in which congruences to one and the same modulus can be added, subtracted and multiplied like equalities, was first systematically developed by him. Gauss defines primitive roots in article 57 of the Disquisitiones and credits the term itself to Euler; article 56 records that Lambert and Euler knew of them, and Gauss’s own contribution, in articles 54 and 55, is the first rigorous proof that a primitive root exists for every prime. Article 1 of the Disquisitiones defines congruence as divisibility of the difference, article 2 introduces the sign ≡, and Gauss’s footnote says he chose it for the great analogy between equality and congruence. Euler introduced the totient function in 1763; the notation φ comes from Gauss’s Disquisitiones Arithmeticae of 1801. *Status: confirmed* - [MacTutor, Carl Friedrich Gauss](https://mathshistory.st-andrews.ac.uk/Biographies/Gauss/) — gives the birth date 30 April 1777 and states that “He published the book Disquisitiones Arithmeticae in the summer of 1801,” which puts Gauss at twenty-four. - [Encyclopedia of Mathematics, Congruence](https://encyclopediaofmath.org/wiki/Congruence) — defines a congruence modulo m as the divisibility of a - b by m, states that congruences to the same modulus “can be added, subtracted and multiplied in the same way as normal equalities,” and records that the theory of congruences “was first systematically developed by C.F. Gauss.” - [Disquisitiones arithmeticae, Sectio prima, Latin Wikisource](https://la.wikisource.org/wiki/Disquisitiones_arithmeticae/Sectio_prima) — the primary text: article 1, “Si numerus a numerorum b,c differentiam metitur, b et c secundum a congrui dicuntur”; article 2, “Numerorum congruentiam hoc signo, ≡, in posterum denotabimus”; and its footnote, “Hoc signum propter magnam analogiam quae inter aequalitatem atque congruentiam invenitur adoptavimus.” - [Primitive root modulo n, Wikipedia](https://en.wikipedia.org/wiki/Primitive_root_modulo_n) — “Gauss defined primitive roots in Article 57 of his Disquisitiones Arithmeticae (1801), where he credited Leonhard Euler with coining the term. In Article 56 he stated that Johann Heinrich Lambert and Euler knew of them, but he was the first to rigorously demonstrate that primitive roots exist for a prime number n.” - [Euler’s totient function, Wikipedia](https://en.wikipedia.org/wiki/Euler%27s_totient_function) — “Leonhard Euler introduced the function in 1763.”; “The now-standard notation φ(A) comes from Gauss’s 1801 treatise Disquisitiones Arithmeticae, although Gauss did not use parentheses around the argument and wrote φA.” Editorial note: Neither source ties the congruence notation itself to the year 1801 in so many words: MacTutor dates the Disquisitiones and the Encyclopedia of Mathematics names Gauss as the first systematic developer of the theory. The two together carry the chapter’s sentence; the notation’s first appearance in the book’s opening lines is not separately sourced here. ### 6.30 {#r-6.30} George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs, in an attempt to prove the four color theorem. The four color theorem was proved by Appel and Haken in 1976, by way of reducible configurations. *Status: confirmed* - [Wikipedia, Chromatic polynomial](https://en.wikipedia.org/wiki/Chromatic_polynomial) — states that “George David Birkhoff introduced the chromatic polynomial in 1912, defining it only for planar graphs, in an attempt to prove the four color theorem,” and gives the triangle’s polynomial as x(x-1)(x-2). - [Four color theorem, Wikipedia](https://en.wikipedia.org/wiki/Four_color_theorem) — on the eventual proof: “the four color theorem resisted until 1976, when it was proven by Kenneth Appel and Wolfgang Haken in a computer-aided proof” and “The Appel–Haken proof proceeds by analyzing a very large number of “reducible configurations,” examples of maps with a particular property.” Editorial note: r-6.18’s MathWorld page carries the triangle polynomial but names Birkhoff only in its bibliography (A Determinant Formula for the Number of Ways of Coloring a Map, Ann. Math. 14, 42-46, 1912) and never states the four-color motivation. ### 6.31 {#r-6.31} Ramanujan’s 1919 paper proves the partition congruences modulo 5 and modulo 7; the proof of the modulo 11 congruence was extracted by G. H. Hardy from an unpublished manuscript after Ramanujan’s death in 1920 and published in 1921. *Status: confirmed* - [Wikipedia, Ramanujan’s congruences](https://en.wikipedia.org/wiki/Ramanujan%27s_congruences) — states that “In his 1919 paper, he proved the first two congruences” and that “After Ramanujan died in 1920, G. H. Hardy extracted proofs of all three congruences from an unpublished manuscript of Ramanujan on p(n) (Ramanujan, 1921).” Editorial note: The chapter’s prose and the partition5 card both say Ramanujan proved the congruence “with companion congruences modulo 7 and 11.” All three proofs are his, but only the 5 and 7 cases are in the 1919 paper; the 11 case appeared posthumously in 1921. ### 6.32 {#r-6.32} Fermat stated the little theorem in a letter of 18 October 1640 to Frenicle de Bessy; the first published proof is Euler’s, in the 1736 paper Theorematum quorundam ad numeros primos spectantium demonstratio. *Status: confirmed* - [Wikipedia, Fermat’s little theorem](https://en.wikipedia.org/wiki/Fermat%27s_little_theorem) — states that Fermat first stated the theorem in a letter dated 18 October 1640 to Frenicle de Bessy, and that Euler provided the first published proof in 1736 in Theorematum quorundam ad numeros primos spectantium demonstratio; also “Fermat’s little theorem is the basis for the Fermat primality test,” and, of its generalization, “Euler’s theorem is used with n not prime in public-key cryptography, specifically in the RSA cryptosystem.” - [Encyclopedia of Mathematics, Fermat little theorem](https://encyclopediaofmath.org/wiki/Fermat_little_theorem) — gives the congruence a^(p-1) = 1 (mod p) for a not divisible by the prime p and states that the theorem “was established by P. Fermat (1640).” Editorial note: Added for Q6.2. The fermatlittle card said Euler proved the theorem in 1736 while its only source, MathWorld, dates the first published proof to 1749. Two different Euler papers are in circulation under that description, so the card now says first published proof and names the 1736 one, and this entry carries both halves of the sentence. The Encyclopedia of Mathematics source was moved here on 17 September 2026 from the former entry 6.28, which said only “Fermat stated the little theorem in 1640,” was cited by nobody, and was retired as redundant with this entry; the move leaves the 1640 date resting on two independent sources instead of one. ### 6.33 {#r-6.33} In the Königsberg graph one land mass is touched by 5 bridges and each of the other three by 3, so all four have odd degree; a walk crossing every edge exactly once needs a connected graph with exactly zero or two odd-degree nodes, which is why no such walk exists. *Status: confirmed* - [Wikipedia, Seven Bridges of Königsberg](https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg) — states that “one is touched by 5 bridges, and each of the other three is touched by 3,” that “a necessary condition for the walk of the desired form is that the graph be connected and have exactly zero or two nodes of odd degree,” names Euler’s 1736 paper Solutio problematis ad geometriam situs pertinentis, and records that the solution “is considered to be the first theorem of graph theory.” Editorial note: Added with the konigsberg card. r-6.27 carries the negative answer, the year and the founding status, but not the degree count or the odd-vertex condition, which is the argument the card explains. ### 6.34 {#r-6.34} The dated attributions on this chapter’s cards are as stated. Fermat stated the two-squares theorem in a letter to Mersenne of 25 December 1640 and Euler announced the first proof, by infinite descent, in letters to Goldbach of 6 May 1747 and 12 April 1749, publishing it in detail between 1752 and 1755. Legendre introduced his symbol in 1797 or 1798; the source gives both years, and corrections are welcome. Gauss first proved quadratic reciprocity, which Euler and Legendre had conjectured, on 8 April 1796 by his own diary, called it privately the golden theorem, published the first two proofs in the Disquisitiones Arithmeticae of 1801, and gave eight proofs in all, six published and two found in his posthumous papers. E. H. Moore proved in 1893 that the order of a finite field is a prime power and that fields of each prime-power order exist and are all isomorphic. Gabriel Lame proved in 1844 that Euclid’s algorithm never needs more steps than five times the number of decimal digits of the smaller integer. Pascal’s Traite du triangle arithmetique was written in 1654 and published posthumously in 1665, and the triangle was known earlier in India, Persia and China, appearing in Zhu Shijie’s Siyuan Yujian of 1303. Frank Ramsey’s theorem was published in 1930. Greenwood and Gleason established R(3, 3)=6, R(3, 4)=9 and R(4, 4)=18 in 1955. Euler described the Catalan sequence in 1751 through polygon triangulations, the numbers are named for Eugene Charles Catalan, and Ming Antu had reached them in China earlier. Dobinski gave his formula for the Bell numbers in 1877, Eric Temple Bell wrote about them in a paper of 1934 on Bell polynomials and one of 1938 in which he said they had been rediscovered many times, and Becker and Riordan gave them his name in 1948; the earliest exhaustive enumeration of set partitions was the medieval Japanese incense game genjiko. Pierre Remond de Montmort posed the derangement problem in the Essay d’analyse sur les jeux de hazard in 1708 and solved it in 1713, as did Nicholas Bernoulli, and the name subfactorial is William Allen Whitworth’s. Euler proved his partition theorem in 1748, Hardy and Ramanujan found the asymptotic size of p(n) in 1918, Rademacher gave a convergent exact series in 1937, and p(100) = 190,569,292. Euler introduced the generating function of the partition function in a paper presented in 1741 and printed in 1751, and discussed it in the Introductio of 1748. Any of these three years could be called the date of the generating function, so the card says the 1740s; corrections welcome. *Status: confirmed* - [Fermat’s theorem on sums of two squares, Wikipedia](https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares) — read as raw HTML: Fermat wrote the statement “in a letter to Marin Mersenne dated December 25, 1640,” and of Euler, “The first proof was found by Euler after much effort and is based on infinite descent. He announced it in two letters to Goldbach, on May 6, 1747 and on April 12, 1749; he published the detailed proof in two articles (between 1752 and 1755).” The card’s “proved by Euler in 1749” is the second announcement; the printing is later. - [Legendre symbol, Wikipedia](https://en.wikipedia.org/wiki/Legendre_symbol) — read as raw HTML: “The Legendre symbol was introduced by Adrien-Marie Legendre in 1797 or 1798 in the course of his attempts at proving the law of quadratic reciprocity.” The source hedges between the two years, and so does the card. - [Quadratic reciprocity, Wikipedia](https://en.wikipedia.org/wiki/Quadratic_reciprocity) — read as raw HTML: “The quadratic reciprocity theorem was conjectured by Leonhard Euler and Adrien-Marie Legendre and first proved by Carl Friedrich Gauss”; Gauss “referred to it as the ‘fundamental theorem’ in his Disquisitiones Arithmeticae” and “Privately, Gauss referred to it as the ‘golden theorem’. He published six proofs for it, and two more were found in his posthumous papers,” which is the eight the card counts; the first proof is dated by “his mathematical diary entry for April 8, 1796 (the date he first proved quadratic reciprocity),” and “Gauss published the first and second proofs of the law of quadratic reciprocity on arts 125-146 and 262 of Disquisitiones Arithmeticae in 1801”; and, of a later proof, “This proof served as a template for class field theory, which can be viewed as a vast generalization of quadratic reciprocity.” - [Finite field, Wikipedia](https://en.wikipedia.org/wiki/Finite_field) — read as raw HTML: “the following classification theorem first proved in 1893 by E. H. Moore: The order of a finite field is a prime power. For every prime power q there are fields of order q, and they are all isomorphic.” - [Euclidean algorithm, Wikipedia](https://en.wikipedia.org/wiki/Euclidean_algorithm) — read as raw HTML: “the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844 (Lamé’s Theorem), and marks the beginning of computational complexity theory.” - [Pascal’s triangle, Wikipedia](https://en.wikipedia.org/wiki/Pascal%27s_triangle) — read as raw HTML: “Pascal’s Traité du triangle arithmétique (Treatise on Arithmetical Triangle) was published posthumously in 1665,” its page images being dated 1654; the page also records Tartaglia publishing six rows in 1556, Cardano in 1570, and the Chinese diagram in Zhu Shijie’s Siyuan Yujian of 1303. - [Ramsey’s theorem, Wikipedia](https://en.wikipedia.org/wiki/Ramsey%27s_theorem) — read as raw HTML: the paper is given as Ramsey, F. P. (1930), “On a problem of formal logic,” Proceedings of the London Mathematical Society 30, 264-286. The page gives no 1928 date. - [Wolfram MathWorld, Ramsey Number](https://mathworld.wolfram.com/RamseyNumber.html) — read as raw HTML: its table of known values credits “Greenwood and Gleason (1955)” for R(3, 3)=6, R(3, 4)=9, R(3, 5)=14 and R(4, 4)=18, and records that “Exoo (1989) proved that R(5, 5) ≥ 43 and Angeltveit and McKay (2024) proved that R(5, 5) ≤ 46.” - [Catalan number, Wikipedia](https://en.wikipedia.org/wiki/Catalan_number) — read as raw HTML: “The Catalan sequence was described in 1751 by Leonhard Euler, who was interested in the number of different ways of dividing a polygon into triangles. The sequence is named after Eugène Charles Catalan, who discovered the connection to parenthesized expressions during his exploration of the Towers of Hanoi puzzle.” The page carries no year for Catalan and links Larcombe, “The 18th century Chinese discovery of the Catalan numbers,” for Ming Antu. - [OEIS A000108, the Catalan numbers](https://oeis.org/A000108) — read as raw HTML: “A very large number of combinatorial interpretations are known - see references, esp. R. P. Stanley, ‘Catalan Numbers’, Cambridge University Press, 2015,” which is the catalogue the card means. Neither this page nor Wikipedia’s states a count, so “more than two hundred families” is the book’s own reading of that book. - [Bell number, Wikipedia](https://en.wikipedia.org/wiki/Bell_number) — read as raw HTML: “The Bell numbers are named after Eric Temple Bell, who wrote about them in 1938, following up a 1934 paper in which he studied the Bell polynomials”; “in his 1938 paper, he wrote that the Bell numbers ‘have been frequently investigated’ and ‘have been rediscovered many times’”; “Bell cites several earlier publications on these numbers, beginning with Dobiński 1877 which gives Dobiński’s formula”; “the name ‘Bell numbers’ and the notation Bₙ … was given to them by Becker & Riordan 1948”; and “The first exhaustive enumeration of set partitions appears to have occurred in medieval Japan, where … a parlor game called genjikō sprang up.” - [Derangement, Wikipedia](https://en.wikipedia.org/wiki/Derangement) — read as raw HTML: “The problem of counting derangements was first considered by Pierre Raymond de Montmort in his Essay d’analyse sur les jeux de hazard in 1708; he solved it in 1713, as did Nicholas Bernoulli at about the same time,” and “The name ‘subfactorial’ originates with William Allen Whitworth”; and, of e^−1 ≈ 0.367879, “This is the limit of the probability that a randomly selected permutation of a large number of objects is a derangement.” - [Partition function (number theory), Wikipedia](https://en.wikipedia.org/wiki/Partition_function_(number_theory)) — read as raw HTML: “This asymptotic formula was first obtained by G. H. Hardy and Ramanujan in 1918 and independently by J. V. Uspensky in 1920,” and “In 1937, Hans Rademacher was able to improve on Hardy and Ramanujan’s results by providing a convergent series expression for p(n).” - [Integer partition, Wikipedia](https://en.wikipedia.org/wiki/Integer_partition) — read as raw HTML, for the 1748 date: of the identity between partitions into odd parts and into distinct parts, “This result was proved by Leonhard Euler in 1748.” The page does not date the generating function; Jordan Bell’s paper below has Euler introduce it in a paper presented in 1741 and printed in 1751, and discuss it in the Introductio of 1748. - **Own computation** (the author's own work) — p(100) computed by the standard coin-change recurrence over parts 1 to 100: p(100) = 190,569,292, and the same recurrence gives p(4) = 5 and p(9) = 30, which are the values r-6.11 cites from DLMF. - [Traité du triangle arithmétique, Cambridge Digital Library](https://cudl.lib.cam.ac.uk/view/PR-CCB-00013-00024/1) — “In 1654 Blaise Pascal entered into correspondence with Pierre de Fermat of Toulouse about some problems in calculating the odds in games of chance, as a result of which he wrote the Traité du triangle arithmétique, avec quelques autres petits traitez sur la mesme matière, probably in August of that year. Not published until 1665” - [Jordan Bell, Euler and the pentagonal number theorem, arXiv math/0510054](https://arxiv.org/abs/math/0510054) — “presented to the St. Petersburg Academy on April 6, 1741 and published in 1751”; “In this paper Euler introduces the generating function”; “In §323 (in ch. XVI, “De partitione numerorum”) of the Introductio in analysin infinitorum [Euler, 1748], E101, published in 1748, Euler notes in his discussion on the generating function” Editorial note: Added 17 September 2026 for the B6 pass. Eleven cards in this chapter carried dated attributions on entries whose claim lines stop at the mathematics - MathWorld and DLMF definitions with no history in them. Four entries for exactly this pattern already existed and had been attached last pass (6.23, 6.26, 6.29, 6.30, 6.31), so this entry finishes the block rather than starting it. Three dates could not be sourced and were handled rather than asserted. Ramsey: no source found dates the proof to 1928, and the paper is 1930, so the card now says 1930 and the 1928 reading, which is the year the paper was read to the London Mathematical Society, is left out. Catalan: no source found gives 1838 for Catalan’s own work, so the card no longer gives a year for him. Stanley’s catalogue: no source states a count, so “more than two hundred families” is flagged above as the book’s own reading of Stanley’s Catalan Numbers (2015). One more nuance worth keeping: the Legendre symbol source hedges between 1797 and 1798, and Euler’s two-squares proof was announced in 1747 and 1749 and printed between 1752 and 1755, so “proved by Euler in 1749” is the announcement. ### 6.35 {#r-6.35} The chapter epigraph is Gauss’s, as reported by Wolfgang Sartorius von Waltershausen in Gauss zum Gedaechtniss of 1856. *Status: confirmed* - [Carl Friedrich Gauss, Wikiquote](https://en.wikiquote.org/wiki/Carl_Friedrich_Gauss) — read as raw HTML: “Mathematics is the queen of the sciences. As quoted in Gauss zum Gedächtniss (1856) by Wolfgang Sartorius von Waltershausen; Variants: Mathematics is the queen of sciences and number theory is the queen of mathematics,” which is the epigraph’s form. Editorial note: Added 17 September 2026 to source the chapter epigraph, which carried no marker. Another of the four secondhand ones: what survives is Sartorius’s report of 1856, not anything Gauss printed, and the claim line says so. ### 6.36 {#r-6.36} RSA is a public-key cryptosystem publicly described in 1977 by Ron Rivest, Adi Shamir and Leonard Adleman, and described in Scientific American’s Mathematical Games column in August 1977, before the patent filing of December 1977. An equivalent system was developed secretly in 1973 at GCHQ by Clifford Cocks and declassified in 1997. Its arithmetic is exponentiation modulo the product of two primes, with the exponents paired modulo the totient. *Status: confirmed* - [RSA cryptosystem, Wikipedia](https://en.wikipedia.org/wiki/RSA_cryptosystem) — read as raw HTML: “Ron Rivest, Adi Shamir and Leonard Adleman, who publicly described the algorithm in 1977… An equivalent system was developed secretly in 1973 at Government Communications Headquarters (GCHQ)… by the English mathematician Clifford Cocks. That system was declassified in 1997,” and “A detailed description of the algorithm was published in August 1977, in Scientific American’s Mathematical Games column… This preceded the patent’s filing date of December 1977.” Editorial note: The chapter’s own sentence is a warning rather than a recipe — Fermat’s little theorem alone is not an encryption system — and this entry carries only the history and the shape of the arithmetic, not any claim about the security of any key size. ### 6.37 {#r-6.37} Dates and attributions printed on this chapter’s glossary cards and in its field notes, each checked against the source listed: Ming Antu had found the Catalan numbers in China around 1730; Gauss restated the Chinese remainder theorem in 1801; Euler’s paper proving his theorem was presented to the Berlin Academy in 1758 and printed in 1763, and does not yet name the totient; Euler’s paper proving his theorem was printed in 1763; Gauss wrote [x] for the floor in his third proof of quadratic reciprocity (1808); Iverson named floor and ceiling in A Programming Language (1962); Euclid’s algorithm, Elements VII.2, about 300 BC; The notation n! is Christian Kramp’s, 1808; the Petersen graph is named for Julius Petersen’s paper of 1898 and had already appeared in a paper of A. B. Kempe in 1886. The Iverson bracket began in the same 1962 book, in parentheses; the square-bracket form was Knuth’s. Stirling stated his approximation in a 1729 letter to de Moivre and showed in 1730 that its constant is √(2π); the card gives both years rather than choose one. Corrections welcome. *Status: confirmed* - [Catalan number, Wikipedia](https://en.wikipedia.org/wiki/Catalan_number) — read raw: “In 1988, it came to light that the Catalan number sequence had been used in China by the Mongolian mathematician Mingantu by 1730, when he started to write his book Ge Yuan Mi Lu Jie Fa.” - [Chinese remainder theorem, Wikipedia](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) — read raw: “The Chinese remainder theorem appears in Gauss’s 1801 book Disquisitiones Arithmeticae.”; “Both names of the theorem refer to its earliest known statement that appeared in Sunzi Suanjing, a Chinese manuscript written during the 3rd to 5th century CE”; “a complete solution called Da-yan-shu (大衍術) in Qin Jiushao’s 1247 Mathematical Treatise in Nine Sections”; “Most implementations of RSA use the Chinese remainder theorem during signing of HTTPS certificates and during decryption.” - [Euler’s theorem, Wikipedia](https://en.wikipedia.org/wiki/Euler%27s_theorem) — read raw: “This paper was first presented to the Berlin Academy on June 8, 1758 and to the St. Petersburg Academy on October 15, 1759.”; “Subsequently, Euler presented other proofs of the theorem, culminating with his paper of 1763, in which he proved a generalization to the case where n is not prime.”; the theorem “states that, if n and a are coprime positive integers, then a φ ( n ) is congruent to 1 modulo n” (exponent as typeset on the page); of that paper, in its reference list: “In this paper, Euler’s totient function, φ(n), is not named but referred to as “numerus partium ad N primarum.”” - [Floor and ceiling functions, Wikipedia](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions) — read raw: “Carl Friedrich Gauss introduced the square bracket notation [x] in his third proof of quadratic reciprocity (1808).”; “Kenneth E. Iverson introduced, in his 1962 book A Programming Language, the names “floor” and “ceiling” and the corresponding notations ⌊x⌋ and ⌈x⌉..” - [Euclidean algorithm, Wikipedia](https://en.wikipedia.org/wiki/Euclidean_algorithm) — read raw: “It is named after the ancient Greek mathematician Euclid, who first described it in his Elements (c. 300 BC)..” - [Factorial, Wikipedia](https://en.wikipedia.org/wiki/Factorial) — read raw: “The notation n! for factorials was introduced by the French mathematician Christian Kramp in 1808..” - [Petersen graph, Wikipedia](https://en.wikipedia.org/wiki/Petersen_graph) — read raw: “Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by A. B. Kempe (1886)..” - [Iverson bracket, Wikipedia](https://en.wikipedia.org/wiki/Iverson_bracket) — cites Iverson (1962), A Programming Language, p. 11: “The notation was originally introduced by Kenneth E. Iverson in his programming language APL,” “though restricted to single relational operators enclosed in parentheses,” the square brackets being “advocated by Donald Knuth.” - [Stirling’s approximation, Wikipedia](https://en.wikipedia.org/wiki/Stirling%27s_approximation) — dates the constant: “Stirling’s contribution in 1730 consisted of showing that the constant is precisely” √(2π); it also says “a related but less precise result was first stated by Abraham de Moivre.” The Factorial page above has “a 1729 letter from James Stirling to de Moivre stating what became known as Stirling’s approximation.” Editorial note: Added 18 September 2026 by the V42 citation sweep. citecheck.py found these years printed on a card or in a paragraph whose cited entries did not carry them; each was then verified against a source fetched raw that day, and the quotation in each source note is verbatim. ### 6.38 {#r-6.38} Dates and attributions printed on this chapter’s glossary cards and in its field notes, each checked against the source listed: Julius Petersen constructed the graph in 1898; Dirichlet used the pigeonhole principle in 1842, naming it the Schubfachprinzip only in later work; James Stirling introduced the numbers in Methodus Differentialis (1730); Jovan Karamata used the brace notation for Stirling numbers of the second kind in 1935, before Marx and Salmeri; The brace notation was used by Marx and Salmeri in 1962; Knuth adopted the brace notation in 1968; Ibn al-Haytham knew Wilson’s theorem around 1000; The Petersen graph is a ten-vertex graph from 1898. The year 1834 is often repeated, as on Wikipedia, but Rittaud and Heeffer (2014) find no source for it; Dirichlet’s first uses are in two papers of 1842, on diophantine approximation. *Status: confirmed* - [Petersen graph, Wikipedia](https://en.wikipedia.org/wiki/Petersen_graph) — read raw: “Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by A. B. Kempe (1886).”; “The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring..” - [Pigeonhole principle, Wikipedia](https://en.wikipedia.org/wiki/Pigeonhole_principle) — read raw: “it is commonly called Dirichlet’s box principle or Dirichlet’s drawer principle after an 1834 treatment of the principle by Peter Gustav Lejeune Dirichlet under the name Schubfachprinzip.” - [Stirling number, Wikipedia](https://en.wikipedia.org/wiki/Stirling_number) — read raw: “They are named after James Stirling, who introduced them in a purely algebraic setting in his book Methodus differentialis (1730)..” - [Stirling numbers of the second kind, Wikipedia](https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind) — read raw: “According to the third edition of The Art of Computer Programming, this notation was also used earlier by Jovan Karamata in 1935.”; “The brace notation was used by Imanuel Marx and Antonio Salmeri in 1962 for variants of these numbers.”; “This led Knuth to use it, as shown here, in the first volume of The Art of Computer Programming (1968)..” - [Wilson’s theorem, Wikipedia](https://en.wikipedia.org/wiki/Wilson%27s_theorem) — read raw: “The theorem was first stated by Ibn al-Haytham c. 1000 AD.”; “There is evidence that Leibniz was also aware of the result a century earlier, but never published it.”; its footnote on Waring: “In the third (1782) edition of Waring’s Meditationes Algebraicae, Wilson’s theorem appears as problem 5 on page 380. On that page, Waring states: “Hanc maxime elegantem primorum numerorum proprietatem invenit vir clarissimus, rerumque mathematicarum peritissimus Joannes Wilson Armiger.” (A man most illustrious and most skilled in mathematics, Squire John Wilson, found this most elegant property of prime numbers.)”; its elementary proof: “the only values of a for which a ≡ a⁻¹ (mod p) are a ≡ ±1 (mod p). Therefore, with the exception of ±1, the factors in the expanded form of (p − 1)! can be arranged in disjoint pairs such that product of each pair is congruent to 1 modulo p.” (formulas typeset on the page) - [Rittaud and Heeffer, The pigeonhole principle, two centuries before Dirichlet, Mathematical Intelligencer 36 (2014), Ghent repository copy](https://biblio.ugent.be/publication/4115264/file/4115265.pdf) — the historical study: “In the writings of Dirichlet, the application of the principle is to be found in 1842”; “It seems that no one knows any precise prior reference, even if the year 1834 is frequently mentioned as the year of the discovery”; “In [7] and [5], the pigeonhole principle is used to prove complex and multidimensional versions of Equation 1” (Dirichlet’s diophantine approximation); and “In a later work he calls it the “Schubfachprinzip.”” - [Ramsey’s theorem, Wikipedia](https://en.wikipedia.org/wiki/Ramsey%27s_theorem) — the proof of R(3, 3) = 6: “There are 5 edges incident to v and so (by the pigeonhole principle) at least 3 of them must be the same colour.” Editorial note: Added 18 September 2026 by the V42 citation sweep. citecheck.py found these years printed on a card or in a paragraph whose cited entries did not carry them; each was then verified against a source fetched raw that day, and the quotation in each source note is verbatim. ### 6.39 {#r-6.39} The Petersen graph is a ten-vertex, three-regular graph formed by connecting a pentagon to a pentagram; Julius Petersen constructed it in 1898 as the smallest bridgeless cubic graph with no three-edge-coloring, and it has served since as the standard counterexample to optimistic conjectures in graph theory. A. B. Kempe had already drawn the same graph in 1886. *Status: confirmed* - [Petersen graph, Wikipedia](https://en.wikipedia.org/wiki/Petersen_graph) — describes the construction, Petersen’s 1898 paper, and its role as a standard counterexample. ### 6.42 {#r-6.42} Ramanujan found in 1919 that the partition function satisfies p(5n+4) congruent to 0 mod 5, p(7n+5) congruent to 0 mod 7, and p(11n+6) congruent to 0 mod 11 for every n, congruences later extended by Ken Ono and others to further prime moduli. *Status: confirmed* - [Ramanujan’s congruences, Wikipedia](https://en.wikipedia.org/wiki/Ramanujan%27s_congruences) — states the three original congruences and later extensions. ### 6.45 {#r-6.45} States the binomial theorem, that (x+y)^n expands as the sum of C(n, k) x^k y^(n-k), and notes Newton’s 1665 generalization to non-integer exponents. Notes that the convention 0! = 1 makes C(n, 0) = C(n, n) = 1. *Status: confirmed* - [Binomial theorem, Wikipedia](https://en.wikipedia.org/wiki/Binomial_theorem) — states the expansion (x+y)^n = sum C(n, k) x^k y^(n-k) and Newton’s 1665 generalized binomial series. - [Factorial, Wikipedia](https://en.wikipedia.org/wiki/Factorial) — carries why 0! = 1 matters for binomial coefficients: “the number of ways to choose all n elements from a set of n is C(n, n) = n!/(n!0!) = 1, a binomial coefficient identity that would only be valid with 0!=1.”