Divisibility and Congruences

Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Chapter 2 built $\mathbb{Z}$ out of pairs of natural numbers and proved it an ordered ring, but it said nothing about which integers divide which. Sets and Functions, Section 3.2 did, for the school integers: it proved division with remainder, showed that every integer from $2$ on has a prime factor, and set the uniqueness of prime factorization aside as a fact it neither proved nor used. This chapter proves that arithmetic again for the constructed $\mathbb{Z}$ , and goes further, using the ordered-ring axioms and two properties of the order of $\mathbb{Z}$ : there is no integer strictly between $0$ and $1$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.4.2 (c)), and a non-empty set of integers with a lower bound has a least element (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.4). Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Section 2.5 drew division with remainder from the second property (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.5.2), and this chapter starts there; the field $\mathbb{Q}$ enters for lowest terms and in a few examples and exercises. Then one move does most of the work. In a set of integers closed under sums and under multiplication by any integer, the least positive element divides every element, and dividing by it with remainder is how one sees this. Applied to the combinations $ax + by$ , it makes the greatest common divisor a combination of $a$ and $b$ (Bézout’s theorem), and the Euclidean algorithm computes it. Multiplying that combination by a third integer gives Euclid’s lemma, that a prime dividing a product divides one of the factors, and with it the uniqueness of prime factorization and the lowest terms of a rational number.

The second half returns to the clock of Sets and Functions, Section 5.2. There, and again for $\mathbb{Z}$ and $\mathbb{Q}$ in Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Chapters 2 and 3, each sum and product of classes was checked separately to be well defined. Section 2.3 makes the check once, for the quotient of any commutative ring by an ideal, and $\mathbb{Z}/n\mathbb{Z}$ becomes a commutative ring with $n$ elements on which, for $n \ge 2$ , no order fits. In it the classes that can be divided by are exactly the classes of the integers coprime to $n$ . So $\mathbb{Z}/p\mathbb{Z}$ is a field with $p$ elements for every prime $p$ , and two congruences with coprime moduli have exactly one class of solutions modulo the product of the moduli, the Chinese remainder theorem. Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Chapter 5 builds $\mathbb{R}$ in the same shape, as classes of rational Cauchy sequences whose difference is null (the null sequences play the part of the ideal), though it checks its operations directly; Chapter 7 of this volume runs division with remainder, gcd and unique factorization again for polynomials over a field.

Two integers, one theory. Sets and Functions, Chapters 1, 3 and 5 proved its facts about divisibility for the school integers, from school facts such as the closure of $\mathbb{Z}$ under $+$ , $-$ and $\cdot$ (Sets and Functions, Proposition 3.1.2). This chapter keeps their definitions of divisibility, prime and congruence (Sets and Functions, Definition 1.1.2, Sets and Functions, Definition 1.1.3, Sets and Functions, Definition 5.2.5), read word for word on the ring of Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Chapter 2, and proves the results again; no proof in it cites a result of Sets and Functions about integers. Each such result has a twin here: transitivity of divisibility (Sets and Functions, Proposition 1.1.1) and even or odd (Sets and Functions, Theorem 1.1.2), from its Chapter 1, are Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (b) and Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Corollary 2.5.3 (a); the others are named in the section that proves them: division with remainder (Sets and Functions, Theorem 3.2.3) and the antisymmetry of divisibility on $\mathbb{N}$ (Sets and Functions, Proposition 5.1.1) in Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Section 2.5; a prime factor of every $n \ge 2$ (Sets and Functions, Theorem 3.2.5) and lowest terms (Sets and Functions, Lemma 3.2.4) in Section 2.2; and the arithmetic of congruence classes (Sets and Functions, Proposition 5.2.5) in Section 2.3. Nothing earlier was circular: the earlier chapters used these facts about the school integers as stated facts, and this chapter proves them for the constructed ones.

Time. About 20 hours on the core track (all of A, one B and one C per section, the exit checks); about 30 hours for everything.

Roadmap

The Greatest Common Divisor, Bézout, and the Euclidean Algorithm. The combinations $a\mathbb{Z} + b\mathbb{Z}$ and the multiples $n\mathbb{Z}$ , the greatest common divisor with $\gcd(0, 0) \mathrel{:=} 0$ , Bézout’s theorem (the least positive combination is the gcd, and every combination is a multiple of it), coprime integers, and the Euclidean algorithm as a recursion that keeps the set of combinations fixed, with back-substitution for the coefficients.
Euclid’s Lemma and the Fundamental Theorem of Arithmetic. Euclid’s lemma from the Bézout identity, a prime dividing a product of primes equal to one of them, coprime divisors, the least divisor above $1$ as a prime, existence and uniqueness of non-decreasing prime factorizations by comparing the largest primes, a monoid in which factorization is not unique, and lowest terms in $\mathbb{Q}$ .
Ideals, Quotient Rings, and the Integers Modulo n. Ideals as the subsets that a quotient needs, the quotient ring $R/I$ of a commutative ring by an ideal, the failure for $\mathbb{Z} \subseteq \mathbb{Q}$ , the ideals of $\mathbb{Z}$ as the sets $n\mathbb{Z}$ , and $\mathbb{Z}/n\mathbb{Z}$ as a commutative ring with $n$ elements that no order fits when $n \ge 2$ .
Units, Prime Moduli, and the Chinese Remainder Theorem. Units of a commutative ring, the units of $\mathbb{Z}/n\mathbb{Z}$ as the classes coprime to $n$ with inverses from back-substitution, $\mathbb{Z}/n\mathbb{Z}$ a field exactly when $n$ is prime, and the Chinese remainder theorem for two coprime moduli, with the failures when the moduli share a factor; the review exercises reach back to Chapter 1 of this volume, Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Chapters 1 and 3, Logic and Proof, Chapter 2, and Sets and Functions, Chapter 4.

Named moves

Least positive element, then divide. Take the least positive element $d$ of a set of integers closed under integer combinations; divide any element of the set by $d$ ; the remainder lies in the set and is smaller than $d$ , so it is $0$ . This proves Bézout’s theorem in Section 2.1 and the description of the ideals of $\mathbb{Z}$ in Section 2.3, and Section 2.2’s B2 and Section 2.3’s C2 use it for common multiples and for sets closed under subtraction.
Multiply the Bézout identity. From $1 = ax + by$ , multiply by $c$ : $c = acx + bcy$ , and read off what divides $c$ . It turns a statement about common divisors into an equation, and it gives Euclid’s lemma in Section 2.2; in Section 2.4 the same identity, read modulo $n$ , gives inverses, and read modulo $m$ and modulo $n$ at once, the Chinese remainder theorem.
Compute on representatives; the ideal absorbs the change. An operation on classes $a + I$ is well defined because a change of representative is an element of $I$ , and multiplying it by the other argument keeps it in $I$ . This is Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Chapter 2’s check one argument at a time, now made once for every commutative ring and every ideal.