For integers a and b, what is the relationship between gcd(a,b) and the set of integer linear combinations of a and b?

Printable View

- September 14th 2010, 05:34 PMJanu42gcd, linear combination problem
For integers a and b, what is the relationship between gcd(a,b) and the set of integer linear combinations of a and b?

- September 14th 2010, 06:23 PMChris11
gcd(a,b) divides all linear combos of a and b.

- September 15th 2010, 08:44 AMmelese
Suppose and are integers - not both zero, and let be the set of all linear combinations of and .

The following relationship holds: Every linear combination of and (a member in ) is a multiple of ; conversely, any multiple of is a linear combination of and .

In short, is precisely the set of all multiples of .

BTW, the greatest common divisor of and is the smallest postive linear combination of and .