Hello everyone. Welcome to week 6 of Carmen's Core Concepts.
My name is Carmen Bruni,
and this week, or in these video series, we'll be going through the videos
for Math 135 week by week.
These are meant to be like a review session,
a supplement to going to lectures and other
good forms of mathematical practice.
In the end, nothing can compare to actually doing problems
and practicing these concepts by yourself, preferably without your notes.
Just pencil and paper and trying to recall what you remember from the week
and how everything fits in together.
This is the midway point of Math 135, which is fantastic if you made it this far.
So without further ado, let’s begin.
So the first thing we want to talk about is the Extended Euclidean Algorithm
So the basic idea behind the Extended Euclidean Algorithm
is that it gives you a fast way to compute
the gcd of a and b and integers x and y such that
we've written the gcd as a linear integer combination of a and b.
That's the basis of it so,
just as a quick example, we can try...
the following:
“Find x and y integers such that 506 times x, plus 391 times y
is equal to the gcd of 506 and 391.
So if you haven’t… well so, pause the video at this point,
and try this problem out.
You should be able to do this. If you
don't know the Extended Euclidean Algorithm you obviously can't do this, but
if you do know it, pause the video and give it a try, okay?
Hopefully you've come back now.
So let's see how to do this. I'm not going to do this step by step,
I'm just going to kind of rip it off like a band-aid.
So here in our table, we have our headings x, y, r, q.
r for remainder and q for quotient.
We set up our first two rows as follows: we have 1, 0, and 506,
notice that 506 is the bigger of 506 and 391,
and we have 0, 1, and 391.
And here the first two quotients don't matter, you can leave them blank or put a 0, that's fine.
Now to compute the quotient in every subsequent row,
what we do is we take the previous two terms,
the previous two remainder terms, and divide them,
and then take the floor of that,
and that gives us 1, and then we take 391 and 115 that gives us 3.
We take 115 and 46, that gives us 2.
We take 46 and 23 and that gives us 2.
Remember the floor is the
greatest integer less than or equal to the integer in here,
so the floor of 1.5, let's say, is 1.
All these are positive numbers,
so you don't have to worry about any negative weird cases happening.
And then how do we figure out the x and y columns after this?
So here we have the quotient of 1, and what we do with the quotient of 1
is we're going to take the previous row, and subtract
q copies of the next row.
So in this case, we're going to take the first row and subtract 1 copy of the second row.
So 1 minus 0 is 1,
0 minus 1 is negative 1,
and then we do the next one.
The next quotient is 3, so we're going to take
0 minus 3, times 1, so that's negative 3.
1 minus 3 times negative 1, that's 4.
And then we do it again,
right, with 2. So
1 minus 2, times negative 3, that's 7.
Negative 1 minus 2, times 4, that's negative 9.
The last one doesn't matter, I did it but once you have the last non-zero remainder,
in this case 23,
we know that the greatest common divisor between the two starting numbers,
506 and 391 is 23.
And we've determined our x and y
it's 506 times 7, plus 391 times negative 9.
So now
you can go through this algorithm and
do it and that's actually really… it's not too hard. It's pretty easy.
The thing that's maybe a little difficult is actually understanding
why this algorithm computes what you want it to do.
And if you think back to the Euclidean Algorithm, right,
and think back to GCD With Remainders,
what happening here is that these first two r values are your a and your b,
and what you're doing is you're computing the q and r
from the division algorithm,
and then saying, well the gcd of 506 and 391 is the same as
the gcd of 391 and 115.
Now once you've done that, instead of 506 being your a, you make 391 being your a,
and then instead of 391 being your b, you make 115 be your b,
and then again you're going to compute the same remainder.
So as you can kind of hopefully see based on that description,
we keep doing this and repeating this and it's going to give us all of the
quotients from before and the remainders from before. So
clearly the gcd is going to be okay,
and by following along with these x and y values,
you can actually trace through it and compute the x and y values
as you're going along, as opposed to doing back substitution.
If you want to see an example of like really
explicitly where these come from, these equations,
check out the lecture notes
on the Extended Euclidean Algorithm.
So that's all I want to say about this for now.
This is very useful too - I guess I should also mention
this is called… so I liked to…
as a theorem it's called Bézout’s Lemma, the fact that these integers exist.
The notes call them the Extended Euclidean Algorithm, either way is fine.
That’s the first point I have here.
Notice that in the previous example,
a was bigger than b,
so if you're doing this with b bigger than a, then what
you can do is you can just swap a and b, that's not a big concern.
You might have to swap the roles of x and y in your table, that's okay,
and if a is less than 0 or b is less than 0, then
what you can do is you can just make all the terms positive.
So make the a and the b positive and we don't really care
because the gcd of a and b is equal to the gcd of the absolute value of
a and the absolute value b.
So in practice,
one can often do these things by actually changing the headings
in the EEA table and going from there.
So an example can be found in the lecture notes and…
actually I'm going to go back for a second.
So you can find examples again in the lecture notes,
but going back…
so for example if this was 506x - 391y,
what I would do is instead of having a y here, I would put a negative y,
and then just run through the algorithm as normal
and just remember that in the end, I got a negative
y value over here. So
here I would need a negative sign out here, and I would have a negative sign…
well in here I would just copy whatever's in here.
And that's what you would do. So again
examples of this can be found in the notes. If you’d like some shortcuts
for dealing with plus and minus signs and dealing with the
sizes of these two values flipped.