PROOF 83

Prove.

The last remainder of the Euclidean algorithm is the gcd

On the natural numbers ℕ.

A way to read this proof

First separate what is assumed from what is to be proved. At each step, ask which definition or earlier result permits the move. If it is unclear, return to that premise rather than skipping to the conclusion.

Definition D1

d | a means there exists a natural number k with a = dk.

Proof.

In that case d is called a divisor of a.convention

∎

Definition D2

C(a, b) is the set of all common divisors of a and b, and gcd(a, b) is the maximum of C(a, b).

Proof.

If two pairs have the same set of common divisors, they have the same maximum.convention

∎

Definition D3

Set r₀ = a, r₁ = b, and while rₖ > 0 define the next term by rₖ₋₁ = rₖqₖ + rₖ₊₁, 0 ≤ rₖ₊₁ < rₖ.

Proof.

(1)At each step, A1 determines qₖ and rₖ₊₁ uniquely.A1

(2)Stop when rₖ = 0.convention

∎

Lemma L1

If d | x, then for every q, d | xq

Proof.

(1)There is m with x = dm.assumption, D1

(2)xq = (dm)q(1), E

(3)　 = d(mq)A5

(4)Therefore d | xq(3), D1

∎

Lemma L2

If a = bq + r, then C(a, b) = C(b, r) and gcd(a, b) = gcd(b, r)

Proof.

(1)First let d ∈ C(b, r).assumption, D2

(2)d | b, so d | bq(1), L1

(3)d | r, so d | bq + r, that is, d | a(1), (2), A2, assumption

(4)Therefore C(b, r) ⊆ C(a, b)(1), (3), D2

(5)Now let d ∈ C(a, b).assumption, D2

(6)d | b, so d | bq(5), L1

(7)a = bq + r and d | a, so d | r(5), (6), A3, assumption

(8)Therefore C(a, b) ⊆ C(b, r)(5), (7), D2

(9)Each contains the other, so the two sets are equal.(4), (8)

(10)Equal sets have the same maximum.(9), D2

∎

Lemma L3

For every k at which rₖ is defined, gcd(a, b) = gcd(rₖ, rₖ₊₁)

Proof.

(1)Let P(k) be gcd(a, b) = gcd(rₖ, rₖ₊₁).convention

(2)r₀ = a and r₁ = b, so P(0) holds.(1), D3

(3)Suppose P(k) holds and rₖ₊₁ > 0.assumption

(4)There are qₖ₊₁ and rₖ₊₂ with rₖ = rₖ₊₁qₖ₊₁ + rₖ₊₂.(3), D3, A1

(5)gcd(rₖ, rₖ₊₁) = gcd(rₖ₊₁, rₖ₊₂)(4), L2

(6)Therefore P(k+1) holds.(3), (5)

(7)By induction, P(k) holds for every k.(2), (6), A8

∎

Theorem T

If the algorithm stops at rₙ > 0, rₙ₊₁ = 0, then gcd(a, b) = rₙ.

Proof.

(1)rₙ₋₁ = rₙqₙ + 0 = rₙqₙassumption, D3, A7

(2)Therefore rₙ | rₙ₋₁(1), D1

(3)rₙ = rₙ × 1, so rₙ | rₙA6, D1

(4)rₙ ∈ C(rₙ₋₁, rₙ)(2), (3), D2

(5)If d ∈ C(rₙ₋₁, rₙ), then d | rₙ and rₙ > 0, so d ≤ rₙassumption, D2, A4

(6)Therefore gcd(rₙ₋₁, rₙ) = rₙ(4), (5), D2

(7)gcd(a, b) = gcd(rₙ₋₁, rₙ)L3

(8)Therefore gcd(a, b) = rₙ(6), (7)

∎

Remark

Can A1 be removed from this proof?

L2 is a conditional statement. Identify what supplies its condition.