1 00:00:00,000 --> 00:00:05,566 In this video, we're going to talk about Linear 
Diophantine Equation Theorem Part 2, 2 00:00:05,566 --> 00:00:08,866 or LDET2 as it's known in the notes. 3 00:00:08,866 --> 00:00:13,100 So suppose we have the gcd of a and b is d for some nonzero d, 4 00:00:13,100 --> 00:00:13,633 5 00:00:13,633 --> 00:00:16,466 and if we have one solution to our 6 00:00:16,466 --> 00:00:17,100 7 00:00:17,100 --> 00:00:20,966 linear Diophantine equation 
a x plus b y equals c, 8 00:00:20,966 --> 00:00:24,900 then the complete integer 
solution is given by the following: 9 00:00:24,900 --> 00:00:27,766 so x equals x naught plus b over d n, 10 00:00:27,766 --> 00:00:30,666 and y equals y naught minus a over d n. 11 00:00:30,666 --> 00:00:33,266 12 00:00:33,266 --> 00:00:35,833 So what this is saying is, 13 00:00:35,833 --> 00:00:40,000 it's kind of like…it's like buy 
one get infinitely many free, 14 00:00:40,000 --> 00:00:43,466 right? So once you have one solution 
to a linear Diophantine equation, 15 00:00:43,466 --> 00:00:46,266 then you essentially have all of them, okay? 16 00:00:46,266 --> 00:00:50,066 At least when it's a binary 
linear Diophantine equation. 17 00:00:50,066 --> 00:00:52,433 18 00:00:52,433 --> 00:00:55,366 Alright so here notice that 19 00:00:55,366 --> 00:00:58,333 n is parameterized… 20 00:00:58,333 --> 00:01:00,166 it's a parameter. 21 00:01:00,166 --> 00:01:02,966 So the number of solutions 
here is infinite, right, 22 00:01:02,966 --> 00:01:05,600 it depends on this n and n can vary. 23 00:01:05,600 --> 00:01:08,233 So once you have one solution, 
you can find them all; 24 00:01:08,233 --> 00:01:10,566 that's the moral of this. 25 00:01:10,566 --> 00:01:14,166 So let's see an example of a 
linear Diophantine equation, 26 00:01:14,166 --> 00:01:16,833 and let's try to find a solution. 27 00:01:16,833 --> 00:01:20,600 By the way, to find the first solution, you 
can either use inspection, you can just 28 00:01:20,600 --> 00:01:23,166 find one and show that it works, 29 00:01:23,166 --> 00:01:25,833 or you can use the Extended 
Euclidean Algorithm. 30 00:01:25,833 --> 00:01:29,066 So I haven't done a video on the 
Extended Euclidean Algorithm yet, 31 00:01:29,066 --> 00:01:31,400 so I'm going to do one on one now. 32 00:01:31,400 --> 00:01:32,733 33 00:01:32,733 --> 00:01:35,933 So here is the sample that we have. 34 00:01:35,933 --> 00:01:38,333 Solve the linear Diophantine equation 35 00:01:38,333 --> 00:01:43,100 868x plus 465y equals 62. 36 00:01:43,100 --> 00:01:46,266 Now off the top of my head, I don't know 37 00:01:46,266 --> 00:01:49,700 if 868 and 465 have a common factor. 38 00:01:49,700 --> 00:01:52,400 It's possible, but I don't see one immediately. 39 00:01:52,400 --> 00:01:56,566 So sometimes if you see one immediately you 
can reduce the equation to make your life easier. 40 00:01:56,566 --> 00:01:58,833 I don't see one so I'm going to just 41 00:01:58,833 --> 00:02:01,700 plug through the Extended Euclidean Algorithm. 42 00:02:01,700 --> 00:02:04,000 Okay? So… 43 00:02:04,000 --> 00:02:08,400 44 00:02:08,400 --> 00:02:11,166 use EEA. 45 00:02:11,166 --> 00:02:13,466 So that's how we're 
going to start our proof, 46 00:02:13,466 --> 00:02:17,933 we are going to start by using 
the Extended Euclidean Algorithm. 47 00:02:17,933 --> 00:02:21,233 48 00:02:21,233 --> 00:02:23,266 Let's see what we have. 49 00:02:23,266 --> 00:02:24,300 50 00:02:24,300 --> 00:02:26,600 Okay, so let's set up our table. 51 00:02:26,600 --> 00:02:27,366 52 00:02:27,366 --> 00:02:30,100 So we're going to start with 
868 as our first remainder, 53 00:02:30,100 --> 00:02:31,900 465 as our second remainder, 54 00:02:31,900 --> 00:02:34,566 and we're going to start 
dividing these one at a time. 55 00:02:34,566 --> 00:02:37,966 So 465 goes into 868 one time. 56 00:02:37,966 --> 00:02:40,033 57 00:02:40,033 --> 00:02:44,000 So going to put 1 in 
our q in the third row. 58 00:02:44,000 --> 00:02:44,933 59 00:02:44,933 --> 00:02:48,333 Now we're going to subtract the first row 60 00:02:48,333 --> 00:02:50,566 minus 1 times the second row, 61 00:02:50,566 --> 00:02:53,500 and what's that going to give 
us? That's going to give us 62 00:02:53,500 --> 00:02:59,866 1 minus 1 and 868 minus 
465, that should be 403. 63 00:02:59,866 --> 00:03:01,300 64 00:03:01,300 --> 00:03:03,633 So let’s fill in that table. 65 00:03:03,633 --> 00:03:04,866 66 00:03:04,866 --> 00:03:11,233 And now we're going to repeat this, so now we’re 
going to do 403 into 465, that goes in again once. 67 00:03:11,233 --> 00:03:14,100 The difference there is 62, 68 00:03:14,100 --> 00:03:18,866 and again we're going to get a 2 
and so x is minus 1 and y is 2, right, 69 00:03:18,866 --> 00:03:21,400 so we're going to subtract 
second and the third row. 70 00:03:21,400 --> 00:03:22,433 71 00:03:22,433 --> 00:03:26,800 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. 72 00:03:26,800 --> 00:03:28,766 Here's where we get an interesting little case. So 73 00:03:28,766 --> 00:03:31,200 how many times does 62 go into 403? 74 00:03:31,200 --> 00:03:34,000 It's definitely at least 5 since 6 times 5 is 30, 75 00:03:34,000 --> 00:03:38,366 turns out it’ll go in 6 times, so we're going to put a 6 there. 76 00:03:38,366 --> 00:03:43,600 Now 6 times 62 that should be 372. 77 00:03:43,600 --> 00:03:46,700 403 minus 372 that's 31. 78 00:03:46,700 --> 00:03:47,566 403 minus 372 that's 31. 79 00:03:47,566 --> 00:03:51,033 Thankfully, the other two computations are a little easier. 80 00:03:51,033 --> 00:03:53,433 So let me save it just so that we can see it. 81 00:03:53,433 --> 00:03:54,866 82 00:03:54,866 --> 00:03:58,666 So 6 - so we’re taking row 
three minus 6 times row four. 83 00:03:58,666 --> 00:04:04,533 So minus 1 minus 6 times 2, that’s 12, so it's minus 13, 84 00:04:04,533 --> 00:04:06,566 and then the first one should be a 7. 85 00:04:06,566 --> 00:04:08,566 86 00:04:08,566 --> 00:04:10,900 Okay, that's it, and then now 87 00:04:10,900 --> 00:04:15,433 31 goes into 62 well that 
actually goes in exactly twice. 88 00:04:15,433 --> 00:04:17,200 So... 89 00:04:17,200 --> 00:04:17,966 90 00:04:17,966 --> 00:04:20,166 let me put one more 91 00:04:20,166 --> 00:04:26,166 row in this…twice and the remainder is 0, 92 00:04:26,166 --> 00:04:30,300 and I'm not going to do 
the x and y here because… 93 00:04:30,300 --> 00:04:33,566 what the hell, I'll do it. 28 and 94 00:04:33,566 --> 00:04:35,966 95 00:04:35,966 --> 00:04:39,466 negative 15, that should be right. 96 00:04:39,466 --> 00:04:43,733 It's actually small enough that we can do it. So 
let's extend our row by one more, there we go. 97 00:04:43,733 --> 00:04:44,466 98 00:04:44,466 --> 00:04:48,166 By the way, you should get down to 
0 in your table, okay, you need to 99 00:04:48,166 --> 00:04:52,000 show the marker that you know when to 
stop and you stop when the remainder is 0. 100 00:04:52,000 --> 00:04:53,000 101 00:04:53,000 --> 00:04:55,833 It's important for the computation side. 102 00:04:55,833 --> 00:04:57,100 103 00:04:57,100 --> 00:05:00,133 Just to know when you 
have to stop this algorithm. 104 00:05:00,133 --> 00:05:03,166 Okay that's great. So… 105 00:05:03,166 --> 00:05:04,866 106 00:05:04,866 --> 00:05:07,233 here we get a little bit lucky 107 00:05:07,233 --> 00:05:09,133 So we actually have a row with 62 in it. 108 00:05:09,133 --> 00:05:12,666 Let's suppose that we didn't though, for the sake of argument, 109 00:05:12,666 --> 00:05:15,766 or we didn't notice that we could just 
use this row to get our 62 equation, 110 00:05:15,766 --> 00:05:18,666 right? So let's go down to the 31. 111 00:05:18,666 --> 00:05:22,633 It's not going to always be this way, 
this just happened to work out. 112 00:05:22,633 --> 00:05:25,033 So what's our solution? So therefore, 113 00:05:25,033 --> 00:05:26,866 114 00:05:26,866 --> 00:05:30,266 what do we have? So 868 115 00:05:30,266 --> 00:05:33,533 times 7 plus 116 00:05:33,533 --> 00:05:36,633 465 times minus 13 117 00:05:36,633 --> 00:05:38,833 is equal to 31. 118 00:05:38,833 --> 00:05:40,700 By the way, 119 00:05:40,700 --> 00:05:41,800 120 00:05:41,800 --> 00:05:44,333 since this is a video and on an 
assignment things like this, 121 00:05:44,333 --> 00:05:47,833 you should be able to check 
that all of these rows are valid. 122 00:05:47,833 --> 00:05:50,266 Okay? There's no reason not to. 123 00:05:50,266 --> 00:05:52,566 On an exam, maybe it's a little tricky, but 124 00:05:52,566 --> 00:05:56,200 still it would be a good way 
to validate your work. 125 00:05:56,200 --> 00:05:59,666 Again, your notes refer to this 
as a certificate of correctness. 126 00:05:59,666 --> 00:06:00,466 127 00:06:00,466 --> 00:06:03,566 Okay great, so now that 
we have this solution here, 128 00:06:03,566 --> 00:06:07,066 to get to 62 well we know 
that 31 times 2 gives us 62. 129 00:06:07,066 --> 00:06:09,833 So we multiply this solution by 2… 130 00:06:09,833 --> 00:06:13,966 131 00:06:13,966 --> 00:06:18,333 and what are we going to get? 
We're going to get 868 times 14 132 00:06:18,333 --> 00:06:22,666 plus 465 times negative 26 is equal to 62. 133 00:06:22,666 --> 00:06:28,633 134 00:06:28,633 --> 00:06:32,000 There we have it. Alright, so we have our 135 00:06:32,000 --> 00:06:34,100 136 00:06:34,100 --> 00:06:37,066 solution here, 14 and minus 26. 137 00:06:37,066 --> 00:06:38,000 138 00:06:38,000 --> 00:06:41,166 So let’s… 139 00:06:41,166 --> 00:06:43,300 where to now? Okay, 140 00:06:43,300 --> 00:06:44,200 141 00:06:44,200 --> 00:06:45,833 so we have our solution 142 00:06:45,833 --> 00:06:49,133 now let's use LDET2. 
What does LDET2 say? 143 00:06:49,133 --> 00:06:54,266 Buy one, get infinitely many free. So 
we have our first solution, 14 minus 26, 144 00:06:54,266 --> 00:06:56,833 how do we get the rest 
of the solutions? So by 145 00:06:56,833 --> 00:06:59,633 LDET2, 146 00:06:59,633 --> 00:07:02,200 we have that 147 00:07:02,200 --> 00:07:03,566 148 00:07:03,566 --> 00:07:07,500 x is equal to 14 plus something 149 00:07:07,500 --> 00:07:10,166 150 00:07:10,166 --> 00:07:14,633 and y is equal to negative 
26 minus something. 151 00:07:14,633 --> 00:07:15,600 152 00:07:15,600 --> 00:07:15,800 153 00:07:15,800 --> 00:07:18,800 So how do I fill in the blanks here? 154 00:07:18,800 --> 00:07:20,500 So... 155 00:07:20,500 --> 00:07:21,066 156 00:07:21,066 --> 00:07:23,100 what do I do to get the 
blank? Well okay, so the 157 00:07:23,100 --> 00:07:27,333 14 belongs to the 868, right, so the idea is that I want to cancel out… 158 00:07:27,333 --> 00:07:29,200 159 00:07:29,200 --> 00:07:32,933 I want to add a term that 
will get cancelled out when I 160 00:07:32,933 --> 00:07:37,800 combine it with the 465. So if I 
just put 465 here, I'll get 868 161 00:07:37,800 --> 00:07:39,833 plus 465, and over here 162 00:07:39,833 --> 00:07:45,166 I would put 868 or negative 868, and I would 
get 465 minus 868, so those will cancel. 163 00:07:45,166 --> 00:07:46,033 164 00:07:46,033 --> 00:07:50,666 Now it turns out that that's the right idea 
but it's not going to give us the full solution. 165 00:07:50,666 --> 00:07:53,700 To get the full solution, you also 
need to account for the gcd. 166 00:07:53,700 --> 00:07:54,900 167 00:07:54,900 --> 00:07:59,600 And how does that work? So I'm going to 
take 465 and I'm going to divide it by 31, 168 00:07:59,600 --> 00:08:01,333 and then the other one 169 00:08:01,333 --> 00:08:02,200 170 00:08:02,200 --> 00:08:04,366 I'm going to take… 171 00:08:04,366 --> 00:08:07,766 172 00:08:07,766 --> 00:08:11,133 868 and I’m going to divide it 
by 31. Let's see what we get. 173 00:08:11,133 --> 00:08:16,233 174 00:08:16,233 --> 00:08:18,666 I need to multiply both by n. 175 00:08:18,666 --> 00:08:18,866 176 00:08:18,866 --> 00:08:19,000 177 00:08:19,000 --> 00:08:23,400 Now this will give us everything, okay, so when 
I take out the - why do I take out the 31? 178 00:08:23,400 --> 00:08:27,500 Well 868 and 465 each have 
31 as a common factor. 179 00:08:27,500 --> 00:08:31,700 So I want to - so if I divide out 
by that common factor, then 180 00:08:31,700 --> 00:08:34,433 I can still multiply those 
two things together and 181 00:08:34,433 --> 00:08:37,566 these two numbers together and 
get the cancellation that we want. 182 00:08:37,566 --> 00:08:39,533 The key is that these two things are integers 183 00:08:39,533 --> 00:08:43,133 and that's going to be the 
case because 31 was the gcd. 184 00:08:43,133 --> 00:08:48,000 So if I simplify this a little bit, 
I'm going to get 14 plus 185 00:08:48,000 --> 00:08:49,733 186 00:08:49,733 --> 00:08:54,966 465 divided by 31. I know because I 
made this example I know it's 15, 187 00:08:54,966 --> 00:08:55,866 188 00:08:55,866 --> 00:09:00,000 and on the other side 
it's minus 26 minus 28n. 189 00:09:00,000 --> 00:09:01,833 So let's 190 00:09:01,833 --> 00:09:03,866 see that. 191 00:09:03,866 --> 00:09:08,700 192 00:09:08,700 --> 00:09:11,266 And of course here, n is just some integer. 193 00:09:11,266 --> 00:09:15,700 194 00:09:15,700 --> 00:09:17,833 And that's perfect. By the 
way, so as an exercise, 195 00:09:17,833 --> 00:09:22,300 if you did start with minus 1 and 2 as your 
solution, you still get the same solution set. 196 00:09:22,300 --> 00:09:26,433 How do we see that? Well here if 
I plug in n equals minus 1, I get 197 00:09:26,433 --> 00:09:30,666 negative 1 for my x and if I plug 
in minus 1 here I get 2 for my y. 198 00:09:30,666 --> 00:09:33,066 So indeed I still get this solution 
and I'll get all the other ones, 199 00:09:33,066 --> 00:09:36,866 right, so if you want, you could...if 
you do it starting with this solution, 200 00:09:36,866 --> 00:09:38,566 might be a good exercise, see what you get 201 00:09:38,566 --> 00:09:41,466 and try to justify to yourself that you actually get the same answer. 202 00:09:41,466 --> 00:09:43,400 203 00:09:43,400 --> 00:09:46,700 And this gives us a complete 
set of solutions. So again this 204 00:09:46,700 --> 00:09:52,000 LDET2 is very powerful, right? Once you get 
one solution, you have all of the solutions 205 00:09:52,000 --> 00:09:55,133 by doing this simple little 
computation by taking the other term, 206 00:09:55,133 --> 00:09:58,166 dividing by 31, and then taking 
this term and dividing by 31. 207 00:09:58,166 --> 00:09:59,900 208 00:09:59,900 --> 00:10:03,000 Always double check your sign. 
It's a very easy thing to get wrong 209 00:10:03,000 --> 00:10:06,933 and it's a very easy thing to 
check, right? 868 times positive… 210 00:10:06,933 --> 00:10:10,066 let's do this one, times positive 15 211 00:10:10,066 --> 00:10:13,966 and you get positive 465 times negative 28, so 212 00:10:13,966 --> 00:10:16,866 at least the signs work, right? 
868 times 15 is positive, 213 00:10:16,866 --> 00:10:20,566 so we need 465 times negative 
28 to be negative, and it is. 214 00:10:20,566 --> 00:10:21,200 215 00:10:21,200 --> 00:10:24,033 So always do that last little check 
just to make sure that you can 216 00:10:24,033 --> 00:10:27,733 cancel out those extra n terms when you plug it in here. 217 00:10:27,733 --> 00:10:29,233 218 00:10:29,233 --> 00:10:32,600 And again, as an exercise, plug 
in this x into this equation 219 00:10:32,600 --> 00:10:36,866 and plug in this y to this equation 
and expand and see what happens. 220 00:10:36,866 --> 00:10:40,366 I'll leave that for you to do, I think 
it's worth doing, but I won't do it 221 00:10:40,366 --> 00:10:42,433 222 00:10:42,433 --> 00:10:46,200 because it's a little bit tough on the 
computer. It's just tough to type out, 223 00:10:46,200 --> 00:10:52,066 and the value is more when you actually do 
it than it is when you actually see me do it. 224 00:10:52,066 --> 00:10:54,800 Okay, so hopefully this helps you out, 225 00:10:54,800 --> 00:10:59,033 gives you a little bit of 
an idea of EEA and LDET2. 226 00:10:59,033 --> 00:11:00,866 227 00:11:00,866 --> 00:11:03,966 That's all I have to say, thank you very much.