Linear Diophantine Equation and EEA Example

In this video, we're going to talk about Linear Diophantine Equation Theorem Part 2, or LDET2 as it's known in the notes.

Theorem (LDET2): Let $\gcd(a,b)=d\neq 0$ . If $x=x_0$ and $y=y_0$ is one particular solution to the linear Diopohantine equation $ax+by=c$ , then the complete intger solution is:

$x=x_0+\frac{b}{d}n,y=y_0-\frac{a}{d}n,\forall n\in\mathbb{Z}$

So what this is saying is, 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.

Example

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.

Solve the Linear Diophantine Equation

$868x+465y=62$

Solution

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.

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.

$x$	$y$	$r$	$q$
$1$	$0$	$868$
$0$	$1$	$465$

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?

$x$	$y$	$r$	$q$
$1$	$0$	$868$
$0$	$1$	$465$
$1$	$-1$	$403$	$1$

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

$x$	$y$	$r$	$q$
$1$	$0$	$868$
$0$	$1$	$465$
$1$	$-1$	$403$	$1$
$-1$	$2$	$62$	$1$
$7$	$-13$	$31$	$6$
$-15$	$28$	$0$	$2$

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(7)+465(-13)=31$ .

By the way, since this is a video, and on assignments and things like this, you should be able to check that all of these rows are valid. 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 $868(7)+465(-13)=31$ , to get to $62$ well we know that $31\cdot 2=62$ . So we multiply this solution by $2$ , and we get $868(14)+465(-26)=62$ .

There we have it. Alright, so we have our solution here, $14$ and $-26$ , now let's use LDET2. What does LDET2 say? Buy one, get infinitely many free.

So we have our first solution, $14$ and $-26$ , how do we get the rest of the solutions? So by LDET2, we have that

$x=14+... \quad\quad y=-26-...$

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 add a term that will get cancelled out when I combine it with the $465$ . So if I replaced the blanks with $868$ and $465$ respectively

$\begin{align*} 868(14+465)+465(-26-868)&=868(14)+868(465)+465(-26)+(465)(-868)\\ &=868(14)+465(-26)\\ &=62 \end{align*}$

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

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

$x=14+\frac{465}{31}n=14+15n \quad\quad y=-26-\frac{868}{31}n=-26-28n$

Now this will give us everything. Why do I take out the $31$ ? Well $868$ and $465$ each have $31$ as a common factor. So if I divide out by that common factor, then I can still multiply those two things together and get the cancellation that you want.

The key is that these two things are integers and that's going to be the case since $31$ is the $\gcd$ . 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 $-1$ and $2$ as your solution, you still get the same solution set.

How do we see that? Well for the $x$ equation, if I plug in $n=-1$ ,

$x=14+15(-1)=-1$

If I plug in $n=-1$ into the $y$ equation,

$y=-26-28(-1)=2$

So indeed I still get this solution and I'll get all the other ones, right, so if you do it starting with this $x=-1$ and $y=2$ as your 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 opposite terms 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 $15$ and positive $465$ times negative $28$ , so at least the signs work, right? $868\cdot 15$ is positive, so we need $465\cdot (-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 $x=14+15n$ into $868x+465y=62$ and plug in $y=-26-28n$ to the same 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.