Today has as its main goal the analysis of Linear Diophantine Equations. But first, let's look at some homework.
What about $gcd(a,a+1)$ or $gcd(a,a+2)$? Here, the Euclidean algorithm might be easiest! Doing the same thing either way with the first one is immediate; the second one we see that 2 is a multiple of the gcd right away, but checking that the gcd is two precisely when $a$ is even (and one otherwise) takes a little more effort.
Corollary 1.10 is going to be very useful later, because we will be able to simplify to where things are coprime in harder problems. Here is a great example; if $gcd(15,25)=5$, then $gcd(150,250)=5\cdot 10=50$ and $gcd(\frac{15}{5},\frac{25}{5})=1$. Enough said.
It is also helpful to look at Corollary 1.11 for both the proofs and for getting counterexamples. In many ways, finding examples where theorems are false if we don't use all their hypotheses are just as important as the proofs themselves, because they help us understand what is important about the theorem. Let's try a couple right now.
As said, the main goal for today is Linear Diophantine Equations. They have been studied since the late Roman era (by Greeks, of course), but it turns out that a general solution for equations like $6x+4y=2$ were already known in the early medieval days by Indian mathematicians like Aryabhata. When, shortly after 1600, Bachet de Méziriac came up with the same answer, it was only the first in a long line of people coming up with this solution again and again. And that's the one we are doing today!
There are several main cases in solving something like $ax+by=c$ for all integers $x,y$ that make it work.
In our case, trial and error tells us that $6x+4y=2$ can be solved with $x_0=1,y_0=1$, so the full answer is $$x=1+\frac{4}{2}n,\; y=1\frac{6}{2}n$$ or $$x=1+2n,y=13n\, .$$ Now let's try to do it with $15x21y=6$, a slightly harder example.
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.
Click to the left again to hide and once more to show the dynamic interactive window 
(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. 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.
Next time, we will look at a more subtle question:
This is similar to the conductor question; it turns out that this is related to integer programming, something with industrial applications.
Click to the left again to hide and once more to show the dynamic interactive window 
Let's explore this. How many such points are there in the following cases?
We should be able to get some good conjectures. Next time we'll resolve them.
Homework for next time, to be handed in:
Click to the left again to hide and once more to show the dynamic interactive window 
