gcd(a,b) is the smallest positive linear combination of a and b
The greatest common divisor of a and b is the smallest positive linear combination of a and b with integer coefficients.
Fix a,b∈N≥2. Let L be the set {ax+by:x,y∈Z, ax+by>0} of positive linear combinations of a and b. Then minL=gcd(a,b).
First note that since a,b=0 then L is nonempty, which by the well-ordering principle implies that minL exists.
Let d denote minL. Since d∈L we know ∃x0,y0:ax0+by0=d.
We want to show that d=gcd(a,b). We will do this by showing that (1) d∣a; that (2) d∣b; and that (3) any e dividing both a and b also divides d.
1. Assume for contradiction that d∤a. Then we can write a=dq+r for some q and some 0<r<d. Thus r=a−dq=a−q(ax0+by0)=a(1−qx0)+b(−qy0)∈L. Since r<d and r∈L, then d=minL, which is a contradiction. Conclude that d∣a.
2. d∣b by analogous reasoning
3. Take e such that e∣a and e∣b. Since e∣a then exists k where e=ka. Thus e=a⋅k+b⋅0, and so e∈L. Since d=minL, then e≤d.