Existence of Solutions for Linear Equations with Integer Coefficients

[scottstapp]

Homework Statement

I just have a general question.

Suppose a,b and c are integers with a and b not both 0. There exists d=gcd(a,b) and ax+by=c.
From this I know that d|a and d|b but how do I know that there exists x,y such that d|(ax+by) where ax+by does not equal d and d|c ?

I cannot simply state that because d|ax and d|by, it must divide their sum. Or can I?

Thanks

 

[owlpride]

If d|a and d|b, then d|(ax + by) for all integers x and y. This is very easy to see in different notation: If d|a and d|b, then a = a'd and b = b'd and ax + by = a'dx+b'dy = d(a'x+b'd).

If d|(ax +by) and ax+by=c, then d|c obviously enough.

However, it is possible that d = c. In fact, the Extended Euclidean Algorithm will produce an x and y such that ax + by = gcd(a,b).

 

[scottstapp]

Thanks owlpride, that's what I was thinking but I just needed some reassurance.