Proving the Relationship between GCD and Linear Combinations

[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?

 

[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?

 

[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?

 

[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?

 

[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?

 

[shmoe]

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

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.