Greatest Common Divisor is expressible as a linear combination of its arguments

See greatest common divisor

For any nonzero integers $a, b$ , there exist integers $s, t$ such that $gcd (a, b) = a s + b t$ .
Furthermore, $gcd (a, b)$ is the smallest possible integer of this form.

Proof

Let $S = {a m + b n : m, n \in Z and a m + b m > 0}$
nb $S \neq \emptyset$
By the well-ordering principle, $S$ has a least element $d = a s + b t$

Claim: $gcd (a, b) = d$

By Division Algorithm 1, $a = q d + r$ , with $0 \leq r < d$

Suppose $r > 0$ , then

\begin{aligned} r & = a - q d \\ = a - q (a s + b t) \\ = a (1 - q s) + b (- q t) \end{aligned}

Therefore $r \in S$ ,
but $d$ the least element of $S$ , so either $r \geq d$ or $r = 0$ ,
and by construction $r < d$ ,
so $r = 0$
so $d | a$

Similarly, $d | b$ .

Let $d^{'}$ another divisor of $a$ and $b$ .
Then $a = h d^{'}$ and $b = k d^{'}$ for some $h, k \in Z$

Therefore $d = (h d^{'}) s + (h d^{'}) t = d^{'} (h s + k t)$
So $d^{'} | d$
but $d^{'} \leq d$
so $d^{'} = d^{'}$

so $d = gcd (a, b)$

QED