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

- Sep 14th 2010, 04: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?

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

- Sep 15th 2010, 07:44 AMmelese
Suppose $\displaystyle a $ and $\displaystyle b $ are integers - not both zero, and let $\displaystyle L=\left\{ax+by|x,y\in\mathbb{Z}\right\}$ be the set of all linear combinations of $\displaystyle a $ and $\displaystyle b $.

The following relationship holds: Every linear combination of $\displaystyle a $ and $\displaystyle b $ (a member in $\displaystyle L $) is a multiple of $\displaystyle gcd(a,b) $; conversely, any multiple of $\displaystyle gcd(a,b)$ is a linear combination of $\displaystyle a $ and $\displaystyle b $.

In short, $\displaystyle L $ is precisely the set of all multiples of $\displaystyle gcd(a,b) $.

BTW, the greatest common divisor of $\displaystyle a $ and $\displaystyle b $ is the smallest postive linear combination of $\displaystyle a $ and $\displaystyle b $.