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.