Results 1 to 3 of 3

Math Help - proof integer can be written as a linear combination of 2 others

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    66

    Post proof integer can be written as a linear combination of 2 others

    Ok here is my problem, let a,b be integers at least one not 0. Prove any integer c can be written as a linear combination of a and b iff gcd(a,b)|c

    I think i got the half starting with assuming c can be written as a linear combination but im not sure where to go when you need to go the other way. I know to assume gcd(a,b)|c let d = gcd then d|c and c = xd i know that d|a and d|b since it is there gcd but am not sure how to get it into the form of a linear combination of a and b. If i let one of them equal 0 i can use the fact that d|a and say b = 0 the a = dy and c = xdy which is a linear combination but that doesnt seem right to me
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Black's Avatar
    Joined
    Nov 2009
    Posts
    105
    Let c be an integer such that c = ka + lb for some integers k and l. Since gcd(a,b)|a and gcd(a,b)|b, we have gcd(a,b)|ka+lb. Therefore, gcd(a,b)|c.

    If gcd(a,b)|c, then we have c = r*gcd(a,b), for some integer r. We use the fact that gcd(a,b) can be written as a linear combination of a and b. c is just that linear combination multiplied by r, which is also a linear combination of a and b.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Shanks's Avatar
    Joined
    Nov 2009
    From
    BeiJing
    Posts
    374
    Black is quite right!
    You can also see
    http://www.mathhelpforum.com/math-he...b-m-gcd-b.html here.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Linear combination and a proof for the area.
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 8th 2011, 12:08 PM
  2. Replies: 1
    Last Post: July 13th 2010, 07:54 AM
  3. Replies: 0
    Last Post: February 3rd 2010, 12:48 PM
  4. Replies: 2
    Last Post: October 3rd 2009, 12:34 PM
  5. Linear combination proof
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: July 14th 2009, 11:16 PM

Search Tags


/mathhelpforum @mathhelpforum