# GCD and linear combinations

1. Sep 12, 2006

### ZioX

I remember this from awhile back but can't seem to find any justification.

Why is the smallest positive linear combination of two numbers necessarily the GCD of the two numbers?

2. Sep 12, 2006

### shmoe

You can use the Euclidean algorithm to find the gcd, then work backwards to write this gcd as a linear combination. Have you seen the Euclidean algorithm?

3. Sep 12, 2006

### ZioX

Yes, I am well aware of it. Perhaps not well enough to immediately see how that applies here.

But knowing that you have two numbers, a and b, and you know there exists s and t such that as+bt=1 how do you know that have gcd of one? Knowing that they have a gcd of one guarantees there exists an s and a t, but what if we're given s and t?

Again, my original question, and more generally, why is the smallest positive linear combination of two numbers necessarily the greatest common divisor?

4. Sep 12, 2006

### shmoe

The Euclidean algorithm repeatedly uses the division algorithm until the gcd pops out. Example, to find the gcd of 12 and 93:

93=12*7+9
12=9*1+3
9=3*3+0

This tells you that gcd(93,12)=3. We can work backwards to write 3 as a linear combination of 93 and 12:

3=12-9*1

from the second line. The first line says 9=93-12*7, sub this in for 9:

3=12-(93-12*7)*1=12*8-93*1

and we have 3 as a linear combination of 12 and 93.

This works in general, and you can prove this way that given a,b you can always find s and t so that a*s+b*t=gcd(a,b).

Proving that any other linear combination (that is positive) will be larger will follow from properties of the gcd. It divides both a and b, so what about a linear combination? Maybe look at the gcd=1 case first, if as+bt=1, what if d divides both a and b?

5. Sep 12, 2006

### ZioX

I'm still having problems and very confused. I don't want to go in that direction with the euclidean algorithm.

Essentially what my problem boils down to is, we know that as+bt=1. Why is gcd(a,b)=1?

6. Sep 12, 2006

### shmoe

In this case you know that gcd(a,b) divides a, and it divides b, so it divides any linear combination of a and b, so it must be 1.

This doesn't prove that if gcd(a,b)=1 then you can actually write 1 as a linear combination of a and b though. That's what the euclidean algortihm will let you do. But you can go another way if you like, assume you have the smallest positive linear combination as+bt=r. If r doesn't divide a and b, show you can find a smaller linear combination, which is a contradiction.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook