Results 1 to 3 of 3

Thread: gcd, linear combination problem

  1. #1
    Member
    Joined
    Nov 2008
    Posts
    152

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    gcd(a,b) divides all linear combos of a and b.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2010
    From
    Israel
    Posts
    148
    Quote Originally Posted by Janu42 View Post
    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 $.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simple Linear Combination problem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Nov 16th 2011, 01:55 AM
  2. linear combination
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Jan 6th 2011, 03:27 PM
  3. Linear Algebra - Linear Combination/Span
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Sep 13th 2008, 06:06 PM
  4. linear combination problem dealing with uniqueness
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Feb 10th 2008, 05:38 AM
  5. linear combination ?
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Mar 14th 2007, 05:54 PM

Search Tags


/mathhelpforum @mathhelpforum