We now consider applications of the Euclid's algorithm, I'm sorry, for computing the greatest common divisor. Our first application is computing the least common multiple of two integers efficiently. By definition, the least common multiple of two integers, a and b, which are not both equal to zero, is the smallest integer which is divisible by both a and b. For example, the least common multiple of 24 and 16 is equal to 48. The least common multiple of 9 and 17 is equal to 153, which is just the product of 9 and 17, which is of course divisible by both, 9 and 17. On the other hand, the least common multiple of 200, 39, and 0, is undefined, because we cannot divide by 0, okay? Again, as with the greatest common divisor, we will assume that both a and b are unknown negative integers because if some number is divisible by a, then it is also divisible by -a of course. Okay? So, one of the common application of the least common multiple is working with fractions once again. So, consider the following toy example. It seems that we would like to compute the sum of the following two fractions, so 31 divided by 177, and 29 divided by 118. So, first of all we would like to turn this to fractions to have the common denominator. And for this, it is enough to find the last common multiple because we would like to find some small number. Of course, one possibility is just to multiply two denominators, but we can do much better. Namely, we can find the least common multiple of 177 and 118. In this case, it is equal to 354, and it is actually equal to 2 times 177, or 3 times 118. This allows us to rewrite these two fractions as follows, it is equal to 31 x 2 / 177 x 2 + 29 x 3 / 118 x 3. And this allows us finally to compute this sum. Which, finally, gives us a result. And once again, using the least common multiple instead of just the product of denominators allows us to keep the numbers involved in these computations small enough, okay? So, first of all, for computing the least common multiple, we again just iterate through all possible potential candidates, starting from one to a times b. So we just move from numbers from one to a times b and check whether the current number is divisible by a and b simultaneously, even if it is divisible, we return immediately least number, right? So this gives us the following code. In this for loop, once again, we just start with 1 and we go from 1 to a times b. And if d is divisible by a and d is divisible by b, we return d immediately. So in the worst case, we will return a times b. But if we are lucky, then we will find some smaller number. So as this is a small example, if we run it on the numbers 24 and 16, it will give us 48 as expected. So in the worst case, we will perform a times b checks. And this has bad enough for numbers like this, for example if we have a number with six decimal digits, and another number with six decimal digits. And if you run this algorithm then it will take on your laptop definitely more than one minute. And this is something that we actually hate. So the question is how can we apply the Euclid's algorithm for computing the greatest common divisor, for computing the least common multiple. You have probably guessed, of course, that we can do this and in fact, the formula is simple enough. So it turns out that for any two numbers a and b, is the product of the least common multiple of a and b and the greatest common divisor between a and b is equal to the product of a and b. So this immediately gives us an efficient algorithm for computing the least common multiple. Namely, for computing the least common multiple, we just compute the greatest common divisor of a and b, and then we divide a times b by the greatest common divisor. So this gives us the least common multiple. So the only remaining thing is to prove this formula. So let's do this. Assume that we are given two non-negative integers a and b. Then what we would like to prove is that the lcm (a, b) = ab / gcd(a,b), okay? So, let's prove it. Denote by d as usual the greatest common divisor of a and b, and assume that a = db, and b = dq, where p and q are integers, okay? So we know that p and q are integers, just because d divides a and b, okay? Then, first of all, we notice that m = ab /d, is again is indeed in multiple of a and b. So why is that? Well, just because a times b is equal to dp times dq. So if we divided by d, so on one hand it is equal to, we can cancel these p, this will give us p times dq, and this is equal to p times b, right? Because dq = pb. I'm sorry, dq is equal to b. On the other hand, instead of cancelling this d, we can cancel this d. This will give us dp times q and this is equal to a times, a times q, right because dp is equal to a. Okay, so we know that m defined as follows is indeed a multiple of a and b. So what we now need to prove is that, this is the smallest touch multiple. So to prove that this is indeed the smallest one, let's assume the country. Assume that there is some other smaller multiple of a and b. We know this by m bar. Then we can define d bar as follows. It is ab / m bar. So we know that this an integer just because m bar is a multiple of a and b. And we also know that this is greater than d, right? Just because m bar is smaller than b. And we know that d actually is equal to ab / m. Since m bar is smaller than m, where dividing by a smaller number. This means that d bar is greater than d and also, it is not difficult to check that d bar divides a and b, just because a / d bar = m bar divided by b, and b / d bar = m bar / a. And both this number is integers just because m bar is, just by our assumption, is a multiple of a and b. So this contradicts the fact that d is the largest common divisor of a and b. And this finally proves our lemma.