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

Let d be the smallest positive linear combination (a m + b n). 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:

$$ \textcolor{purple}{a} = q(\textcolor{orange}{m}\textcolor{purple}{a} + \textcolor{orange}{n}\textcolor{purple}{b}) + \textcolor{red}{r} $$$$ \textcolor{red}{r} = (1 - q\textcolor{orange}{m}) \textcolor{purple}{a} - (q\textcolor{orange}{n}) \textcolor{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)|(a x + b y)], where x and y can be any integers. That means gcd(a, b)| d, which also means d \geq 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 \leq gcd(a, b).

Since d \leq gcd(a, b) and d \geq gcd(a, b), then d = gcd(a, b).