NTIC Geometry of Equations

Section 3.2 Geometry of Equations

But just proving things are true and using them isn't enough. Why is the theorem true, intuitively? I believe the right way to approach this is with geometry, as in the following figure. Then try out the interactive cell below to see how things change with different coefficients.

Solutions to $3x+2y=10$ with $x,y\leq 10$

xxxxxxxxxx
 
@interact
def _(a=slider(-10,10,1,6),b=slider(-10,10,1,4), c=slider(-20,20,1,2),viewsize=slider(3,20,1,5)):
    p = plot(-(a/b)*x+c/b,-viewsize,viewsize, plot_points=200)
    lattice_pts=[[i,j] for i in [-viewsize..viewsize] for j in [-viewsize..viewsize]]
    plot_lattice_pts = points(lattice_pts,rgbcolor=(0,0,0), pointsize=2)
    if mod(c,gcd(a,b))==0:
        line_pts = [coords for coords in lattice_pts if a*coords[0]+b*coords[1]==c]
        if line_pts==[]:
            plot_line_pts = Graphics()
        else:
            plot_line_pts = points(line_pts,rgbcolor=(0,0,1), pointsize=20)
        pretty_print(html("Showing solutions to $%sx+%sy=%s$ in this viewing window"%(str(a),str(b),str(c))))
        show(p+plot_lattice_pts+plot_line_pts, figsize=[5,5], xmin=-viewsize,xmax=viewsize, ymin=-viewsize,ymax=viewsize)
    else:
        pretty_print(html("The gcd of $%s$ and $%s$ is $%s$, which does not divide $%s$,"%(str(a),str(b),str(gcd(a,b)),str(c))))
        pretty_print(html("so no solutions to $%sx+%sy=%s$"%(str(a),str(b),str(c))))
        show(p+plot_lattice_pts, figsize=[5,5],xmin=-viewsize,xmax=viewsize, ymin=-viewsize,ymax=viewsize)

🔗

The little gray dots in the graphic above are called the integer lattice; this is the collection of all the intersections of the lines

$y=m,x=n$ for all integers

$m,n\text{.}$ There are many mathematical lattices (many quite intimately connected to number theory), but we will focus on this one in this text.

🔗

Definition 3.2.2.

The integer lattice is the set of points $(m,n)$ for $m,n\in\mathbb{Z}\text{.}$

🔗

In the graphic, for instance

$(-2,3)$ is probably visible; on the other hand, the point

$(-1,1/2)$ should not have 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

$\begin{equation*} y=-\frac{a}{b}x+\frac{c}{b} \end{equation*}$

🔗

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\text{,}$

$b\text{,}$

$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, Theorem 3.1.2 now expresses a very mysterious geometric idea, depending on whether

$\begin{equation*} \gcd(a,b)\mid c \end{equation*}$

If so, then this line hits lots of the lattice points; 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 interact above.
Secondly, it makes the proof of why Theorem 3.1.2 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}\text{.}$ 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\text{.}$ Namely, as pointed out in in a 2013 American Mathematical Monthly article by S. A. Rankin [C.7.21], the “solution provided … lies nearest to the origin.” Try the interactive cell at the beginning of this subsection to convince yourself of this!

🔗

Although we won't pursue it, there is a question which this formulation in an online text brings up. Namely, given that the ‘line’s in question are themselves only pixellated approximations whose coordinates may not satisfy

$ax+by=c\text{,}$ what is the connection between the computer graphics and the number theory? See How to Guard an Art Gallery [C.6.7], Chapter 4, for an accessible take on this¹As well as several other topics in this text! But you'll have to read it to find out which ones. from a number-theoretic viewpoint, as well as Exercise 3.6.23.