1 00:00:00,000 --> 00:00:00,600 2 00:00:00,600 --> 00:00:03,300 We've talked a little bit throughout 
the rest of the week on 3 00:00:03,300 --> 00:00:05,066 Linear Diophantine Equations. 4 00:00:05,066 --> 00:00:05,433 5 00:00:05,433 --> 00:00:07,833 What’s the idea here? 
Well we want to solve 6 00:00:07,833 --> 00:00:10,700 equations of the form 
a x plus b y equals c, 7 00:00:10,700 --> 00:00:12,933 where a, b, and c are integers 8 00:00:12,933 --> 00:00:13,766 9 00:00:13,766 --> 00:00:16,000 but there's a catch, right, and the 
catch is that we don't just want 10 00:00:16,000 --> 00:00:17,666 to solve these for 
real numbers x and y, 11 00:00:17,666 --> 00:00:20,000 we want to solve these 
for integers x and y. 12 00:00:20,000 --> 00:00:20,566 13 00:00:20,566 --> 00:00:22,233 Now if you think about this, 14 00:00:22,233 --> 00:00:24,833 when x and y are real, we've 
actually already done this. 15 00:00:24,833 --> 00:00:26,800 Well by “we” I mean “you”, 16 00:00:26,800 --> 00:00:29,600 and also by “we” I mean 
“you did this in high school”. 17 00:00:29,600 --> 00:00:32,066 This is the equation of a line, so 18 00:00:32,066 --> 00:00:32,666 19 00:00:32,666 --> 00:00:36,233 solving these for real 
values is the same as 20 00:00:36,233 --> 00:00:38,833 solving for the equation of a line, 
right? So you have your slope, 21 00:00:38,833 --> 00:00:41,266 your negative a 
over b in this case, 22 00:00:41,266 --> 00:00:44,000 and you have your… 23 00:00:44,000 --> 00:00:47,133 what do you call this - your 
y-intercept value, your c over b, 24 00:00:47,133 --> 00:00:49,566 and you could find points, right? 25 00:00:49,566 --> 00:00:52,000 Once you find your…you have 
x’s, then you can find y’s, 26 00:00:52,000 --> 00:00:54,000 right, so the solution set 27 00:00:54,000 --> 00:00:56,766 over the reals gives you 
the equation of a line. 28 00:00:56,766 --> 00:00:59,066 Over the integers it gives 
you a subset of that line 29 00:00:59,066 --> 00:01:01,833 and it'll turn out as 
we'll see from LDET2, 30 00:01:01,833 --> 00:01:06,133 that the points on your line are equidistant 
from each other. They're equally spaced out, 31 00:01:06,133 --> 00:01:10,300 and they're spaced out by some 
factor depending on your slope. 32 00:01:10,300 --> 00:01:12,700 It's not exactly the 
slope minus a over b, 33 00:01:12,700 --> 00:01:15,400 but as you can see - as you 
will see - what will happen is 34 00:01:15,400 --> 00:01:17,366 you'll go a little bit 
over and a little bit up, 35 00:01:17,366 --> 00:01:19,333 or a little bit over 
and a little bit down, 36 00:01:19,333 --> 00:01:21,433 depending on the 
slope of your line, 37 00:01:21,433 --> 00:01:24,300 and you're going to create 
these new points that'll appear. 38 00:01:24,300 --> 00:01:26,533 39 00:01:26,533 --> 00:01:28,633 We'll see that in a minute, 
I'm getting ahead of myself. 40 00:01:28,633 --> 00:01:32,000 So two things we want to know when we're dealing with a Linear Diophantine Equation: 41 00:01:32,000 --> 00:01:34,666 one, does it have 
a solution at all? 42 00:01:34,666 --> 00:01:37,900 And two, what are all of the solutions 
to a Linear Diophantine Equation? 43 00:01:37,900 --> 00:01:38,933 44 00:01:38,933 --> 00:01:42,033 These are answered in two 
theorems: LDET1 and LDET2. 45 00:01:42,033 --> 00:01:43,933 So let's take a 
look at LDET1: 46 00:01:43,933 --> 00:01:46,100 “Let d be the gcd of a and b. 47 00:01:46,100 --> 00:01:48,433 The LDE ax plus b y equals c has a solution 48 00:01:48,433 --> 00:01:51,800 if and only if d divides c.” Okay? 
So a couple of things to note here. 49 00:01:51,800 --> 00:01:55,633 Whenever we write the letters LDE, we 
mean a Linear Diophantine Equation, 50 00:01:55,633 --> 00:01:59,600 so by those three letters we 
mean a, b, and c are integers, 51 00:01:59,600 --> 00:02:02,600 and we're looking for 
solutions x and y as integers. 52 00:02:02,600 --> 00:02:04,533 53 00:02:04,533 --> 00:02:06,633 So I've hidden the proof. This 
is something that you should 54 00:02:06,633 --> 00:02:08,133 probably pause the 
video and actually try. 55 00:02:08,133 --> 00:02:09,833 This proof isn't too hard. 56 00:02:09,833 --> 00:02:12,000 You should be able to 
write a proof of this. 57 00:02:12,000 --> 00:02:13,833 58 00:02:13,833 --> 00:02:16,000 So the LDE has a solution 59 00:02:16,000 --> 00:02:18,066 if and only if d divides c. 60 00:02:18,066 --> 00:02:22,133 This is an “if and only if” proof so we 
have to divide this into two components. 61 00:02:22,133 --> 00:02:24,833 Part 1 is assuming that the LDE has a solution, 62 00:02:24,833 --> 00:02:27,133 and part 2 is assuming 
that d divides c. 63 00:02:27,133 --> 00:02:28,066 64 00:02:28,066 --> 00:02:30,733 So let's go through the proof. 
Again, just rip it off like a band-aid. 65 00:02:30,733 --> 00:02:32,366 66 00:02:32,366 --> 00:02:36,366 So here we're going to assume 
that a x plus b y equals c, 67 00:02:36,366 --> 00:02:38,033 the LDE has an integer solution, 68 00:02:38,033 --> 00:02:40,266 and we're going to call it 
x naught and y naught. 69 00:02:40,266 --> 00:02:44,600 Since d divides a and d divides b, by DIC we have that d must divide the 70 00:02:44,600 --> 00:02:48,466 integer linear combination given 
by a x naught plus b y naught. 71 00:02:48,466 --> 00:02:52,200 But a x naught plus b y naught, that was 
just equal to c, so we have that d divides c. 72 00:02:52,200 --> 00:02:54,700 73 00:02:54,700 --> 00:02:56,366 And that's it in that direction. 74 00:02:56,366 --> 00:02:56,866 75 00:02:56,866 --> 00:03:00,000 So in the opposite direction, we're 
going to assume that d divides c. 76 00:03:00,000 --> 00:03:00,800 77 00:03:00,800 --> 00:03:04,000 What does that give us? Well that 
means that there exists an integer k 78 00:03:04,000 --> 00:03:08,000 such that d k equals c, right? That's 
what d dividing c means, okay? 79 00:03:08,000 --> 00:03:09,133 80 00:03:09,133 --> 00:03:11,733 So we have this and what 
does that mean? Well... 81 00:03:11,733 --> 00:03:14,200 doesn't look like it's helped us 
much, but we do have that we - 82 00:03:14,200 --> 00:03:17,400 well okay we've set the 
gcd of a and b to be d. 83 00:03:17,400 --> 00:03:20,166 So we can use some of our hammers 
and, in this case Bézout’s Lemma, 84 00:03:20,166 --> 00:03:23,333 or the Extended Euclidean
Algorithm, to get 85 00:03:23,333 --> 00:03:25,566 that there exists integers 
u and v such that 86 00:03:25,566 --> 00:03:28,500 a u plus b v is equal to the 
gcd of a and b and that's d. 87 00:03:28,500 --> 00:03:29,533 88 00:03:29,533 --> 00:03:32,100 So if you multiply this equation by what value? 89 00:03:32,100 --> 00:03:35,333 Well we want to get c on the right, 
so if we multiply everything by k, 90 00:03:35,333 --> 00:03:38,300 we're going to get d k over here and that's equal to c, 91 00:03:38,300 --> 00:03:40,800 and if we do this on the left, 
then we can just group 92 00:03:40,800 --> 00:03:42,966 the u and the k together and the 
v and the k together and we actually 93 00:03:42,966 --> 00:03:46,400 get a solution to our LDE 
given by u k and v k. 94 00:03:46,400 --> 00:03:48,000 So we use Bézout’s Lemma, 95 00:03:48,000 --> 00:03:50,400 and we use the definition of divisibility. 96 00:03:50,400 --> 00:03:51,100 97 00:03:51,100 --> 00:03:54,100 So notice that this also gives you 
a way to find a solution, right? 98 00:03:54,100 --> 00:03:57,333 The Extended Euclidean Algorithm 
can be used to find a solution 99 00:03:57,333 --> 00:03:58,900 of a Linear Diophantine Equation, 100 00:03:58,900 --> 00:04:01,733 and that's the good 
news about this proof 101 00:04:01,733 --> 00:04:04,333 is that it actually is constructive. 
You can actually find the u and v 102 00:04:04,333 --> 00:04:06,966 by using the Extended Euclidean 
Algorithm, which is pretty cool. 103 00:04:06,966 --> 00:04:08,566 104 00:04:08,566 --> 00:04:12,133 So now that we have a solution, or we now 
have a criteria for when we have a solution, 105 00:04:12,133 --> 00:04:15,466 and it's really strong, it’s an “if and 
only if”, it's necessary and sufficient, 106 00:04:15,466 --> 00:04:18,400 what do we do? So we have this really strong criteria, 107 00:04:18,400 --> 00:04:20,433 how can we find 
all of the solutions? 108 00:04:20,433 --> 00:04:21,266 109 00:04:21,266 --> 00:04:23,400 And that's given by LDET2... 110 00:04:23,400 --> 00:04:26,000 oh I put the proof on here 
I didn't mean to, that's okay. 111 00:04:26,000 --> 00:04:28,166 So LDET2, what does this say? 112 00:04:28,166 --> 00:04:31,733 “Let d be the gcd of a 
and b, where a and b 113 00:04:31,733 --> 00:04:35,400 are not 0…” this just 
eliminates silly cases, 114 00:04:35,400 --> 00:04:36,466 115 00:04:36,466 --> 00:04:39,300 “…if x and y is equal 
to x naught, y naught 116 00:04:39,300 --> 00:04:42,833 is a solution to our LDE 
a x plus b y equals c, 117 00:04:42,833 --> 00:04:46,300 then all solutions are 
given by the following set. 118 00:04:46,300 --> 00:04:48,733 So the set is a set of ordered pairs, 119 00:04:48,733 --> 00:04:52,433 and the ordered pairs are of the form 
x naught plus b over d, times n, 120 00:04:52,433 --> 00:04:56,100 and y naught minus a 
over d, times n, okay? 121 00:04:56,100 --> 00:05:01,300 So as n ranges over all the integers, this 
gives you an infinite pairing of integers, 122 00:05:01,300 --> 00:05:04,400 and it's formed by this pairing. 123 00:05:04,400 --> 00:05:05,733 124 00:05:05,733 --> 00:05:07,833 Think back to that line analogy, right? 125 00:05:07,833 --> 00:05:10,600 So what we're doing essentially 
is we're taking some x naught 126 00:05:10,600 --> 00:05:12,466 and we're incrementing it by some 127 00:05:12,466 --> 00:05:14,666 b over d multiples of n, 128 00:05:14,666 --> 00:05:17,466 and...so that's going, I 
guess, in the x-direction 129 00:05:17,466 --> 00:05:19,600 instead of going up, I'm just 
going to go in the x direction, 130 00:05:19,600 --> 00:05:23,133 and in the y direction, every time we 
go over 1 we're going to go down 131 00:05:23,133 --> 00:05:25,200 by an a over d times n, 
so we're going to go 132 00:05:25,200 --> 00:05:26,833 over and down, over and down, 
over and down, over and down, 133 00:05:26,833 --> 00:05:28,866 and that's going to 
give us a line like this. 134 00:05:28,866 --> 00:05:30,500 This of course assumes that a and b are positive. 135 00:05:30,500 --> 00:05:33,233 If a and b are negative, the slope 
of the line is going to change. 136 00:05:33,233 --> 00:05:35,533 It's not a huge deal, 
but it will change the 137 00:05:35,533 --> 00:05:37,700 little picture that I'm drawing with my hands. 138 00:05:37,700 --> 00:05:39,400 But that's the main idea. 139 00:05:39,400 --> 00:05:41,266 140 00:05:41,266 --> 00:05:43,233 So the proof. 141 00:05:43,233 --> 00:05:45,600 So one thing we 
have to note is that 142 00:05:45,600 --> 00:05:46,333 143 00:05:46,333 --> 00:05:48,533 we really need - well okay there's 
two things we need to show: 144 00:05:48,533 --> 00:05:53,166 first we have to show that all of these are actually 
integer solutions to the Linear Diophantine Equation, 145 00:05:53,166 --> 00:05:55,466 that's easy. Just 
plug it in and check. 146 00:05:55,466 --> 00:05:57,933 What's going to happen? You're 
going to get your a b over d times n, 147 00:05:57,933 --> 00:06:00,466 and you're going to get your negative a b over d times n. 148 00:06:00,466 --> 00:06:01,633 So those two terms will cancel, 149 00:06:01,633 --> 00:06:05,200 and the x naught y naught we've already 
started [with as] a solution to the LDE, right? 150 00:06:05,200 --> 00:06:06,766 151 00:06:06,766 --> 00:06:10,333 So notice that because we have a solution, we 
know that the gcd of a and b does divide c. 152 00:06:10,333 --> 00:06:13,533 Turns out not to be useful for this proof, 
but that’s something to think about. 153 00:06:13,533 --> 00:06:15,000 154 00:06:15,000 --> 00:06:16,900 So now in the other direction, what do we need to show? 155 00:06:16,900 --> 00:06:19,766 We need to show that all 
solutions can written in this form. 156 00:06:19,766 --> 00:06:22,400 So how are we going to start? We're 
going to start with another solution 157 00:06:22,400 --> 00:06:26,600 some new x and y as a different solution to our LDE. 158 00:06:26,600 --> 00:06:29,666 Well what does that mean? Well we have these two equations, a x plus b y equals c 159 00:06:29,666 --> 00:06:32,600 and x naught plus 
b y naught equals c. 160 00:06:32,600 --> 00:06:35,633 So if you look at these two equations, 
we notice there's a lot of similarities, 161 00:06:35,633 --> 00:06:37,466 and one way to get rid 
of them is to cancel the c. 162 00:06:37,466 --> 00:06:40,400 So let's subtract 
the two equations, 163 00:06:40,400 --> 00:06:42,500 and what does that give 
us? It gives us a times 164 00:06:42,500 --> 00:06:45,766 x minus x naught is equal to 
negative b times y minus y naught, 165 00:06:45,766 --> 00:06:47,300 after a little bit of rearranging. 166 00:06:47,300 --> 00:06:48,566 167 00:06:48,566 --> 00:06:50,933 And now what we'd like to do is we'd like to say something along lines of, 168 00:06:50,933 --> 00:06:53,000 “Well a must divide 
y minus y naught,” 169 00:06:53,000 --> 00:06:54,966 but of course that's not true. 170 00:06:54,966 --> 00:06:59,000 And why isn't that true? Well it's not true 
because a and b could have common divisors, 171 00:06:59,000 --> 00:07:00,000 172 00:07:00,000 --> 00:07:03,600 and that could be a problem. So what we 
can do is we can actually divide out by d, 173 00:07:03,600 --> 00:07:06,933 which is the gcd, of a and 
b. So if we divide out by d, 174 00:07:06,933 --> 00:07:09,466 what do we get? Well now we 
get that the gcd of a and d 175 00:07:09,466 --> 00:07:13,366 and the gcd of minus b and d, or 
the gcd of b and d, either way, 176 00:07:13,366 --> 00:07:16,200 that's equal to 1, and that's by DBGCD, right? 177 00:07:16,200 --> 00:07:19,533 If we divide by the gcd, then 
these two things are co-prime. 178 00:07:19,533 --> 00:07:21,833 Remember co-prime 
means that their gcd is 1. 179 00:07:21,833 --> 00:07:23,366 180 00:07:23,366 --> 00:07:25,866 So now looking at this, 
and now since we have… 181 00:07:25,866 --> 00:07:28,533 I'm going to go the other way, so instead 
of saying a divides y minus y naught, 182 00:07:28,533 --> 00:07:31,433 I’m actually going to go 
b divides x minus x naught. 183 00:07:31,433 --> 00:07:36,000 So now let's look at b over d. 
So b over d divides this thing: 184 00:07:36,000 --> 00:07:39,666 negative b over d 
times y minus y naught, 185 00:07:39,666 --> 00:07:41,366 and that thing is equal to 186 00:07:41,366 --> 00:07:42,166 187 00:07:42,166 --> 00:07:44,300 a over d times x minus x naught. 188 00:07:44,300 --> 00:07:45,100 189 00:07:45,100 --> 00:07:49,166 So by Coprimeness and Divisibility, b over d divides x minus x naught. 190 00:07:49,166 --> 00:07:50,333 191 00:07:50,333 --> 00:07:53,000 Again, b over d and a 
over d are co-prime, 192 00:07:53,000 --> 00:07:57,066 and b over d divides the product of two 
things, so it must divide the other thing, 193 00:07:57,066 --> 00:07:58,833 which is x minus x naught. 194 00:07:58,833 --> 00:08:01,266 Thus there exists an 
integer n such that 195 00:08:01,266 --> 00:08:03,833 x is equal to x naught plus b over d n, 196 00:08:03,833 --> 00:08:06,200 that's just by definition 
and rearrangement. 197 00:08:06,200 --> 00:08:08,000 198 00:08:08,000 --> 00:08:10,800 Now, at this point, something 
to mention here, right, 199 00:08:10,800 --> 00:08:12,900 is that you kind of want to argue… 200 00:08:12,900 --> 00:08:17,466 you want to say, “Well similarly 
y minus y naught is equal to 201 00:08:17,466 --> 00:08:20,266 a over d times n,” right? 202 00:08:20,266 --> 00:08:22,866 But the thing that's not clear is it's not clear why the n here 203 00:08:22,866 --> 00:08:26,000 had to be the same as 
the n when I do this with a. 204 00:08:26,000 --> 00:08:29,533 So you actually can't quite do the same…
you can't do the exact same argument, 205 00:08:29,533 --> 00:08:32,200 what you can actually do 
is use this information 206 00:08:32,200 --> 00:08:36,466 that x minus x naught is equal 
to b over d in this equation here, 207 00:08:36,466 --> 00:08:39,500 to actually show that a over d 208 00:08:39,500 --> 00:08:44,000 times n, or negative a over d times 
n, is equal to y minus y naught, 209 00:08:44,000 --> 00:08:46,666 and that's what you have to do. 
So instead of arguing similarly, 210 00:08:46,666 --> 00:08:50,166 just actually use this information, 
substitute it in, and then simplify. 211 00:08:50,166 --> 00:08:52,000 And that's going to 
complete your proof. 212 00:08:52,000 --> 00:08:53,233 213 00:08:53,233 --> 00:08:56,000 So again summary of LDET2. 214 00:08:56,000 --> 00:08:58,366 Once you have one solution, 
you have them all, 215 00:08:58,366 --> 00:09:01,666 and you can find them by 
looking at multiples… or by 216 00:09:01,666 --> 00:09:04,000 multiples as follows. So take x naught and add 217 00:09:04,000 --> 00:09:07,566 b over d times n to it, and take y 
naught and subtract a over d times n. 218 00:09:07,566 --> 00:09:09,966 So one solution gives 
you all the solutions. 219 00:09:09,966 --> 00:09:12,466 This is a pretty cool feature of LDET, right? 220 00:09:12,466 --> 00:09:15,300 If you think about like quadratic 
equations and cubic equations, 221 00:09:15,300 --> 00:09:19,466 just because you have one solution to a 
quadratic equation or a cubic equation equals 0 222 00:09:19,466 --> 00:09:22,566 doesn't mean that you get both solutions. 
Sometimes there's more work to be done. 223 00:09:22,566 --> 00:09:24,433 Specifically in the cubic 
case. The quadratic case 224 00:09:24,433 --> 00:09:26,600 maybe you can argue that I can find the other one. 225 00:09:26,600 --> 00:09:29,300 But here you just get 
them all for free basically. 226 00:09:29,300 --> 00:09:32,200 You don't have to do any other work. 
Once you have one you have them all. 227 00:09:32,200 --> 00:09:33,366 228 00:09:33,366 --> 00:09:34,900 Let's see an example. 229 00:09:34,900 --> 00:09:35,533 230 00:09:35,533 --> 00:09:38,533 Solve the LDE 20x plus 35y equals 15. 231 00:09:38,533 --> 00:09:41,733 So again pause the video at this point. 
Hopefully you've paused it a couple of times, 232 00:09:41,733 --> 00:09:44,166 and hopefully you’ve paused this 
video in general. It's a very long video 233 00:09:44,166 --> 00:09:46,533 so hopefully you're taking 
breaks while watching it. 234 00:09:46,533 --> 00:09:48,366 Pause the video, try this out. 235 00:09:48,366 --> 00:09:52,000 Physically try to see if you can solve 
this Linear Diophantine Equation. 236 00:09:52,000 --> 00:09:53,033 237 00:09:53,033 --> 00:09:54,833 Hopefully you've come back now. 238 00:09:54,833 --> 00:09:57,000 So let's try to do 
this together, okay? 239 00:09:57,000 --> 00:10:01,333 So the first thing that I notice here 
is that I have 20, 35, and 15. 240 00:10:01,333 --> 00:10:03,900 I can actually prime factor 
these very quickly in my head. 241 00:10:03,900 --> 00:10:07,200 4 times 5, 7 times 
5, and 3 times 5, 242 00:10:07,200 --> 00:10:12,433 and I quickly see oh well 5 is a 
prime factor of all of these things, 243 00:10:12,433 --> 00:10:16,166 and it's the largest common 
factor of all these things. 244 00:10:16,166 --> 00:10:19,000 So I can do that and I can 
divide everything by 5. 245 00:10:19,000 --> 00:10:19,866 246 00:10:19,866 --> 00:10:21,833 What's that going to give me? 
Well it's going to give me 247 00:10:21,833 --> 00:10:23,866 4x plus 7y equals 3. 248 00:10:23,866 --> 00:10:26,133 So now when I 
have this equation, 249 00:10:26,133 --> 00:10:27,033 250 00:10:27,033 --> 00:10:30,466 you have options, right? If you don't see 
a solution immediately, you can use 251 00:10:30,466 --> 00:10:33,066 the Extended Euclidean 
Algorithm to find a solution. 252 00:10:33,066 --> 00:10:36,000 There's no problem with that, right, 
we know that the gcd of 4 and 7 is 1, 253 00:10:36,000 --> 00:10:38,700 so LDET1 will tell us that we will have a solution here. 254 00:10:38,700 --> 00:10:41,333 Just like LDET1 told us 
before, right? If I divide by 5, 255 00:10:41,333 --> 00:10:44,000 it doesn't change whether 
or not I have a solution. 256 00:10:44,000 --> 00:10:45,466 257 00:10:45,466 --> 00:10:47,500 So that's excellent, so now 
I know I have a solution. 258 00:10:47,500 --> 00:10:50,433 So now I just have to find a 
solution. Well how do I find one? 259 00:10:50,433 --> 00:10:52,033 Here I can just do 
it by inspection. 260 00:10:52,033 --> 00:10:54,466 7 minus 4 I quickly 
notice is 3, 261 00:10:54,466 --> 00:10:57,433 so if I make x equals minus 1 
and y equals 1, I get a solution. 262 00:10:57,433 --> 00:11:00,800 Again if you don't see it, run through the 
Extended Euclidean Algorithm. It’ll take 263 00:11:00,800 --> 00:11:04,400 a couple of seconds, but it's 
better than not finding a solution. 264 00:11:04,400 --> 00:11:08,000 If you don't find one in 10 seconds, just 
run through the algorithm, it's okay. 265 00:11:08,000 --> 00:11:11,266 So define all solutions 
we invoke LDET2, 266 00:11:11,266 --> 00:11:13,933 Linear Diophantine 
Equation Theorem 2, 267 00:11:13,933 --> 00:11:16,533 and how do we find all 
solutions? Well we have one, 268 00:11:16,533 --> 00:11:19,000 to find all the rest 
of them just take 269 00:11:19,000 --> 00:11:21,700 x is equal to x naught plus 270 00:11:21,700 --> 00:11:24,300 b over d, so in this case, 7 over the 271 00:11:24,300 --> 00:11:27,133 gcd of 4 and 7, times n, 272 00:11:27,133 --> 00:11:30,766 and y is equal to the solution 
that we found, y naught 273 00:11:30,766 --> 00:11:32,966 minus a over d, times n. 274 00:11:32,966 --> 00:11:36,000 So here a and b are both positive, so that's nice, 275 00:11:36,000 --> 00:11:37,233 276 00:11:37,233 --> 00:11:40,866 and here the gcd 4 and 7 is actually 
1. Why am I writing it like this? 277 00:11:40,866 --> 00:11:43,033 I'm writing it like this just to emphasize that 278 00:11:43,033 --> 00:11:46,066 if you didn't find the gcd, 
you should make sure that 279 00:11:46,066 --> 00:11:48,600 divide by it when you're 
invoking LDET2. 280 00:11:48,600 --> 00:11:52,200 And here n is any integer, 
okay, so that's another 281 00:11:52,200 --> 00:11:56,266 big thing to note, right? Quantify your variables when you're using them. 282 00:11:56,266 --> 00:12:00,400 So here, n is an arbitrary integer, 
and x and y is our solution 283 00:12:00,400 --> 00:12:02,333 to this Diophantine Equation. 284 00:12:02,333 --> 00:12:03,500 285 00:12:03,500 --> 00:12:05,933 Notice that this is equivalent 
to the solution set: 286 00:12:05,933 --> 00:12:10,400 x equals minus 1, minus 7, over 
the gcd of 4 and 7 times n, 287 00:12:10,400 --> 00:12:13,466 and y is equal to 1 plus 4 over the gcd of 4 and 7 times n. 288 00:12:13,466 --> 00:12:16,000 So notice here that I 
flipped the signs here. 289 00:12:16,000 --> 00:12:17,766 Why is that okay? So 290 00:12:17,766 --> 00:12:20,500 the reason why this is okay, it's just a technical thing, 291 00:12:20,500 --> 00:12:21,433 292 00:12:21,433 --> 00:12:23,866 but it's not hard to understand 
so let's try to understand this. 293 00:12:23,866 --> 00:12:27,633 As n varies over all integers, 294 00:12:27,633 --> 00:12:30,800 n is going to take on 
positive and negative values. 295 00:12:30,800 --> 00:12:34,400 So in this solution set when 
I make n equal to 1, I get 296 00:12:34,400 --> 00:12:38,000 negative 1 plus 7, 
and I get 1 minus 4. 297 00:12:38,000 --> 00:12:40,000 Well if I make n 
equals to 1 down here, 298 00:12:40,000 --> 00:12:44,300 I don't get the same solutions, but if I 
make n equal to minus 1 what do I get? 299 00:12:44,300 --> 00:12:49,266 I get minus 1, minus 7 times 
negative 1, so that's minus 1 plus 7, 300 00:12:49,266 --> 00:12:51,566 oh that's the same solution that I had up here. 301 00:12:51,566 --> 00:12:53,333 And if I do that over here, I'm going to get 302 00:12:53,333 --> 00:12:55,533 1 plus 4 times negative 1, 303 00:12:55,533 --> 00:12:59,800 so 1 minus 4, oh that's the same solution 
I had over here when I plugged in n equals 1. 304 00:12:59,800 --> 00:13:03,500 So really what you're doing is a change of 
variables. You're sending n to negative n, 305 00:13:03,500 --> 00:13:05,933 and you're substituting in 
negative n instead of n. 306 00:13:05,933 --> 00:13:08,600 That doesn't matter because 
they're just arbitrary integers, 307 00:13:08,600 --> 00:13:11,500 and if n is an arbitrary 
integer, then negative n - so 308 00:13:11,500 --> 00:13:13,266 as n ranges over the integers, 309 00:13:13,266 --> 00:13:16,000 then negative n also ranges 
over the integers, right? 310 00:13:16,000 --> 00:13:17,633 1 corresponds to minus 1, 311 00:13:17,633 --> 00:13:19,333 negative 5 corresponds to 5 312 00:13:19,333 --> 00:13:21,933 and so on and so forth, right, 
there's this matching that occurs. 313 00:13:21,933 --> 00:13:24,500 So there's multiple ways to write the solution set. Don't let 314 00:13:24,500 --> 00:13:28,000 the flipping of the signs 
bother you too much. 315 00:13:28,000 --> 00:13:29,700 That's all I want to say about that.