Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
You wrote it yourself: the gcd is the smallest positive linear combination. –  André Nicolas Oct 24 '12 at 7:32
3  
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

1 Answer 1

up vote 11 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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