Let d be the smallest positive linear combination (am + bn). Our goal is to prove that d = gcd(a, b).
Since d is the smallest positive linear combination, then d|a and d|b. Proof? Well, let's first assume d∤a, then there exists a remainder r more than 0 and smaller than d where:
In other words:
Therefore r is a linear combination. However, we stated that d is the smallest linear combination, and we also stated that r is smaller than d; this is a contradiction. Therefore, no such r exists. This shows that d|a and by using a similar proof we can show that d|b.
Since [gcd(a, b)|a] and [gcd(a, b)|b], then [gcd(a, b)|(ax + by)], where x and y can be any integers. That means gcd(a, b)|d, which also means d ≥ gcd(a, b).
Since d|a and d|b, then d is a common divisor. Since gcd(a, b) is the greatest common divisor, then d ≤ gcd(a, b).
Since d ≤ gcd(a, b) and d ≥ gcd(a, b), then d = gcd(a, b).