Proving that $ \gcd(a,b) = as + bt $, i.e., $ \gcd $ is a linear combination. [duplicate]

For any nonzero integers $ a $ and $ b $, there exist integers $ s $ and $ t $ such that $ \gcd(a,b) = as + bt $. Moreover, $ \gcd(a,b) $ is the smallest positive integer of the form $ as + bt $.

I know of one proof of this question, in which we consider $$ S = \{ am + bn ~|~ \text{$ m,n \in \mathbb{Z} $ and $ am + bn > 0 $} \}, $$ but I didn’t manage to get the proof. Can someone please explain this theorem?

Solution 1:

Take the set $$S=\{ax+by>0:x,y\in \Bbb Z\}$$

Without loss of generality, assume that $a<b$. Then $b-a>0$ is in $S$, so $S$ is a nonempty set of positive natural numbers. By the well ordering principle, there exists a least element $d\in S$, which we know is of the form $ax'+by'$. By the division algorithm, there exists $q,r$ with $0\leq r <ax'+by'$ such that $$a=qd+r$$

But then $a-qd=r$ is a nonnegative number of the form $ax+by$ yet smaller than $d$, so it must forcefully be zero. This means that the remainder when $d$ divides $a$ is $0$; which means $d\mid a$. By a completely analogous argument, it follows that $d\mid b$. So $d$ is a common divisor of $a$ and $b$. But if $c$ is any common divisor of $a$ and $b$, it must divide $ax'+by'=d$. By the definition of the $\gcd$, we just proved that $\gcd(a,b)=d$. $\blacktriangle$

Solution 2:

This is known as Bezout's Identity and you can study section 4 of this http://math.bard.edu/belk/math332s09/NumberTheory.pdf

Solution 3:

I'm not too quick, so I usually find it useful to look at concrete examples (say, $\gcd (83, 56) =1$) before considering the general one.

If you can show why this process (in general) terminates, I think you would be done.

$83 = 1 \times 56 + (83-56)$

$56 = 2 \times (83-56) + (56 - 2 \times (83-56))$

$83-56 = 13 \times (56 - 2 \times (83-56)) + (83-56-(13 \times (56 - 2 \times (83-56))))$

and that last remainder, $1=\gcd(83,56)$.

$1=(83-56-(13 \times (56 - 2 \times (83-56))))$

$1=83-56-(13 \times (-2 \times 83 + 3 \times 56)$

$1 = 83-56 + 26 \times 83 - 39 \times 56$

$1 = 27 \times 83 - 40 \times 56$

And you have your coefficients.