1 00:00:00,000 --> 00:00:03,066 Hello everyone. Welcome to week 
6 of Carmen's Core Concepts. 2 00:00:03,066 --> 00:00:04,600 My name is Carmen Bruni, 3 00:00:04,600 --> 00:00:08,133 and this week, or in these video series, 
we'll be going through the videos 4 00:00:08,133 --> 00:00:10,266 for Math 135 week by week. 5 00:00:10,266 --> 00:00:12,233 These are meant to be 
like a review session, 6 00:00:12,233 --> 00:00:14,833 a supplement to going 
to lectures and other 7 00:00:14,833 --> 00:00:17,133 good forms of 
mathematical practice. 8 00:00:17,133 --> 00:00:20,400 In the end, nothing can compare to actually doing problems 9 00:00:20,400 --> 00:00:24,533 and practicing these concepts by 
yourself, preferably without your notes. 10 00:00:24,533 --> 00:00:27,733 Just pencil and paper and trying to recall what you remember from the week 11 00:00:27,733 --> 00:00:30,233 and how everything 
fits in together. 12 00:00:30,233 --> 00:00:34,633 This is the midway point of Math 135, 
which is fantastic if you made it this far. 13 00:00:34,633 --> 00:00:35,466 14 00:00:35,466 --> 00:00:37,833 So without further 
ado, let’s begin. 15 00:00:37,833 --> 00:00:41,100 So the first thing we want to talk about 
is the Extended Euclidean Algorithm 16 00:00:41,100 --> 00:00:43,733 So the basic idea behind the Extended Euclidean Algorithm 17 00:00:43,733 --> 00:00:45,833 is that it gives you a 
fast way to compute 18 00:00:45,833 --> 00:00:49,033 the gcd of a and b and 
integers x and y such that 19 00:00:49,033 --> 00:00:52,366 we've written the gcd as a linear integer combination of a and b. 20 00:00:52,366 --> 00:00:53,600 21 00:00:53,600 --> 00:00:55,200 That's the basis of it so, 22 00:00:55,200 --> 00:00:57,833 just as a quick 
example, we can try... 23 00:00:57,833 --> 00:00:58,433 24 00:00:58,433 --> 00:00:59,566 the following: 25 00:00:59,566 --> 00:01:05,600 “Find x and y integers such that 
506 times x, plus 391 times y 26 00:01:05,600 --> 00:01:09,600 is equal to the gcd 
of 506 and 391. 27 00:01:09,600 --> 00:01:13,733 So if you haven’t… well so, 
pause the video at this point, 28 00:01:13,733 --> 00:01:16,166 and try this problem out. 29 00:01:16,166 --> 00:01:17,833 You should be able 
to do this. If you 30 00:01:17,833 --> 00:01:21,200 don't know the Extended Euclidean 
Algorithm you obviously can't do this, but 31 00:01:21,200 --> 00:01:23,833 if you do know it, pause the 
video and give it a try, okay? 32 00:01:23,833 --> 00:01:24,433 33 00:01:24,433 --> 00:01:26,433 Hopefully you've come back now. 34 00:01:26,433 --> 00:01:29,833 So let's see how to do this. I'm 
not going to do this step by step, 35 00:01:29,833 --> 00:01:31,766 I'm just going to kind of 
rip it off like a band-aid. 36 00:01:31,766 --> 00:01:32,800 37 00:01:32,800 --> 00:01:35,933 So here in our table, we 
have our headings x, y, r, q. 38 00:01:35,933 --> 00:01:37,833 r for remainder 
and q for quotient. 39 00:01:37,833 --> 00:01:38,300 40 00:01:38,300 --> 00:01:42,200 We set up our first two rows as 
follows: we have 1, 0, and 506, 41 00:01:42,200 --> 00:01:45,833 notice that 506 is the 
bigger of 506 and 391, 42 00:01:45,833 --> 00:01:48,366 and we have 
0, 1, and 391. 43 00:01:48,366 --> 00:01:49,166 44 00:01:49,166 --> 00:01:52,766 And here the first two quotients don't matter, you 
can leave them blank or put a 0, that's fine. 45 00:01:52,766 --> 00:01:53,700 46 00:01:53,700 --> 00:01:56,833 Now to compute the quotient 
in every subsequent row, 47 00:01:56,833 --> 00:01:58,866 what we do is we take 
the previous two terms, 48 00:01:58,866 --> 00:02:00,900 the previous two remainder 
terms, and divide them, 49 00:02:00,900 --> 00:02:02,666 and then take 
the floor of that, 50 00:02:02,666 --> 00:02:06,400 and that gives us 1, and then we 
take 391 and 115 that gives us 3. 51 00:02:06,400 --> 00:02:09,633 We take 115 and 
46, that gives us 2. 52 00:02:09,633 --> 00:02:11,733 We take 46 and 23 
and that gives us 2. 53 00:02:11,733 --> 00:02:12,533 54 00:02:12,533 --> 00:02:14,333 Remember the floor is the 55 00:02:14,333 --> 00:02:17,233 greatest integer less than or 
equal to the integer in here, 56 00:02:17,233 --> 00:02:20,166 so the floor of 1.5, 
let's say, is 1. 57 00:02:20,166 --> 00:02:21,466 58 00:02:21,466 --> 00:02:23,500 All these are positive numbers, 59 00:02:23,500 --> 00:02:26,500 so you don't have to worry about any 
negative weird cases happening. 60 00:02:26,500 --> 00:02:28,900 And then how do we figure out the x and y columns after this? 61 00:02:28,900 --> 00:02:32,400 So here we have the quotient of 1, 
and what we do with the quotient of 1 62 00:02:32,400 --> 00:02:35,366 is we're going to take the 
previous row, and subtract 63 00:02:35,366 --> 00:02:37,700 q copies of the next row. 64 00:02:37,700 --> 00:02:38,166 65 00:02:38,166 --> 00:02:41,600 So in this case, we're going to take the 
first row and subtract 1 copy of the second row. 66 00:02:41,600 --> 00:02:43,400 So 1 minus 0 is 1, 67 00:02:43,400 --> 00:02:46,000 0 minus 1 is negative 1, 68 00:02:46,000 --> 00:02:47,566 and then we do the next one. 69 00:02:47,566 --> 00:02:48,166 70 00:02:48,166 --> 00:02:50,766 The next quotient is 3, 
so we're going to take 71 00:02:50,766 --> 00:02:51,200 72 00:02:51,200 --> 00:02:55,133 0 minus 3, times 1, 
so that's negative 3. 73 00:02:55,133 --> 00:02:59,000 1 minus 3 times 
negative 1, that's 4. 74 00:02:59,000 --> 00:03:00,533 And then we do it again, 75 00:03:00,533 --> 00:03:02,066 right, with 2. So 76 00:03:02,066 --> 00:03:05,833 1 minus 2, times 
negative 3, that's 7. 77 00:03:05,833 --> 00:03:09,500 Negative 1 minus 2, 
times 4, that's negative 9. 78 00:03:09,500 --> 00:03:10,133 79 00:03:10,133 --> 00:03:15,000 The last one doesn't matter, I did it but once 
you have the last non-zero remainder, 80 00:03:15,000 --> 00:03:16,400 in this case 23, 81 00:03:16,400 --> 00:03:19,166 we know that the greatest common divisor between the two starting numbers, 82 00:03:19,166 --> 00:03:21,566 506 and 391 is 23. 83 00:03:21,566 --> 00:03:23,133 And we've determined our x and y 84 00:03:23,133 --> 00:03:26,200 it's 506 times 7, plus 
391 times negative 9. 85 00:03:26,200 --> 00:03:27,300 86 00:03:27,300 --> 00:03:29,100 So now 87 00:03:29,100 --> 00:03:31,233 you can go through this algorithm and 88 00:03:31,233 --> 00:03:32,233 89 00:03:32,233 --> 00:03:35,900 do it and that's actually really…
it's not too hard. It's pretty easy. 90 00:03:35,900 --> 00:03:38,000 The thing that's maybe a little 
difficult is actually understanding 91 00:03:38,000 --> 00:03:40,433 why this algorithm computes 
what you want it to do. 92 00:03:40,433 --> 00:03:43,166 And if you think back to the 
Euclidean Algorithm, right, 93 00:03:43,166 --> 00:03:45,833 and think back to GCD With Remainders, 94 00:03:45,833 --> 00:03:50,066 what happening here is that these first 
two r values are your a and your b, 95 00:03:50,066 --> 00:03:53,100 and what you're doing is 
you're computing the q and r 96 00:03:53,100 --> 00:03:54,333 from the division algorithm, 97 00:03:54,333 --> 00:03:57,833 and then saying, well the gcd of 
506 and 391 is the same as 98 00:03:57,833 --> 00:04:00,200 the gcd of 391 and 115. 99 00:04:00,200 --> 00:04:04,900 Now once you've done that, instead of 506 
being your a, you make 391 being your a, 100 00:04:04,900 --> 00:04:08,600 and then instead of 391 being 
your b, you make 115 be your b, 101 00:04:08,600 --> 00:04:10,766 and then again you're going to 
compute the same remainder. 102 00:04:10,766 --> 00:04:14,533 So as you can kind of hopefully 
see based on that description, 103 00:04:14,533 --> 00:04:18,166 we keep doing this and repeating this 
and it's going to give us all of the 104 00:04:18,166 --> 00:04:20,466 quotients from before and the 
remainders from before. So 105 00:04:20,466 --> 00:04:22,466 clearly the gcd is going to be okay, 106 00:04:22,466 --> 00:04:25,600 and by following along 
with these x and y values, 107 00:04:25,600 --> 00:04:29,200 you can actually trace through it 
and compute the x and y values 108 00:04:29,200 --> 00:04:31,866 as you're going along, as opposed 
to doing back substitution. 109 00:04:31,866 --> 00:04:33,500 110 00:04:33,500 --> 00:04:35,666 If you want to see an example of like really 111 00:04:35,666 --> 00:04:37,833 explicitly where these come 
from, these equations, 112 00:04:37,833 --> 00:04:39,733 check out the lecture notes 113 00:04:39,733 --> 00:04:41,833 on the Extended Euclidean Algorithm. 114 00:04:41,833 --> 00:04:42,800 115 00:04:42,800 --> 00:04:44,900 So that's all I want to say about this for now. 116 00:04:44,900 --> 00:04:45,966 117 00:04:45,966 --> 00:04:48,333 This is very useful too - I 
guess I should also mention 118 00:04:48,333 --> 00:04:50,633 this is called… so I liked to… 119 00:04:50,633 --> 00:04:54,366 as a theorem it's called Bézout’s Lemma, the fact that these integers exist. 120 00:04:54,366 --> 00:04:55,300 121 00:04:55,300 --> 00:04:59,066 The notes call them the Extended 
Euclidean Algorithm, either way is fine. 122 00:04:59,066 --> 00:05:00,900 That’s the first point I have here. 123 00:05:00,900 --> 00:05:03,366 Notice that in the 
previous example, 124 00:05:03,366 --> 00:05:04,933 a was bigger than b, 125 00:05:04,933 --> 00:05:05,500 126 00:05:05,500 --> 00:05:08,066 so if you're doing this with b 
bigger than a, then what 127 00:05:08,066 --> 00:05:10,933 you can do is you can just swap 
a and b, that's not a big concern. 128 00:05:10,933 --> 00:05:11,700 129 00:05:11,700 --> 00:05:15,400 You might have to swap the roles of x and y in your table, that's okay, 130 00:05:15,400 --> 00:05:18,400 and if a is less than 0 
or b is less than 0, then 131 00:05:18,400 --> 00:05:21,100 what you can do is you can just make all the terms positive. 132 00:05:21,100 --> 00:05:23,733 So make the a and the b positive 
and we don't really care 133 00:05:23,733 --> 00:05:26,966 because the gcd of a and b is equal to the gcd of the absolute value of 134 00:05:26,966 --> 00:05:28,766 a and the absolute value b. 135 00:05:28,766 --> 00:05:29,566 136 00:05:29,566 --> 00:05:31,566 So in practice, 137 00:05:31,566 --> 00:05:35,200 one can often do these things by 
actually changing the headings 138 00:05:35,200 --> 00:05:38,366 in the EEA table and 
going from there. 139 00:05:38,366 --> 00:05:40,833 So an example can be found 
in the lecture notes and… 140 00:05:40,833 --> 00:05:42,166 actually I'm going to 
go back for a second. 141 00:05:42,166 --> 00:05:44,533 So you can find examples 
again in the lecture notes, 142 00:05:44,533 --> 00:05:45,966 but going back… 143 00:05:45,966 --> 00:05:50,500 so for example if this 
was 506x - 391y, 144 00:05:50,500 --> 00:05:53,833 what I would do is instead of having 
a y here, I would put a negative y, 145 00:05:53,833 --> 00:05:55,833 and then just run through 
the algorithm as normal 146 00:05:55,833 --> 00:05:58,366 and just remember that 
in the end, I got a negative 147 00:05:58,366 --> 00:05:59,800 y value over here. So 148 00:05:59,800 --> 00:06:02,833 here I would need a negative sign out 
here, and I would have a negative sign… 149 00:06:02,833 --> 00:06:04,966 well in here I would just 
copy whatever's in here. 150 00:06:04,966 --> 00:06:06,500 151 00:06:06,500 --> 00:06:08,066 And that's what you 
would do. So again 152 00:06:08,066 --> 00:06:11,066 examples of this can be found in the 
notes. If you’d like some shortcuts 153 00:06:11,066 --> 00:06:13,833 for dealing with plus and minus 
signs and dealing with the 154 00:06:13,833 --> 00:06:16,233 sizes of these two values flipped.