- #1

- 370

- 0

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

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter ZioX
- Start date

- #1

- 370

- 0

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

- #2

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

- #3

- 370

- 0

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

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

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

- 370

- 0

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

- #6

shmoe

Science Advisor

Homework Helper

- 1,992

- 1

ZioX said: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.

Share:

- Replies
- 1

- Views
- 2K

- Replies
- 7

- Views
- 26K