Hello everybody. Welcome back. Today, we're going to be talking about computing greatest common divisors. So, in particular, what we'd like to do this lecture, is we're going to define the greatest common divisor problem. And, we're going to talk about an inefficient way to compute them. And, next lecture we'll talk about how to do better. So, okay. What are GCDs? So, suppose that you have a fraction, a over b. And, you want to put it in simplest form. Now, the standard way of doing this, is we want to divide the numerator and denominator both by some d, to get some equivalent fraction, a/d / b/d. Fair enough. Now, what d do we want to use for this? Well, it needs to satisfy two properties. Firstly, d had better divide both a and b, since the new numerator and denominator are both integers. But, subject to that, we would like this d to be as large as possible. So, that we can reduce the fraction as much as we possibly can. So, turning this into a definition, we say that for two integers, a and b, their greatest common divisor, or GCD, is the largest integer d that divides both a and b. Okay, so this is a thing that you use to reduce fractions. However, it turns out that GCDs are a critically important concept in the field of number theory. The study of prime numbers, and factorization, and things like that. And, because it's so important to number theory, it turns out that being able to compute GCDs is actually very important in cryptography. And, the fact that you can perform secure online banking is, in part, due to the fact that we can efficiently compute GCDs of numbers in order for our cryptographic algorithms to work. So, because of this importance, we're going to want to be able to compute GCDs. So, we'd like an algorithm that, given two integers, a and b, at say, at least 0, we can compute the GCD of a and b. And, just to be clear as to what kinds of inputs we care about, we'd actually like to be able to run this on very large numbers. We don't just want something that works for GCD of 5 and 12, or 11 and 73. We'd like to be able to do things like the GCD of 3,918,848 with 1,653,264. In fact, we'd also like to be able to compute much bigger numbers, 20, 50, 100, 1000 digits. We'd still like to be able to get GCDs of numbers of those sizes pretty quickly. Well, let's get started. Let's start by just finding an algorithm that works. What we'd like is the largest number that divides both a and b. So, one thing we can do, is we can just check all of the numbers that are candidates for this, figure out which ones divide a and b, and return the largest one. So, there's an easy implementation for this. We create a variable called best, and set it to 0. This just remembers the biggest thing we've seen so far. We then let d run from 1 to a + b, since this is the range of numbers that are valid. Now, if d divides a, and d divides b, well, since d is increasing, this has to be the new best that we've seen. So, we set best equal to d, and then, at the end the of the day, we return back the best thing we've seen. So, that's a perfectly good algorithm. It works. Unfortunately, it's a little bit slow, because we need to run through this for loop a + b many times. And, this means that, even once a and b are, say, 20 digit numbers, it's already going to be taking us at least thousands of years in order to run this computation. And, so that's not sufficient for the sorts of applications that we care about. We're going to need a better algorithm. So, come back next lecture, and we'll talk about how to find a better algorithm for this problem, and what goes into that.