We've talked a little bit throughout the rest of the week on
Linear Diophantine Equations.
What’s the idea here? Well we want to solve
equations of the form a x plus b y equals c,
where a, b, and c are integers
but there's a catch, right, and the catch is that we don't just want
to solve these for real numbers x and y,
we want to solve these for integers x and y.
Now if you think about this,
when x and y are real, we've actually already done this.
Well by “we” I mean “you”,
and also by “we” I mean “you did this in high school”.
This is the equation of a line, so
solving these for real values is the same as
solving for the equation of a line, right? So you have your slope,
your negative a over b in this case,
and you have your…
what do you call this - your y-intercept value, your c over b,
and you could find points, right?
Once you find your…you have x’s, then you can find y’s,
right, so the solution set
over the reals gives you the equation of a line.
Over the integers it gives you a subset of that line
and it'll turn out as we'll see from LDET2,
that the points on your line are equidistant from each other. They're equally spaced out,
and they're spaced out by some factor depending on your slope.
It's not exactly the slope minus a over b,
but as you can see - as you will see - what will happen is
you'll go a little bit over and a little bit up,
or a little bit over and a little bit down,
depending on the slope of your line,
and you're going to create these new points that'll appear.
We'll see that in a minute, I'm getting ahead of myself.
So two things we want to know when we're dealing with a Linear Diophantine Equation:
one, does it have a solution at all?
And two, what are all of the solutions to a Linear Diophantine Equation?
These are answered in two theorems: LDET1 and LDET2.
So let's take a look at LDET1:
“Let d be the gcd of a and b.
The LDE ax plus b y equals c has a solution
if and only if d divides c.” Okay? So a couple of things to note here.
Whenever we write the letters LDE, we mean a Linear Diophantine Equation,
so by those three letters we mean a, b, and c are integers,
and we're looking for solutions x and y as integers.
So I've hidden the proof. This is something that you should
probably pause the video and actually try.
This proof isn't too hard.
You should be able to write a proof of this.
So the LDE has a solution
if and only if d divides c.
This is an “if and only if” proof so we have to divide this into two components.
Part 1 is assuming that the LDE has a solution,
and part 2 is assuming that d divides c.
So let's go through the proof. Again, just rip it off like a band-aid.
So here we're going to assume that a x plus b y equals c,
the LDE has an integer solution,
and we're going to call it x naught and y naught.
Since d divides a and d divides b, by DIC we have that d must divide the
integer linear combination given by a x naught plus b y naught.
But a x naught plus b y naught, that was just equal to c, so we have that d divides c.
And that's it in that direction.
So in the opposite direction, we're going to assume that d divides c.
What does that give us? Well that means that there exists an integer k
such that d k equals c, right? That's what d dividing c means, okay?
So we have this and what does that mean? Well...
doesn't look like it's helped us much, but we do have that we -
well okay we've set the gcd of a and b to be d.
So we can use some of our hammers and, in this case Bézout’s Lemma,
or the Extended Euclidean Algorithm, to get
that there exists integers u and v such that
a u plus b v is equal to the gcd of a and b and that's d.
So if you multiply this equation by what value?
Well we want to get c on the right, so if we multiply everything by k,
we're going to get d k over here and that's equal to c,
and if we do this on the left, then we can just group
the u and the k together and the v and the k together and we actually
get a solution to our LDE given by u k and v k.
So we use Bézout’s Lemma,
and we use the definition of divisibility.
So notice that this also gives you a way to find a solution, right?
The Extended Euclidean Algorithm can be used to find a solution
of a Linear Diophantine Equation,
and that's the good news about this proof
is that it actually is constructive. You can actually find the u and v
by using the Extended Euclidean Algorithm, which is pretty cool.
So now that we have a solution, or we now have a criteria for when we have a solution,
and it's really strong, it’s an “if and only if”, it's necessary and sufficient,
what do we do? So we have this really strong criteria,
how can we find all of the solutions?
And that's given by LDET2...
oh I put the proof on here I didn't mean to, that's okay.
So LDET2, what does this say?
“Let d be the gcd of a and b, where a and b
are not 0…” this just eliminates silly cases,
“…if x and y is equal to x naught, y naught
is a solution to our LDE a x plus b y equals c,
then all solutions are given by the following set.
So the set is a set of ordered pairs,
and the ordered pairs are of the form x naught plus b over d, times n,
and y naught minus a over d, times n, okay?
So as n ranges over all the integers, this gives you an infinite pairing of integers,
and it's formed by this pairing.
Think back to that line analogy, right?
So what we're doing essentially is we're taking some x naught
and we're incrementing it by some
b over d multiples of n,
and...so that's going, I guess, in the x-direction
instead of going up, I'm just going to go in the x direction,
and in the y direction, every time we go over 1 we're going to go down
by an a over d times n, so we're going to go
over and down, over and down, over and down, over and down,
and that's going to give us a line like this.
This of course assumes that a and b are positive.
If a and b are negative, the slope of the line is going to change.
It's not a huge deal, but it will change the
little picture that I'm drawing with my hands.
But that's the main idea.
So the proof.
So one thing we have to note is that
we really need - well okay there's two things we need to show:
first we have to show that all of these are actually integer solutions to the Linear Diophantine Equation,
that's easy. Just plug it in and check.
What's going to happen? You're going to get your a b over d times n,
and you're going to get your negative a b over d times n.
So those two terms will cancel,
and the x naught y naught we've already started [with as] a solution to the LDE, right?
So notice that because we have a solution, we know that the gcd of a and b does divide c.
Turns out not to be useful for this proof, but that’s something to think about.
So now in the other direction, what do we need to show?
We need to show that all solutions can written in this form.
So how are we going to start? We're going to start with another solution
some new x and y as a different solution to our LDE.
Well what does that mean? Well we have these two equations, a x plus b y equals c
and x naught plus b y naught equals c.
So if you look at these two equations, we notice there's a lot of similarities,
and one way to get rid of them is to cancel the c.
So let's subtract the two equations,
and what does that give us? It gives us a times
x minus x naught is equal to negative b times y minus y naught,
after a little bit of rearranging.
And now what we'd like to do is we'd like to say something along lines of,
“Well a must divide y minus y naught,”
but of course that's not true.
And why isn't that true? Well it's not true because a and b could have common divisors,
and that could be a problem. So what we can do is we can actually divide out by d,
which is the gcd, of a and b. So if we divide out by d,
what do we get? Well now we get that the gcd of a and d
and the gcd of minus b and d, or the gcd of b and d, either way,
that's equal to 1, and that's by DBGCD, right?
If we divide by the gcd, then these two things are co-prime.
Remember co-prime means that their gcd is 1.
So now looking at this, and now since we have…
I'm going to go the other way, so instead of saying a divides y minus y naught,
I’m actually going to go b divides x minus x naught.
So now let's look at b over d. So b over d divides this thing:
negative b over d times y minus y naught,
and that thing is equal to
a over d times x minus x naught.
So by Coprimeness and Divisibility, b over d divides x minus x naught.
Again, b over d and a over d are co-prime,
and b over d divides the product of two things, so it must divide the other thing,
which is x minus x naught.
Thus there exists an integer n such that
x is equal to x naught plus b over d n,
that's just by definition and rearrangement.
Now, at this point, something to mention here, right,
is that you kind of want to argue…
you want to say, “Well similarly y minus y naught is equal to
a over d times n,” right?
But the thing that's not clear is it's not clear why the n here
had to be the same as the n when I do this with a.
So you actually can't quite do the same… you can't do the exact same argument,
what you can actually do is use this information
that x minus x naught is equal to b over d in this equation here,
to actually show that a over d
times n, or negative a over d times n, is equal to y minus y naught,
and that's what you have to do. So instead of arguing similarly,
just actually use this information, substitute it in, and then simplify.
And that's going to complete your proof.
So again summary of LDET2.
Once you have one solution, you have them all,
and you can find them by looking at multiples… or by
multiples as follows. So take x naught and add
b over d times n to it, and take y naught and subtract a over d times n.
So one solution gives you all the solutions.
This is a pretty cool feature of LDET, right?
If you think about like quadratic equations and cubic equations,
just because you have one solution to a quadratic equation or a cubic equation equals 0
doesn't mean that you get both solutions. Sometimes there's more work to be done.
Specifically in the cubic case. The quadratic case
maybe you can argue that I can find the other one.
But here you just get them all for free basically.
You don't have to do any other work. Once you have one you have them all.
Let's see an example.
Solve the LDE 20x plus 35y equals 15.
So again pause the video at this point. Hopefully you've paused it a couple of times,
and hopefully you’ve paused this video in general. It's a very long video
so hopefully you're taking breaks while watching it.
Pause the video, try this out.
Physically try to see if you can solve this Linear Diophantine Equation.
Hopefully you've come back now.
So let's try to do this together, okay?
So the first thing that I notice here is that I have 20, 35, and 15.
I can actually prime factor these very quickly in my head.
4 times 5, 7 times 5, and 3 times 5,
and I quickly see oh well 5 is a prime factor of all of these things,
and it's the largest common factor of all these things.
So I can do that and I can divide everything by 5.
What's that going to give me? Well it's going to give me
4x plus 7y equals 3.
So now when I have this equation,
you have options, right? If you don't see a solution immediately, you can use
the Extended Euclidean Algorithm to find a solution.
There's no problem with that, right, we know that the gcd of 4 and 7 is 1,
so LDET1 will tell us that we will have a solution here.
Just like LDET1 told us before, right? If I divide by 5,
it doesn't change whether or not I have a solution.
So that's excellent, so now I know I have a solution.
So now I just have to find a solution. Well how do I find one?
Here I can just do it by inspection.
7 minus 4 I quickly notice is 3,
so if I make x equals minus 1 and y equals 1, I get a solution.
Again if you don't see it, run through the Extended Euclidean Algorithm. It’ll take
a couple of seconds, but it's better than not finding a solution.
If you don't find one in 10 seconds, just run through the algorithm, it's okay.
So define all solutions we invoke LDET2,
Linear Diophantine Equation Theorem 2,
and how do we find all solutions? Well we have one,
to find all the rest of them just take
x is equal to x naught plus
b over d, so in this case, 7 over the
gcd of 4 and 7, times n,
and y is equal to the solution that we found, y naught
minus a over d, times n.
So here a and b are both positive, so that's nice,
and here the gcd 4 and 7 is actually 1. Why am I writing it like this?
I'm writing it like this just to emphasize that
if you didn't find the gcd, you should make sure that
divide by it when you're invoking LDET2.
And here n is any integer, okay, so that's another
big thing to note, right? Quantify your variables when you're using them.
So here, n is an arbitrary integer, and x and y is our solution
to this Diophantine Equation.
Notice that this is equivalent to the solution set:
x equals minus 1, minus 7, over the gcd of 4 and 7 times n,
and y is equal to 1 plus 4 over the gcd of 4 and 7 times n.
So notice here that I flipped the signs here.
Why is that okay? So
the reason why this is okay, it's just a technical thing,
but it's not hard to understand so let's try to understand this.
As n varies over all integers,
n is going to take on positive and negative values.
So in this solution set when I make n equal to 1, I get
negative 1 plus 7, and I get 1 minus 4.
Well if I make n equals to 1 down here,
I don't get the same solutions, but if I make n equal to minus 1 what do I get?
I get minus 1, minus 7 times negative 1, so that's minus 1 plus 7,
oh that's the same solution that I had up here.
And if I do that over here, I'm going to get
1 plus 4 times negative 1,
so 1 minus 4, oh that's the same solution I had over here when I plugged in n equals 1.
So really what you're doing is a change of variables. You're sending n to negative n,
and you're substituting in negative n instead of n.
That doesn't matter because they're just arbitrary integers,
and if n is an arbitrary integer, then negative n - so
as n ranges over the integers,
then negative n also ranges over the integers, right?
1 corresponds to minus 1,
negative 5 corresponds to 5
and so on and so forth, right, there's this matching that occurs.
So there's multiple ways to write the solution set. Don't let
the flipping of the signs bother you too much.
That's all I want to say about that.