Definition D1
d | a means that a natural number k exists satisfying a = dk.
Proof.
Then d is called a divisor of a, and a a multiple of d.convention
∎
Definition D2
gcd(a, b) is the greatest among the common divisors of a and b.
Proof.
If two pairs have the same set of common divisors, their greatest common divisors coincide.convention
∎
Definition D3
Set r₀ = a, r₁ = b, and while rₖ > 0 determine the next term by rₖ₋₁ = rₖqₖ + rₖ₊₁, 0 ≤ rₖ₊₁ < rₖ.
Proof.
(1)At each step, qₖ and rₖ₊₁ are uniquely determined by A1.A1
(2)Stop when rₖ = 0.convention
∎
Lemma L1
If d | x, then for all q, d | xq
Proof.
(1)There is an 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 gcd(a, b) = gcd(b, r)
Proof.
(1)Let d be a common divisor of b and r.assumption
(2)d | bq(1), L1
(3)d | bq + r, that is, d | a(1), (2), A6, assumption
(4)Now let d be a common divisor of a and b.assumption
(5)d | bq(4), L1
(6)Since a = bq + r and d | a, d | r(4), (5), A7
(7)The two pairs have the same set of common divisors.(3), (6)
(8)Therefore their greatest common divisors coincide.(7), D2
∎
Theorem T
The algorithm reaches rₖ = 0 after finitely many steps.
Proof.
(1)At each step, 0 ≤ rₖ₊₁ < rₖ.D3, A1
(2)Suppose the algorithm never terminates.assumption
(3)Then for all k, rₖ > 0 and rₖ₊₁ < rₖ.(1), (2)
(4)S = { r₁, r₂, r₃, … } is a nonempty subset of ℕ.(3)
(5)S has a least element rₘ.A2, (4)
(6)Since rₘ > 0, rₘ₊₁ is determined and rₘ₊₁ < rₘ.(3), (5), D3
(7)rₘ₊₁ is an element of S.(4), (6)
(8)This contradicts rₘ being the least element of S.(5), (6), (7)
(9)Therefore the algorithm terminates in finitely many steps.(8)
∎
Corollary C
If the algorithm halts at rₙ₊₁ = 0, then gcd(a, b) = rₙ.
Proof.
(1)gcd(r₀, r₁) = gcd(r₁, r₂) = … = gcd(rₙ₋₁, rₙ)L2, D3
(2)rₙ₋₁ = rₙqₙ + 0 = rₙqₙassumption, D3, A3
(3)Therefore rₙ | rₙ₋₁(2), D1
(4)Since rₙ = rₙ × 1, rₙ | rₙA4, D1
(5)rₙ is a common divisor of rₙ₋₁ and rₙ.(3), (4)
(6)Since rₙ > 0, any common divisor d satisfies d | rₙ and d ≤ rₙD3, A8
(7)gcd(rₙ₋₁, rₙ) = rₙ(5), (6), D2
(8)Therefore gcd(a, b) = rₙ(1), (7)
∎