# Is greatest common divisor of two numbers really their smallest linear combination?

In a lecture note from MIT on number theory says:

Theorem 5. The greatest common divisor of a and b is equal to the smallest positive linear combination of a and b.

For example, the greatest common divisor of 52 and 44 is 4. And, sure enough, 4 is a linear combination of 52 and 44:
6 · 52 + (−7) 44 = 4

What about 12 and 6 their gcd is 6 but 0 which is less than 6 can be

-
You wrote it yourself: the gcd is the smallest positive linear combination. –  André Nicolas Oct 24 '12 at 7:32
Note that $52 \times 44 - 44 \times 52 =0$ and you can do this with any pair of integers. –  Mark Bennet Oct 24 '12 at 7:43
@MarkBennet yeah that's right. –  spartacus Oct 24 '12 at 20:40

You wrote it yourself: the gcd is the smallest positive linear combination. Smallest positive linear combination is shorthand for smallest positive number which is a linear combination. It is true that $0$ is a linear combination of $12$ and $6$ with integer coefficients, but $0$ is not positive.

The proof is not difficult, but it is somewhat lengthy. We give full detail below.

Let $e$ be the smallest positive linear combination $as+bt$ of $a$ and $b$, where $s$ and $t$ are integers. Suppose in particular that $e=ax+by$.

Let $d=\gcd(a,b)$. Then $d$ divides $a$ and $b$, so it divides $ax+by$. Thus $d$ divides $e$, and therefore in particular $d\le e$.

We show that in fact $e$ is a common divisor of $a$ and $b$. This means that $e$ is a common divisor of $a$ and $b$, which implies that $e\le d$. That, together with our earlier $d\le e$, will imply that $d=e$.

So it remains to show that $e$ divides $a$ and $e$ divides $b$. We show that $e$ divides $a$. The proof that $e$ divides $b$ is essentially the same.

Suppose to the contrary that $e$ does not divide $a$. Then when we try to divide $a$ by $e$, we get a positive remainder. More precisely, $$a=qe+r,$$ where $0\lt r\lt e$. Then $$r=a-qe=a-q(ax+by)=a(1-qx)+b(-qy).$$ This means that $r$ is a linear combination of $a$ and $b$, and is positive and less than $e$. This contradicts the fact that $e$ is the smallest positive linear combination of $a$ and $b$.

-