The Smallest Positive Linear Combination Of a And b = gcd(a, b)

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:

\[{\color{purple}a} = q {\color{sandybrown}d} + {\color{red}r}\]

In other words:

$$ \displaylines{{\color{purple}a} = q({\color{orange}m}{\color{purple}a} + {\color{orange}n}{\color{purple}b}) + {\color{red}r} \\ {\color{red}r} = (1 - q{\color{orange}m}){\color{purple}a} - (q{\color{orange}n}){\color{purple}b} }$$

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).