# The greatest common divisor is the smallest positive linear combination

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.

• Does theorem 2 imply theorem 1, since the gcd of two numbers is also their common divisor. Or am I missing something. Hence it is sufficient to prove theorem 2.
– john
Sep 1, 2020 at 17:15

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.

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