But just proving things are true and using them isn't enough. Why is it true, intuitively? I believe the right place to do this is in geometry. Try out the following interactive cell.

The little gray dots in the graph above are called the integer lattice. You may treat this as a definition. There are many lattices, but only one which is basically all the intersections of \(y=m,x=n\) for all integers \(m,n\). So for instance \((-2,3)\) is probably visible; however, note that \((-1,1/2)\) is not a little dot, because it doesn't have integer values.)

Now, since \(ax+by=c\) may be thought of as a line (in fact, the line \[y=-\frac{a}{b}x+\frac{c}{b}\] with slope \(-\frac{a}{b}\)), we now have a completely different interpretation of the most basic number theory question there is, the linear Diophantine equation. It is simply asking, "When (for what \(a\), \(b\), \(c\) combinations) does the line hit this lattice? If it does, can you tell me all intersections?" If you play around with the sliders you will quickly see that things work out just as promised in the theorems.

But let's go a little deeper. There are three interesting insights we can get.

• First, the theorem now expresses a very mysterious geometric idea; if \(gcd(a,b)\mid c\), then this line hits lots of the lattice points - and if not, the line somehow slides between every single one of them! You can check this by keeping \(a,b\) the same and varying \(c\) in the Sagelet above.
• Secondly, it makes the proof of why this gets all of the answers much clearer. If you have one answer (for instance, \((1,-1)\)) and go right by the run and down by the rise in \(\frac{a}{b}\) (our example was \(a=6,b=4\)), you hit another solution (perhaps here \((-3,5)\)) since it's still all integers and the slope was the line's slope. But wait, couldn't there be points in between? Sure - so make \(\frac{a}{b}\) into lowest terms (e.g. \(\frac{3}{2}\)), which would be \(\frac{a/d}{b/d}\). And this is the 'smallest' rise over run that works to keep you on the line and keep you on integer points.
• Third, it can help clarify the role of the solution which the Bezout identity (extended Euclidean algorithm) gives for \(ax+by=c\). Namely, as pointed out in a recent article in the American Math Monthly by S.A. Rankin, the "solution provided ... lies nearest to the origin." Again, try the applet to convince yourself of this!