# Thread: gcd, linear combination problem

1. ## gcd, 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?

2. gcd(a,b) divides all linear combos of a and b.

3. Originally Posted by Janu42
For integers a and b, what is the relationship between gcd(a,b) and the set of integer linear combinations of a and b?
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$.