MAT 338 Course Notes Day 3

Complements to Bezout

There are several interesting things that the linear combination version of the gcd can give us.

Relatively Prime

Remember, $a$ and $b$ have greatest common divisor 1 precisely when you can write $ax+by=1$ for some integers $x$ and $y$. That means, in fact, that you can write any integer as a (linear) combination of $a$ and $b$ if their gcd is 1!

This is a property I think people would have come up with no matter how the development of mathematics had gone; the pairs of integers such that you can write any number as a combination of them. We call these relatively prime numbers or coprime numbers.

Here are two interesting facts about coprime integers $a$ and $b$:

The first is not too hard to prove, if you think in terms of Bezout. It does need a little cleverness.

It's also useful to try to find counterexamples! Can you find place where $gcd(a,b)\neq 1$, $a|c$ and $b|c$, but $ab$ does not divide $c$?

Making gcd Computations Easier

What makes finding $gcd(42000,60000)$ so easy? Let's discuss.

If $gcd(a,b)=d$, could you make a guess as to a formula for $gcd(ka,kb)$ (for $k>0$)? Can you prove it? (Hint: here is where our original definition or the Bezout version could be useful.)

Linear Diophantine Equations

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. You should definitely follow the steps with specific numbers (suggested) to see how each proof works!

If $c$ is not a multiple of $gcd(a,b)$

If $a$ or $b$ is zero

If $c=gcd(a,b)$

Suppose $a,b\neq 0$ and $c$ actually is the GCD of $a$ and $b\;\ldots$ then there is some work to do. Follow along with $a=60$, $b=42$, and $c=6$.

If $c$ works, but is not the gcd

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.

    • Examples

    Here's an easy example: $$6x+4y=2$$ 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.

    Geometry of Equations

    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.  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.  

    Positive solutions

    Here is 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.

    Let's explore this.  How many such points are there in the following cases?

    Can you get any good conjectures?

    Exercises

    Homework for next time, to be handed in:

    1. If $gcd(a,b)=d$ and $k>0$, prove a formula for $gcd(ka,kb)$.
    2. Define the least common multiple of $a$ and $b$ to be the smallest positive number which is divisible by both $a$ and $b$. Prove that the least common multiple of $a$ and $b$ is $ab$ precisely when $a$ and $b$ are coprime.
    3. 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.)
    4. Prove that $gcd(a,a+2)=1$ if $a$ is odd and $gcd(a,a+2)=2$ is $a$ is even.
    5. For each of the following linear Diophantine equations, either find the form of a general solution, or show there are no integral solutions.
    6. 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.)
    7. 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.
    8. Find the gcd of 500000001 and 5000001 in any way you see fit other than asking someone else.
    9. Find the gcd of three four digit numbers, none of which is divisible by ten.
    10. Prove, by induction, that if $c$ divides integers $a_i$ and we have other integers $u_i$, then $c|\sum_{i=1}^n a_iu_i$.
    11. Explore 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!
    12. Give me as much information about the conductor as you have thus far accumulated.
    13. You know the Fibonacci numbers $1,1,2,3,5,8,\cdots$ where $f_{n+2}=f_{n+1}+f_{n}$. Try applying the Euclidean algorithm to a pair of consecutive Fibonacci numbers? How long does it take compared to how far you are in the sequence?