Results 1 to 3 of 3

Math Help - 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 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 .
    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: November 16th 2011, 01:55 AM
  2. linear combination
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: January 6th 2011, 03:27 PM
  3. Linear Algebra - Linear Combination/Span
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 13th 2008, 06:06 PM
  4. linear combination problem dealing with uniqueness
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 10th 2008, 05:38 AM
  5. linear combination ?
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: March 14th 2007, 05:54 PM

Search Tags


/mathhelpforum @mathhelpforum