gcd, linear combination problem

**Janu42** · September 14th 2010, 05:34 PM

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

**Chris11** · September 14th 2010, 06:23 PM

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

**melese** · September 15th 2010, 08:44 AM

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 $a$ and $b$ are integers - not both zero, and let $L=\left\{ax+by|x,y\in\mathbb{Z}\right\}$ be the set of all linear combinations of $a$ and $b$ .

The following relationship holds: Every linear combination of $a$ and $b$ (a member in $L$ ) is a multiple of $gcd(a,b)$ ; conversely, any multiple of $gcd(a,b)$ is a linear combination of $a$ and $b$ .
In short, $L$ is precisely the set of all multiples of $gcd(a,b)$ .

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

Thread: gcd, linear combination problem

LinkBack

Thread Tools

Display

gcd, linear combination problem

Similar Math Help Forum Discussions

Simple Linear Combination problem

linear combination

Linear Algebra - Linear Combination/Span

linear combination problem dealing with uniqueness

linear combination ?

Search Tags