In this video, we're going to talk about Linear Diophantine Equation Theorem Part 2,
or LDET2 as it's known in the notes.
So suppose we have the gcd of a and b is d for some nonzero d,
and if we have one solution to our
linear Diophantine equation a x plus b y equals c,
then the complete integer solution is given by the following:
so x equals x naught plus b over d n,
and y equals y naught minus a over d n.
So what this is saying is,
it's kind of like…it's like buy one get infinitely many free,
right? So once you have one solution to a linear Diophantine equation,
then you essentially have all of them, okay?
At least when it's a binary linear Diophantine equation.
Alright so here notice that
n is parameterized…
it's a parameter.
So the number of solutions here is infinite, right,
it depends on this n and n can vary.
So once you have one solution, you can find them all;
that's the moral of this.
So let's see an example of a linear Diophantine equation,
and let's try to find a solution.
By the way, to find the first solution, you can either use inspection, you can just
find one and show that it works,
or you can use the Extended Euclidean Algorithm.
So I haven't done a video on the Extended Euclidean Algorithm yet,
so I'm going to do one on one now.
So here is the sample that we have.
Solve the linear Diophantine equation
868x plus 465y equals 62.
Now off the top of my head, I don't know
if 868 and 465 have a common factor.
It's possible, but I don't see one immediately.
So sometimes if you see one immediately you can reduce the equation to make your life easier.
I don't see one so I'm going to just
plug through the Extended Euclidean Algorithm.
Okay? So…
use EEA.
So that's how we're going to start our proof,
we are going to start by using the Extended Euclidean Algorithm.
Let's see what we have.
Okay, so let's set up our table.
So we're going to start with 868 as our first remainder,
465 as our second remainder,
and we're going to start dividing these one at a time.
So 465 goes into 868 one time.
So going to put 1 in our q in the third row.
Now we're going to subtract the first row
minus 1 times the second row,
and what's that going to give us? That's going to give us
1 minus 1 and 868 minus 465, that should be 403.
So let’s fill in that table.
And now we're going to repeat this, so now we’re going to do 403 into 465, that goes in again once.
The difference there is 62,
and again we're going to get a 2 and so x is minus 1 and y is 2, right,
so we're going to subtract second and the third row.
Then we're going to do it with the third and the fourth row, fourth and the fifth row, and so on and so forth.
Here's where we get an interesting little case. So
how many times does 62 go into 403?
It's definitely at least 5 since 6 times 5 is 30,
turns out it’ll go in 6 times, so we're going to put a 6 there.
Now 6 times 62 that should be 372.
403 minus 372 that's 31.
Thankfully, the other two computations are a little easier.
So let me save it just so that we can see it.
So 6 - so we’re taking row three minus 6 times row four.
So minus 1 minus 6 times 2, that’s 12, so it's minus 13,
and then the first one should be a 7.
Okay, that's it, and then now
31 goes into 62 well that actually goes in exactly twice.
So...
let me put one more
row in this…twice and the remainder is 0,
and I'm not going to do the x and y here because…
what the hell, I'll do it. 28 and
negative 15, that should be right.
It's actually small enough that we can do it. So let's extend our row by one more, there we go.
By the way, you should get down to 0 in your table, okay, you need to
show the marker that you know when to stop and you stop when the remainder is 0.
It's important for the computation side.
Just to know when you have to stop this algorithm.
Okay that's great. So…
here we get a little bit lucky
So we actually have a row with 62 in it.
Let's suppose that we didn't though, for the sake of argument,
or we didn't notice that we could just use this row to get our 62 equation,
right? So let's go down to the 31.
It's not going to always be this way, this just happened to work out.
So what's our solution? So therefore,
what do we have? So 868
times 7 plus
465 times minus 13
is equal to 31.
By the way,
since this is a video and on an assignment things like this,
you should be able to check that all of these rows are valid.
Okay? There's no reason not to.
On an exam, maybe it's a little tricky, but
still it would be a good way to validate your work.
Again, your notes refer to this as a certificate of correctness.
Okay great, so now that we have this solution here,
to get to 62 well we know that 31 times 2 gives us 62.
So we multiply this solution by 2…
and what are we going to get? We're going to get 868 times 14
plus 465 times negative 26 is equal to 62.
There we have it. Alright, so we have our
solution here, 14 and minus 26.
So let’s…
where to now? Okay,
so we have our solution
now let's use LDET2. What does LDET2 say?
Buy one, get infinitely many free. So we have our first solution, 14 minus 26,
how do we get the rest of the solutions? So by
LDET2,
we have that
x is equal to 14 plus something
and y is equal to negative 26 minus something.
So how do I fill in the blanks here?
So...
what do I do to get the blank? Well okay, so the
14 belongs to the 868, right, so the idea is that I want to cancel out…
I want to add a term that will get cancelled out when I
combine it with the 465. So if I just put 465 here, I'll get 868
plus 465, and over here
I would put 868 or negative 868, and I would get 465 minus 868, so those will cancel.
Now it turns out that that's the right idea but it's not going to give us the full solution.
To get the full solution, you also need to account for the gcd.
And how does that work? So I'm going to take 465 and I'm going to divide it by 31,
and then the other one
I'm going to take…
868 and I’m going to divide it by 31. Let's see what we get.
I need to multiply both by n.
Now this will give us everything, okay, so when I take out the - why do I take out the 31?
Well 868 and 465 each have 31 as a common factor.
So I want to - so if I divide out by that common factor, then
I can still multiply those two things together and
these two numbers together and get the cancellation that we want.
The key is that these two things are integers
and that's going to be the case because 31 was the gcd.
So if I simplify this a little bit, I'm going to get 14 plus
465 divided by 31. I know because I made this example I know it's 15,
and on the other side it's minus 26 minus 28n.
So let's
see that.
And of course here, n is just some integer.
And that's perfect. By the way, so as an exercise,
if you did start with minus 1 and 2 as your solution, you still get the same solution set.
How do we see that? Well here if I plug in n equals minus 1, I get
negative 1 for my x and if I plug in minus 1 here I get 2 for my y.
So indeed I still get this solution and I'll get all the other ones,
right, so if you want, you could...if you do it starting with this solution,
might be a good exercise, see what you get
and try to justify to yourself that you actually get the same answer.
And this gives us a complete set of solutions. So again this
LDET2 is very powerful, right? Once you get one solution, you have all of the solutions
by doing this simple little computation by taking the other term,
dividing by 31, and then taking this term and dividing by 31.
Always double check your sign. It's a very easy thing to get wrong
and it's a very easy thing to check, right? 868 times positive…
let's do this one, times positive 15
and you get positive 465 times negative 28, so
at least the signs work, right? 868 times 15 is positive,
so we need 465 times negative 28 to be negative, and it is.
So always do that last little check just to make sure that you can
cancel out those extra n terms when you plug it in here.
And again, as an exercise, plug in this x into this equation
and plug in this y to this equation and expand and see what happens.
I'll leave that for you to do, I think it's worth doing, but I won't do it
because it's a little bit tough on the computer. It's just tough to type out,
and the value is more when you actually do it than it is when you actually see me do it.
Okay, so hopefully this helps you out,
gives you a little bit of an idea of EEA and LDET2.
That's all I have to say, thank you very much.