# Thread: proof integer can be written as a linear combination of 2 others

1. ## 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

2. 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.

3. Black is quite right!
You can also see
http://www.mathhelpforum.com/math-he...b-m-gcd-b.html here.