Let \(d = (a,b)\). If \(d\) divides \(a\) and \(b\), then it can divide any linear combination. If \(x\) and \(y\) are integers, then \(ax+by\) is a linear combination of \(a\) and \(b\), which means \(d\) can divide it. In other words, \(d|c\). The contrapositive of this is that if \(d \nmid c\), then \(x\) and \(y\) cannot be integers.
Now suppose \(d|c\). Let \(e\) be an integer such that \(de=c\). Since \(d = (a,b)\), then \(d\) is the smallest positive linear combination. Let there be integers \(s\) and \(t\) such that \(d=as+bt\). If we multiply both sides by \(e\), then:
This means we have one solution for \(x\) and \(y\). Let's call them \(x_0\) and \(y_0\): \(x_0=se\) and \(y_0=te\). This means:
However, we can get infinite solutions: \(x=x_0+bm\) and \(y=y_0-am\), where \(m\) is an integer. This works because:
Since \(b/d\) and \(a/d\) are integers and smaller than \(b\) and \(a\) respectively, then we can let \(x=x_0+\frac{b}{d}m\) and \(y=y_0-\frac{a}{d}m\) to get more solutions.
We have shown that there are either no solutions (when \(d \nmid c\)) or there are infinite solutions (when \(d | c\)). Now we are going to prove that if there are infinite solutions, then they are all of the form \(x=x_0+\frac{b}{d}m\) and \(y=y_0-\frac{a}{d}m\).
Let \(x=x_0\) and \(y=y_0\) be one of our solutions. This means:
Divding both sides by \(d\):
Since \((a/d,b/d)=1\), then \((a/d)|(y_0-y)\), which means there exists an integer \(n\) such that \((a/d)n =(y_0-y)\). This means:
Now putting this in \(a(x-x_0) = b(y_0-y)\):
This shows that if \(x=x_0\) and \(y=y_0\), then the other solutions are of the form \(x = x_0 + \frac{b}{d}n\) and \(y=y_0-\frac{a}{d}m\).