Hello everyone. So in this video,
we're going to talk about the Euclidean Algorithm and back substitution.
The problem that I have in mind is: "Find the gcd of 65 and 40 and find integers
x and y such that 65x plus 40y is equal to the gcd of 65 and 40."
Alright, so
how do we do this? Well the idea's, again, use
repeated applications of the Division Algorithm
to get a list of equations,
for lack of a better word,
where each time you're reducing the gcd, step by step. Okay?
So I think it's probably just best to actually do an example. So...
We first divide 65 by 40.
40 goes into 65 once, and the remainder is 25.
In line two, we're going to get...
that - we're going to move the 40 down, so 40
is equal to 25 and 25 goes into 40 how many times? Once,
plus 15.
Let's do it again now. 25
is equal to 15
plus 10. So again 15 goes into 25 once - so a lot of these go in once -
15, 10 once plus 5.
And then 10...
5 goes into 10 twice plus 0.
So here we are so let's look at...
So here are the equations 65 equals 40 plus 25,
then you divide 25 into 40 that goes in once, with a remainder 15,
then you divide 15 into 25 that goes in once with remainder 10,
then you divide 10 into 15 that goes in once, with remainder 5,
and you do it one more time with remainder 0.
The Euclidean Algorithm says the gcd is the last non-zero remainder,
which is therefore 5, so thus
the
greatest common divisor
of 65 and 40 is 5.
To find
the integers x and y, we use back substitution.
We're going to start with the last
equation here, so...
the last non-zero remainder equation so we're going to say 5 is equal to
15 plus 10 times minus 1.
Okay so I'm going to take
the 5, which is the 15 plus 10 times minus 1, right?
If I bring it over, it's going to be minus 10 and I'm just going to put the minus 10 inside with the 1.
And now I'm going to do the same thing with the equation 3.
So I'm going to say 10 is equal to 25 plus 15 times minus 1,
and I'm going to replace that 10.
15 plus 25
plus 15 minus 1,
minus 1.
If I simplify...
let's display it first... so again,
by number 3, I get 10 is equal to 25 plus 15 times minus 1.
It's exactly what I have here. By the way, this makes sense. Again you can check it, right?
25 minus 15 is 10, so it's okay.
Bring the negative 1 into everything,
so it's going to give me 25 times minus 1,
plus I have one 15 here, negative 1 times negative 1 is 1,
so I get one more 15, so 15 times 2.
Again, sanity check: 15 times 2 is 30, minus 25 is 5, still good.
Do the same thing now with 15 from equation 2. So 15 is
40 plus 25 times minus 1.
So now we've replaced 15 by the 40 plus 25 times minus 1,
and now we're multiplying by 2,
right, because that was the 2 from down there. So take him over here, and this 15 changed to 40 plus
25 times minus 1.
Again, sanity check: 40 minus 25 is 15, it's still good.
We expand it out so I'm going to get
40 times 2, that's the bigger one, so I'm going to put it first.
You don't have to, it's just a matter of preference.
Now I have minus 1 times 2, so it's negative two 25's
another minus 1 so that's going to give me
minus 3 25's.
Sanity check: 40 times 2 is 80, 25 times minus 3 is 75,
80 minus 75
is 5, still good.
Now let's use the last one.
So 25 is equal to 65 plus 40 times minus 1.
Alright, now I've used all those equations, just one last
distributive property.
So minus 3 times minus 1 is 3,
3 plus 2 so there's 5 there,
and there's minus 3 65's.
Alright, so one last sanity check here:
so, 65 times
minus 3 that should be negative 195,
40 times 5 is 200, 200 minus 195, that's going to be 5. Okay?
So integers that work are x equals minus 3, so...
so integers satisfying the original equation
are x equals minus 3 and y equals 5.
You should always write a concluding sentence like this, right, make sure you actually answer the question.
Well that's great. So there's a solution that gives you the gcd of 5.
This part is called back substitution, and the first part is called the Euclidean Algorithm.
Key takeaways from this: the Euclidean Algorithm
states that when you repeatedly apply the Division Algorithm,
the last non-zero remainder is the gcd,
and the back substitution part says
you can write down the gcd as a linear combination
of the two terms you're taking the gcd of. This is sometimes called Bézout's
Lemma or Bézout's Identity
depends on what you read.
So...
that solves that problem,
and...
I think that's all I want to say. I don't think I have anything else to say about this.
So hopefully, this example gives you an idea of how to
approach this if you saw it on an exam or on an assignment,
and I hope this has been enlightening.
Thank you very much for your time and good luck.