Dividing

What it means for one number to divide another, why division with remainder always works and is unique, and how the Euclidean algorithm finds the greatest common divisor, pictured as a rectangle from which squares are cut.

Almost everything on this website turns on dividing: whether the figure $\{n/k\}$ falls into several parts, whether a number is prime, where the twin places lie. This chapter lays the foundation. It follows the seventh book of Euclid’s Elements, which around 300 BC summed up the number theory of the Greeks.

Divisors

Definition

For $d, n \in \mathbb{N}_0$ , $d$ is called a divisor of $n$ , written $d \mid n$ , if there is a $q \in \mathbb{N}_0$ with $n = d \cdot q$ .

So $4 \mid 12$ , because $12 = 4 \cdot 3$ , but $4 \nmid 10$ . Every number is divided by 1 and by itself, and every number divides zero.

Theorem 1

For all $a, b, d \in \mathbb{N}_0$ :

From $d \mid a$ and $a \mid b$ it follows that $d \mid b$ .
From $d \mid a$ and $d \mid b$ it follows that $d \mid a + b$ , and for $a \ge b$ also $d \mid a - b$ .
From $d \mid n$ and $n > 0$ it follows that $d \le n$ .

Proof

If $a = dq$ and $b = aq'$ , then $b = d(qq')$ .
If $a = dq$ and $b = dq'$ , then $a \pm b = d(q \pm q')$ .
If $n = dq$ with $n > 0$ , then $q \ge 1$ , so $n = dq \ge d$ .

∎

Division with remainder

If a division does not come out evenly, a remainder is left. That this always works in exactly one way is the first truly important theorem of number theory.

Theorem 2

For $a \in \mathbb{N}_0$ and $b \in \mathbb{N}$ there is exactly one pair $q, r \in \mathbb{N}_0$ with

a = b \cdot q + r \quad \text{and} \quad 0 \le r < b.

$q$ is called the quotient and $r = a \bmod b$ the remainder.

Proof

Existence. The multiples $0, b, 2b, 3b, \dots$ grow beyond every bound. Let $q$ be the largest $q$ with $bq \le a$ and $r := a - bq \ge 0$ . If $r \ge b$ , then $b(q+1) \le a$ , against the choice of $q$ . So $r < b$ .

Uniqueness. Let also $a = bq' + r'$ with $0 \le r' < b$ , and without loss of generality $q \ge q'$ . Then $b(q - q') = r' - r$ . The right side is smaller than $b$ , the left a multiple of $b$ , so both are 0. Hence $q = q'$ and $r = r'$ .

∎

Division with remainder is nothing but counting on a clock with $b$ hours. Chapter 5 builds on it, and it is also the core of the figures $\{n/k\}$ : whoever keeps moving $k$ on along $n$ points is calculating with the remainder on division by $n$ .

The greatest common divisor

Definition

For $a, b \in \mathbb{N}_0$ , not both 0, $\gcd(a, b)$ is the largest number that divides $a$ and $b$ .

One could write down all divisors of both numbers and pick the largest common one. Euclid hands down a much faster way, which is probably older still.

Theorem 3

For $a \in \mathbb{N}_0$ and $b \in \mathbb{N}$ , the pairs $a, b$ and $b, a \bmod b$ have the same common divisors. In particular

\gcd(a, b) = \gcd(b,\, a \bmod b).

Proof

Let $a = bq + r$ with $r = a \bmod b$ . If $d$ divides $a$ and $b$ , it divides $bq$ and by Theorem 1 also $r = a - bq$ . Conversely, if $d$ divides $b$ and $r$ , it divides $a = bq + r$ . So the two pairs have the same common divisors and hence the same greatest one.

∎

Applying Theorem 3 again and again, the numbers get smaller at every step, since the remainder is smaller than the divisor. At some point the remainder is 0, and then $\gcd(b, 0) = b$ . This is the Euclidean algorithm, the oldest non-trivial procedure of calculation still in use today. For 21 and 13:

\begin{aligned} 21 &= 1 \cdot 13 + 8 \\ 13 &= 1 \cdot 8 + 5 \\ 8 &= 1 \cdot 5 + 3 \\ 5 &= 1 \cdot 3 + 2 \\ 3 &= 1 \cdot 2 + 1 \\ 2 &= 2 \cdot 1 + 0 \end{aligned}

The last divisor, at which the remainder becomes 0, is the gcd: $\gcd(21, 13) = 1$ . The two numbers are coprime.

The Greeks thought of line segments. From a rectangle with sides $a$ and $b$ you cut as many squares as possible, from the rest again, and so on. The side of the last square that fits exactly is the common measure of both sides, the gcd. The procedure is called anthyphairesis, “mutual taking away”, and Euclid describes it in the Elements VII 1 and 2, with line segments, the picture with the rectangle is a modern illustration.

a b

Squares are cut from the rectangle a × b, each colour one step of the algorithm. The smallest square measures both sides exactly, its side is the gcd. The buttons 1 : √2 and 1 : φ show what happens when there is no common measure (see Chapter 9).

The gcd as a sum

One last theorem about the gcd becomes indispensable in the next chapter. For it we also need negative numbers, the integers $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$ .

Theorem 4

For $a, b \in \mathbb{N}$ there are integers $x, y \in \mathbb{Z}$ with

\gcd(a, b) = a x + b y.

Proof

Let $d$ be the smallest positive number of the form $ax + by$ with $x, y \in \mathbb{Z}$ . Such numbers exist, for example $a = a \cdot 1 + b \cdot 0$ . Dividing $a$ by $d$ with remainder, $a = qd + r$ with $0 \le r < d$ , gives

\begin{aligned} r &= a - q(ax + by) \\ &= a(1 - qx) + b(-qy) \end{aligned}

again of this form. Since $d$ is the smallest positive such number, $r = 0$ , so $d \mid a$ . Likewise $d \mid b$ . Every common divisor of $a$ and $b$ divides $ax + by = d$ and by Theorem 1 is at most $d$ . Hence $d = \gcd(a, b)$ .

∎

For 10 and 4, for example, $\gcd(10, 4) = 2 = 10 \cdot 1 + 4 \cdot (-2)$ . The theorem bears the name of Étienne Bézout, who proved it for polynomials in 1779. For integers Claude-Gaspard Bachet already knew it in 1624.

Checked by computer: the proof in Lean

division_with_remainder is the existence part of Theorem 2, remainder_unique the uniqueness. In Lean a / b is the quotient and a % b the remainder. common_divisors is Theorem 3 in the form “same common divisors”, and the last line makes Lean run the Euclidean algorithm for 10 and 4. Theorem 4 is already proven in Lean’s library and is used in Chapter 4.

/-! Chapter 3: division with remainder and the greatest common divisor -/

/-- Theorem 2: Division with remainder. For a and b > 0 there are
    q and r < b with a = b · q + r. -/
theorem division_with_remainder (a b : Nat) (hb : 0 < b) :
    a = b * (a / b) + a % b ∧ a % b < b :=
  ⟨(Nat.div_add_mod a b).symm, Nat.mod_lt a hb⟩

/-- … and q and r are uniquely determined. -/
theorem remainder_unique (b q r q' r' : Nat)
    (hr : r < b) (hr' : r' < b) (h : b * q + r = b * q' + r') :
    q = q' ∧ r = r' := by
  have h1 : (b * q + r) / b = q := by
    rw [Nat.add_comm, Nat.add_mul_div_left _ _ (by omega)]
    simp [Nat.div_eq_of_lt hr]
  have h2 : (b * q' + r') / b = q' := by
    rw [Nat.add_comm, Nat.add_mul_div_left _ _ (by omega)]
    simp [Nat.div_eq_of_lt hr']
  have hq : q = q' := by rw [← h1, ← h2, h]
  subst hq
  exact ⟨rfl, by omega⟩

/-- Theorem 3: The common divisors of a and b are exactly
    those of b and a mod b. -/
theorem common_divisors (a b d : Nat) :
    (d ∣ a ∧ d ∣ b) ↔ (d ∣ b ∧ d ∣ a % b) := by
  constructor
  · intro ⟨ha, hb⟩
    exact ⟨hb, (Nat.dvd_mod_iff hb).mpr ha⟩
  · intro ⟨hb, hr⟩
    exact ⟨(Nat.dvd_mod_iff hb).mp hr, hb⟩

-- The Euclidean algorithm for 10 and 4:
-- gcd(10, 4) = gcd(4, 2) = gcd(2, 0) = 2
example : Nat.gcd 10 4 = 2 := by decide

Try it in the browser at live.lean-lang.org ↗How to read Lean

Where this appears on the website

The gcd decides the shape of every figure $\{n/k\}$ (Chapter 6, Numbers as figures). The three relations between a number and a divisor that The key to the tetractys describes are exactly the three cases $\gcd(n,k) = k$ , $\gcd(n,k) = 1$ and $1 < \gcd(n,k) < k$ . And the division table colours its fields by these cases (see Simplexes and primes in the division table).

Sources and further reading

Sources

Euclid, Elements, around 300 BC, book VII, 1 and 2
Claude-Gaspard Bachet de Méziriac, Problèmes plaisans et délectables, 2nd ed. Lyon 1624
Étienne Bézout, Théorie générale des équations algébriques, Paris 1779

Dividing

Divisors

Division with remainder

The greatest common divisor

The gcd as a sum

Where this appears on the website

Sources

Further reading