PROOF 187

Prove.

There exist integers with gcd(a,b) = ax + by

On the integers ℤ.

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

c ∣ a means there is an integer m with a = cm.

Proof.

Divisors and multiples are written with this one line.convention

∎

Definition D2

gcd(a, b) is the greatest of the common divisors of a and b.

Proof.

(1)A common divisor is a c with c ∣ a and c ∣ b.D1

(2)Assume a and b are not both 0.assumption

∎

Definition D3

Let S = { ax + by : x, y ∈ ℤ, ax + by > 0 }.

Proof.

The set of all positive integer combinations of a and b.convention

∎

Lemma L1

S is not empty.

Proof.

(1)a and b are not both 0, so we may take a ≠ 0.D2

(2)Setting x = a, y = 0 gives ax + by = a·a + b·0 = a·a + 0 = a·a.A7, A8

(3)a·a > 0, so a·a ∈ S.(1), (2), A3, D3

∎

Lemma L2

S has a least element d. Write d = ax₀ + by₀.

Proof.

(1)S is a nonempty set of positive integers.D3, L1

(2)A least element d exists.(1), A1

(3)d ∈ S, so there are x₀, y₀ with d = ax₀ + by₀, and 0 < d.(2), D3

∎

Theorem T1

d divides a and divides b.

Proof.

(1)Divide a by d: a = qd + r, 0 ≤ r < d.A2, L2

(2)r = a − qd = a − q(ax₀ + by₀)(1), L2, E

(3)　 = a(1 − qx₀) + b(−qy₀) — r is also an integer combination of a and b.(2), A4, A5

(4)If 0 < r, then r ∈ S and r < d — contradicting the minimality of d.(1), (3), D3, L2

(5)Therefore r = 0 and a = qd + 0 = dq — that is, d ∣ a.(4), (1), A8, A5, D1

(6)Applying the same argument to b = q′d + r′ gives d ∣ b.A2, (5)

∎

Theorem T2

Every common divisor c of a and b divides d.

Proof.

(1)Suppose c ∣ a, c ∣ b: a = cm, b = cn.assumption, D1

(2)d = ax₀ + by₀ = (cm)x₀ + (cn)y₀L2, (1), E

(3)　 = c(mx₀ + ny₀)(2), A4, A5

(4)Therefore c ∣ d.(3), D1

∎

Corollary C

d = gcd(a, b). Therefore there exist integers x₀, y₀ with gcd(a, b) = ax₀ + by₀.

Proof.

(1)d is a common divisor of a and b.T1, D2

(2)For an arbitrary common divisor c, c ∣ d and 0 < d, so c ≤ d.T2, L2, A6

(3)The greatest of the common divisors is d — that is, d = gcd(a, b).(1), (2), D2

(4)d = ax₀ + by₀, so gcd(a, b) is an integer combination of a and b.(3), L2

∎

Remark

Can A1 be removed from this proof?

d was defined as 'the smallest positive combination'. Find where the guarantee that a smallest one exists comes from.