The greatest common divisor is the smallest positive linear combination

Question

How to prove the following theorems about gcd?

Theorem 1: Let $a$ and $b$ be nonzero integers. Then the smallest positive linear combination of $a$ and $b$ is a common divisor of $a$ and $b$.

Theorem 2: Let $a$ and $b$ be nonzero integers. The gcd of $a$ and $b$ is the smallest positive linear combination of $a$ and $b$.

Progress

For Theorem 1 I have assumed that $d$ is the smallest possible linear combination of $a$ and $d$. Then $a = dq + r$. Solved it and found a contradiction. Is my method correct? Don't know what to do for Theorem 2.

Answer 1

The procedure very briefly sketched in your comment is the standard way to prove Theorem 1.

For Theorem 2, the proof depends on exactly how the gcd of $a$ and $b$ is defined. Suppose it is defined in the naive way as the largest number which is a common divisor of $a$ and $b$.

We then need to show that there cannot be a larger common divisor of $a$ and $b$ than the smallest positive linear combination of these numbers.

Let $w$ be the smallest positive linear combination of $a$ and $b$, and let $d$ be their largest common divisor.

There exist integers $x$ and $y$ such that $w=ax+by$. Since $d$ divides $a$ and $b$, it follows that $d$ divides $ax+by$. So $d$ divides $w$, and therefore $d\le w$.

Your proof of Theorem 1 shows that $w$ is a positive common divisor of $a$ and $b$, so $w\le d$. It follows that $d=w$.

Remark: An alternate definition of the gcd is that it is a positive integer $d$ which is a common divisor of $a$ and $b$, and such that any common divisor of $a$ and $b$ divides $d$. Theorem 2 can also be proved in a straightforward way using that alternate (but equivalent) definition.

Answer 2

Theorem 1 is equivalent to asking: Is the remainder $r$ a linear combination of $a, b$?

If $d$ would not divide $a$, by division theorem: $a=dq+r, 0\lt r\lt d$. Furthermore, $a=dq+r\implies r=a-dq$, which means $r$ is a linear combination of $a$ and $b$, and it less than $d$, a contradiction that $d$ is the smallest. By the same idea we can prove $d$ divides $b$, so $d$ is a common divisor of $a$ and $b$.