MAT 338 Day 3 2011

3354 days ago by kcrisman

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.

  • Can we find a place where $gcd(a,b)\neq 1$, $a|c$ and $b|c$, but $ab$ does not divide $c$?
  • Can we get a good example with big numbers and $gcd(a,b)=1$ such that $a|bc$ and so $a|c$?

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.

  1. If $c$ is not a multiple of $gcd(a,b)$, then our previous theorems say this is impossible.
  2. If $a$ or $b$ is zero (say $b=0$ - in which case $gcd(a,b)=a$), we are just solving $ax=c$, so it is true precisely when $a|c$, and then all pairs $\left(\frac{c}{a},y\right)$ with integer $y$ are solutions.
  3. Suppose $a,b\neq 0$ and $c$ actually is the GCD of $a$ and $b\;\ldots$ then there is some work to do.
    • Your first step should be to get that GCD via the Euclidean algorithm - let's call it $d$.
    • Then go backwards (i.e. Bezout identity) to get one solution $(x_0,y_0)$.  That is important, since now at least one $ax_0+by_0=c$ is known.
    • Next, simply write down the whole solution set: $$x=x_0+\frac{b}{d}n,\; y=y_0-\frac{a}{d}n\;\text{ for }n\in \mathbb{Z}\; !$$  Notice that $a$ and $b$ switch their 'affiliation' here from $x$ and $y$ to $y$ and $x$.  Also note that $x$ and $y$ have $\pm$ involved.  It doesn't really matter which is which (switch $-n$ for $n$ to see why), but if they have the same sign it is wrong.   (When in doubt, try something and then check to see if the answers are right.)
    • It's easy to check this works: $$a\left(x_0+\frac{b}{d}n\right)+b\left(y_0-\frac{a}{d}n\right)=ax_0+\frac{abn}{d}+by_0-\frac{abn}{d}=c\; .$$ 
    • Why does this give all solutions?  Well, pick another solution $(x,y)$, and let's show it has this form.  Start with $$ax+by=c=ax_0+by_0\text{, so that }\frac{a}{d}(x-x_0)=-\frac{b}{d}(y-y_0)\; .$$  Now we use the corollary; since we divided out by the gcd, $\frac{b}{d}$ is coprime to $\frac{a}{d}$, and since $\frac{b}{d}$ does divide the left side, it must divide the other piece of the left side.  That means $$k\frac{b}{d}=x-x_0\text{, which means }x=x_0+k\frac{b}{d}\; ,$$ which is exactly what we just said was the form of all solutions.
  4. What if $c$ is not the greatest common divisor?  Then let $c=de$.  
    • We still have the same solution for $d$ - so find $d=ax_0+by_0$ for some $(x_0,y_0)$ as above.
    • Now if we multiply the whole thing by $e$, we have that $de=ax_0 e+by_0 e$, or that $c=a(x_0 e)+b(y_0 e)$ is a solution.
    • Now do exactly the same thing as above for the answer!  The surprise is that $x=x_0 e +\frac{b}{d}n, y=y_0 e+\frac{a}{d}n$ still works, but it's easy to check again, with virtually the same check working as above.  You don't need the $e$ in the fractions because they will just cancel anyway.

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=-1-3n\, .$$  Now let's try to do it with $15x-21y=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.

%auto @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) 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: html("The gcd of $%s$ and $%s$ is $%s$, which does not divide $%s$,"%(str(a),str(b),str(gcd(a,b)),str(c))) 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) 

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: 

  • How many such solution pairs $(x,y)$ to $ax+by=c$ have $x$ and $y$ both positive?

This is similar to the conductor question; it turns out that this is related to integer programming, something with industrial applications.

%auto @interact def _(a=slider(1,20,1,1),b=slider(1,20,1,1),c=slider(1,20,1,4)): ym = c/b + 1 xm = c/a + 1 p = plot(-(a/b)*x+c/b,-1,xm, plot_points = 200) lattice_pts = [[i,j] for i in [0..xm] for j in [0..ym]] 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 (coords[0]>0) and (coords[1]>0) and (a*coords[0]+b*coords[1]==c)] if len(line_pts)==0: html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))) html('No positive lattice points at all!') show(p+plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym) else: plot_line_pts = points(line_pts, rgbcolor = (0,0,1),pointsize=20) html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))) html('Number of positive lattice points = ' + str(len(line_pts))) show(p+plot_lattice_pts+plot_line_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym) else: html('Solutions to $%sx+%sy=%s$:'%(str(a),str(b),str(c))) html('No positive lattice points at all!') show(p+plot_lattice_pts, figsize = [5,5], xmin = 0, xmax = xm, ymin = 0, ymax = ym) 

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?

  • $x+y=4$, $x+y=5$, $x+y=6$, $\ldots$
  • $2x+y=4$, $2x+y=5$, $2x+y=6$, $\ldots$
  • $2x+2y=4$, $2x+2y=5$, $2x+2y=6$, $\ldots$
  • $3x+y=4$, $3x+y=5$, $3x+y=6$, $\ldots$

We should be able to get some good conjectures.  Next time we'll resolve them.

Homework for next time, to be handed in:

  1. Prove that the least common multiple of $a$ and $b$ is $ab$ precisely when $a$ and $b$ are coprime.  (This is a corollary of Theorem 1.12.)
  2. Prove that if the pairs $a$ and $c$, and $b$ and $c$, are both coprime pairs, then $ab$ and $c$ are also coprime. (One way to do these is using Bezout.)
  3. Prove that $gcd(a,a+2)=1$ if $a$ is odd and $gcd(a,a+2)=2$ is $a$ is even.
  4. For each of the following linear Diophantine equations, either find the form of a general solution, or show there are no integral solutions.
    • $21x+14y=147$
    • $30x+47y=-11$
  5. Find all integer solutions to the following system of equations. (Hint: do what you would ordinarily do in high school algebra or linear algebra! Then finish the solution as we have done.)
    • $x+y+z=100$
    • $x+8y+50z=156$
  6. Find the GCD of 151 and 187 using the Euclidean algorithm, then write it as a linear combination of these two numbers in two different ways.
  7. Pick an induction proof you didn't really get from the last time you did induction, and write it up in full detail.  It should not be one we've already seen, or that is in the text and can be copied out.
  8. Find the GCD of 500000001 and 5000001 in any way you see fit other than asking someone else.  (It can be quite fun to try this with different amounts of zeros, but I'll try to restrain my enthusiasm.)
  9. Make conjectures about the patterns in the positive integer solutions to $ax+by=c$ situation above.  For sure I want you to do this for the ones I mention there, but try some others and see if you see any broader patterns!
  10. Give as much information about the conductor as you can.  Ideally, you would have a proof of a formula for it, as well as a proof of the number of values which are not representable, but give me whatever you were able to discover and/or prove.   The Sagelet below can help with this!
@interact def _(a=(3,[2..10]),b=(4,[2..10]),n=(20,[10..50])): list_of_them=list(set([a*x+b*y for x in srange(n/a+1) for y in srange(n/b+1)])) list_of_them=[item for item in list_of_them if item <= n ];list_of_them.sort() html("The nonnegative integers up to $n=%s$ which can be"%(str(n),)) html("written as positive combinations of $a=%s$ and $b=%s$ are:"%(str(a),str(b))) print list_of_them 

Click to the left again to hide and once more to show the dynamic interactive window