Hello, everybody. Welcome to the module devoted to the Euclid's Algorithm. This is an efficient algorithm for computing the greatest common divisor of two integers, A and B. So just by definition, the greatest common divisor of A and B, where A and B at any integers that are not both equal to zero, is the largest number that divides both A and B. So, any numbers that divides both A and B is called a common divisor of A and B. So the greatest common divisor is the largest such number. For example, gdc(24,16) = 8. So it is not difficult to check that 8 divides both these numbers, and that any larger number does not divide at least one of them. For example, 16 divides 16 of course, but does not divides 24. Another example, gdc(9,17) = 1. So in a sense, 9 and 17 do not share any non-trivial common divisors, okay? So why do I say non- trivial? Well, this is just because 1 divides any integer numbers. So any two integer numbers have 1 as a common divisor, okay? So the last example is that, gdc(239, 0) = 239 itself. This is just because no larger number can divide 239 on one hand. And on the other hand, it definitely divides zero, just because any non-zero number divides zero, okay? So, the last remark about this definition is that, in this definition with low A and B to be any numbers positive or negative, with the only requirement that they are not both equal to zero. On the other hand, throughout the lecture, we will assume that both A and B are non-negative. We can do this without lost of generality just because if you have a number A, which is positive, and the number minus A, which negative, they have the same set of divisors, okay? So, if you have a negative number A, you can as well consider the number minus A, which is positive, and define a common divisor of this number with some other number, okay? Okay. So before we proceed to the algorithm for computing the greatest common divisor, let me provide you with the motivation. So first of all, it turns out that computing the greatest common divisor of two integers is that an essential operation for computing inverses modulo N. Namely, assume that we're given two numbers, A and N, and what we would like to do is to find the integer K, such that A times K is congruent to 1 modulo N. Or put it otherwise, A times K minus 1 is divisible by N. In this case, K is called an inverse of A modulo N, okay? So this is an essential operation of many modern cryptographic protocols that are used billions of times per day. For example, when we purchase something over the web, okay? And we would like this separation to be computed efficiently. And for this, it is important to have an algorithm for computing the greatest common divisor of two numbers efficiently. We will learn these a little bit later, okay? Another application is the formula. Assumes that we are going to work with rational numbers, and we would like to perform some basic operations with such numbers. For example, to compute the sum of two such fractions. What do you see here on this slide is that point example. So to compute the sum of these two numbers, we're going to do the following. So with that, multiply the first fraction, I mean the bottom part and the top part with 59, and we'll multiply the second fraction with 177. Then, they have the common bottom part, and we can write the sum as follows. Then, we compute the number of top and the number of bottom, and what we get, the following number. So two large numbers. But it turns out that they do have a large common divisor, and we can cancel that out. So what remains is actually 2/3. So, using greatest common divisors, we can simplify fractions. And this is exactly what happens, for example, in the fraction library in Python. So, if you run these four lines of code in Python, then what you get is exactly 2/3 as an output. So, the Python actually always finds the greatest common divisor of the top number at the bottom number for any fraction, and then cancel it out. And it is done very quickly, and we will soon learn how to compute the greatest common divisor quickly. But before preceding to the efficient algorithm, let's just check the most naive algorithm is efficient or not. And by saying the most naive algorithm, I mean the following. So, we are looking for the greatest common divisor. Let's just go through all potential candidates, and let's select the greatest common divisor, okay? So, this can be implemented as follows. So let's build together check this code line by line. So in the first line, we actually check that A is non-negative, and B is non-negative, and A + B > 0. This actually ensures that not both of them are equal to zero, okay? Then, if at least one of them is equal to zero, then we just return the other number, okay? In this case, nothing needs to be done so we just return the maximum of them. We are sure that this is exactly the greatest common divisor. Then what we do in the next four loop, is the following. So we have to positive numbers at this point. So we know that the greatest common divisor cannot be larger than the minimum of them. So what we're going to do with the following, we go from minimum of A and B, we go down to one, one by one. And for any number, we check whether it divides both A and B. If it does, then we stop immediately and we return this number. This is exactly what is happening here. So we go in the ranges from the minimum of A and B, step by step, I mean, one by one down to, this minus one is responsible to the fact that, at each iteration, we're increasing D by one, and we go till we reach one actually. And then, for each such D, we check whether it divides both A and B. And if it does, we return D immediately. So, in a sense, this return statement will never be executed in this code. Okay. So if we run, for example, gcd(24,16), it will return 8 immediately. So, you can try it on your laptop. Let's now analyze the result in algorithm. So first of all, what we can notice is that if the greatest common divisor of A and B = 1, then our algorithm will be forced to check all the possibilities, all the numbers from the minimum of A and B till 1, okay? It will try all possibilities till it reaches 1. And in this point, it will realize that is the greatest common divisor is equal to 1 and it will return it, okay? So now, to check whether it is efficient enough or not, let's recall that our modern laptops perform roughly 1 billion operations per second. I'm not going to specify what is in that operation, what is the basic operation. And also this is a very rough estimate, but at the same time, it is a pretty accurate estimate. So the problem is, in this case, if you can key that these two numbers, if you run this code on your laptop, it will definitely take more than one minute. And this is just because this number is a much larger than 10 to the 9. So this are actually roughly hundred billions or something, okay? So, it will take more than one minute even for such short numbers. And when an algorithm or when some operation on our computer takes more than one second, we become mad immediately, right? So when we purchase something on the web, we would like to press the button, and we would like our operation to be processed immediately so we don't want to wait even for more than one second, right? So this is not an efficient algorithm, unfortunately. So even if we have a supercomputer to process such an operation, it will not be able to run this algorithm in less than one second, not to say more. If A and B say, 100 digits long. So to be more precise, if you run that algorithm for A and B that are 100 digits long, even in a supercomputers that perform, it's not just one billion, but one quadrillion operations per second, like millions and billions operations per second. Then it will take these computer more than 100 years to find the greatest common divisor of such two numbers, which are not that big, actually. So there are just 100 digits long. So this is not just gigabytes or terabytes of data, this are just 100 digits. And our algorithm will not be able to compute the greatest common divisor even in the supercomputer. So we definitely need a more efficient algorithm. And this is what we're going to consider in the next part. So we will present to discover the Euclid's algorithm, which works much faster than our Naive algorithm.
