16
$\begingroup$

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

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

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$, which will imply 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.