In this video we are going to further extend the Euclid's algorithm for computing the greatest common divisor. Let's start with the following motivational question. So imagine that somebody computed the greatest common divisor of two integers a and b, and now would like to convince us that it is equal to d. So, how can this be done? First of all, we can of course check that d divides a and b. This will convince us that d is indeed a common divisor of a and b but this gives us no information whether it is the greatest or not, right? Because it's still not excluded that there exists a larger number than d that divides both a and b. It turns out, however, that to convince us that d is the greatest divider of a and b, it is enough to represent it. And in the form ax plus by, where x and y are integers, okay let's prove it. Assume that d divides a and b and assume that d is equal to ax plus by where x and y are integers. Then necessarily d is equal to the greatest common divisor of a and b. So in a sense, x and y in this case is a certificate of the fact that d is the greatest common divisor of and b. So let's prove this theorem. So first of all since d divides a and b, it is a common divisor of a and b. And since GCD of a, b is the greatest such common divisor, it implies that d is at most GCD of a and b. Once again, this is just because d is some common divisor of a and b and GCD of a and b is the greatest common divisor. So some divisor is definitely at most the greatest common divisor. Okay, on the other hand, so GCD of a and b is some common divisor of a and b. But this means, in fact, that it should divide d. So why is that? So GCD of a, b divides a and b. It means that it also divides a times x and b times y. And it also divides the sum of them. So we conclude that gcd of a, b divides d. But this, in turn, means that GCD of a and b is at most d because no number larger than d can divide d. So all in all we conclude that the d is equal to GCD of a, b. Once again, this is just because we've just proved that d is at most the greatest common divisor of a and b. And at the same time the greatest common divisor of a and b is at most d. So these two numbers are equal, okay? So this is nice and let me illustrate this with a couple of examples. So the great common divisor of 10 and 6 is equal to 2. And this you can see here it indeed can be represented as a linear combination of 10 and 6. Namely, if you multiply 10 by -1 and if you multiply 6 by 2s and then you compute the sum, you get exactly 2. So this says, -10 plus 12, it gives us 2. So the greatest common divisor of 7 and 5 is equal to 1. And it can be represented as 7 times -5, times -2, I'm sorry, which gives us -14 plus 5 times 3, which is 15, so -14 plus 15 is equal to 1, which is the greatest common divisor of 7 and 5. So two more examples which are not so easy to compute by hand here on the fly. But still, so the greatest common divisor of 239 and 299 is equal to 23. And it can be checked so it can be also represented as a linear combination so the numbers 391 and 299, okay? Okay, now let's try to extend the Euclid's algorithm so that besides of computing the greatest common divisor itself, it also gives us a certificate. And by certificate I mean these two numbers, x and y. So first of all recall that the Euclid's algorithm that we discovered in the previous video does the following. To compute the greatest common divisor of a and b it actually makes a recursive call for computing the greatest common divisor of b and the remainder of a divided by b. So this happens when a is at least b, okay? So assume that we've just made such a recursive call, and it actually returned us not only the greatest common divisor d itself. But also representation of this greatest common divisor of the linear combination of the parameters. And by parameters here I mean these two parameters b and a mod b, so the remainder of a divided by b. I assume that we know that its representation, the representation of d is a linear combination of these two parameters. Namely, that d is equal to bp plus a mod b times q. So p and q is a certificate in this case. So now what we would like to do is to transform this certificate into a certificate of the pair a and b, okay? So for this we need a little bit of calculations. Okay, so we know that d is equal to b times p plus a mod b times q. First of all, let's do the following, let's rewrite a mod b using just a and b. So just by definition a mod b is a remainder of a when divided by b. So this means that when we subtract enough copies of b, so what is left is some number which is smaller than b, okay? So this is, for this we need to subtract from a some number of copies of b. Okay, and this is exactly, so a divided by b is an integer part of a divided by b is exactly what we get when we divide a by b, okay? So this is a number of copies that we subtract. So a mod b is equal to a minus a divided by b. So in the integer part of it divide and multiply by b. Okay, so when we rewrite it like this, we can now regroup all the terms. So what we see is that from here we get a times q and this is exactly what we see here and. To get the multiplier for b what we get is that this is b times p plus b, this b times a divided by b by q. And this gives us the following expressions. So this is a new certificate for a and b. So to get d we need to multiply a by q and we need to multiply b by this expression, okay? And this can be implemented as an algorithm which is known as an extended Euclid's algorithm. So let's go through this code line by line once again. So again we assume in this case that a is at least b, that the first parameter is always at least the second one. It is convenient in this case. So b is at least 0 and not both of them are equal to 0. So first of all, if b is equal to 0. So if smaller number's equal to 0 then we return the result immediately. So, in this case d the greatest common divisor is equal to a, to the larger number, right? And the certificate x and y are equal to just 1 and 0, right. So x and y are equal to 1 and 0. So why is that? So recall that in this case, b is equal to 0. So where and d is equal to a. So a is represented as a times 1 plus was b times 0, which is clearly correct. So d is equal to a, so this is our greatest common divisor and we represented this as a linear combination of a and b, so this is x, this is y. So in this case, the output is clearly direct. In the opposite case, when b is greater than 0, we make a recursive call. Recall that in this case, we swap the parameters. So our first parameter is b, our second parameter is the remainder of a divided by b. This is just because we want our first parameter to be larger than the second one. So we make this recursive call and it gives us the greatest common divisor, and also a certificate b, q. And using the formula from the previous slide, we can view the new certificate. So x is just equal to q and y is equal to b minus q times a divided by b. And here we use this integer division. So this a divided by b gives us just exactly what we get, exactly an integer number a divided by b, okay? So this is y. So before we turn in the result, we check that d divides a, d divides b, and that d represents, d can be represented by ax plus by. So in the end we return the result d, x, y. So as you see, just a simple extension of the original Euclid's algorithm allows us to produce not only the greatest common divisor, but also the certificate of this greatest common divisor. And we will use this essentially in the next part to compute inverses modular n, which we discussed already is an essential part of modern integrated protocols.
