Euclid's Algorithm - Numberphile

Key Takeaways

So today we're going to talk about Uklid's algorithm. Um so give me two numbers Brady. Two three-digit numbers. Let's say >> three-digit numbers. >> 484 >> 484 >> 781 >> 781. So we're going to find the greatest common divisor of these two numbers. Um so that's going to be the largest number that divides both 484 and 781. >> Oh, I didn't give you a prime, did I? >> I don't know yet. We'll find out. Um 484 is definitely not prime. Um because 484 is 22. Um so we could actually already find out the greatest common divisor that way. But I'm going to show you this algorithm. And this algorithm I was actually taught probably about 10 years ago um by Vicky Neil who has been on your podcast the late great Vicky Neil. So it's very fun for me to be able to share this today. So the largest factor of both 484 and 781. So, we're going to start with 781 because it's the bigger. And that equals 1 * 484 with a remainder of And now I'm going to have to do this math in my head. We've got seven here, nine there, and two. >> That's just one, subtract the other, is it? >> Yeah, exactly. So, this is the first step of our algorithm. What we do for the next step is we're going to take this number and move it all the way to here. So, we'll take 484 and put it here. And then we take 297, put it here. And how many times does 297 go into 484? Well, that's also once, but this time it's with a remainder of 187. Okay, so now we repeat. 297 goes here. 187 goes here. And again, this is one. And that's a remainder. This one's easy. 110. And we keep going and hope we don't run out of paper. Plus 77. 110 = 1 * 77 + 33. 77 = 2 * 33. >> Out last >> + 11. Okay. 33 then equals 3 * 11 with no remainder. So, we stop here. >> That's the stop point when you've got no remainder. >> Stop point when we've got no remainder. And I've got to thank you now, Brady, for picking a number that takes the length of the paper. Couldn't have done it better. >> Is it Is it not normally you wouldn't have expected it to take that long? >> I have done some that take longer. I have done some that are done in two steps. Um, it can really depend. Um, and I can't reiterate more, we did not prepare this. So, >> this tells us this last remainder term is our greatest common divisor. >> The 11. the 11 obviously in maths often we want to know is that actually true I can tell you it's true all I like um but is it really and we can we can test this how do we know 11 is the greatest common divisor well there are two things we want to know we want to know that it is a divisor and we want to know that any divisor of 484 and 781 is at most 11 so there's not one greater so to tell it's a divisor is actually kind of okay because we see from this bottom line. 11 is a divisor of 11. 1 * 11 is 11. 11 divides 11. And this bottom line tells us that 11 divides 33. Obviously, we did already know that. But if we if we didn't and had more complicated numbers, this bottom line can tell us that. So, we've got 11 divides 33, which means that 11 divides all of this side of the equation. So, it's got to divide this side of the equation as well. So, 11 divides 77. Okay. 11 divides 33 and 77. So it divides all of this side of the equation. So it has to divide all of that side of the equation. And we can keep going up, which tells us that then 11 divides well from here all of this side of the equation. So it's got to divide 484. It divides all of this side of the equation. So it's got to divide 781. So 11 does divide 484 and 781. We know it is a common divisor. And that's a check in that box. Okay. So, is it the greatest common divisor? Well, um, let's have a look. The greatest common divisor is going to divide 781 and 484. So, any number that divides 781 and 484 has to divide 297. So, if it divides this and this, it's going to have to divide this for this equation to work. And then we can go down. It divides this and this. So, it has to divide this, this, this. So going all the way down any divisor of 484 and 781 has to divide 11. So 11 has to be the greatest one. So 11 is the greatest common divisor. And we can do this more generally as well. We can do this with any two numbers. And now I am going to get a second bit of paper. >> Can I just say I'm really impressed by the numbers I chose. Yeah, I really they were great numbers to get um something that eight has a few steps that look nice and ends in not one because if you got co-prime numbers it'll end in one which looks great but looks kind of like maybe they all end in one but no these were actually really helpful numbers. >> I know I had no idea what was coming either. I'm really pleased with myself. >> I I am very very happy with that one as well. So now there's another trick to this and we can use it to go backwards. So if we now start at the bottom, we can rearrange this equation to make 11 equals Okay. Well, it's going to be 77 minus 2 * 33. >> So you've rearranged >> So I've rearranged this equation. >> Yeah. >> So I want to change the 33 now. So I'm going to rearrange this equation. So I'll keep the 77 as it is. But rather than having minus 2 * 33 going to have minus and then in brackets well 33 is 110 minus 77. So I've just replace here the 33 by what we find from this equation by rearranging. And then we can collect like terms. So this becomes 3 * 77us 2 * 110. And if you were to work that out, you would find that 3 * 77 is 231 and 2 * 110 is 220. So this does work out as 11. Great. Now we're going to replace the 77 using the next equation up. So here 77 is 187 - 110. So 3 * 187 - 110 minus 2 * 110. Okay. So 3 * 110 here. Add 2 * 110. So, this is - 5 * 110. And we're going to keep going. And this will probably now be sped up because it's going to be a whole bunch of repeated calculations. And then final step, we're going to replace the 297. So this becomes 8 * 484 minus 13 * 781 take 484 which is 21 * 484 minus 13 * 781. Okay, so we have now reversed Uklid's algorithm and we've got our greatest common divisor as the sum of two multiples of our two original numbers, >> right? >> And we can always do this. So if the greatest common divisor of say we've got a and b as our numbers and let's say their greatest common divisor, which we often write as this brackets, I'm going to call this d. Using this algorithm, we can always find u and v integers such that u a plus vb equals d. Now notice I deliberately said integers. They can be negative as we've got here. But for any a and b we can always find u and v such that the sum of ua plus vb is their greatest common divisor. And this is called basma. Now there's one final fun thing I want to tell you about algorithm. Uh because we were saying how great uh Brady was at picking numbers. What are the worst numbers that Brady could have chosen in terms of taking time to write down? >> Okay. >> So >> cuz if I had chosen prime numbers, >> if you chosen prime numbers, we would have got to one because they would have been co-prime. Uh but we could have got there fairly quickly. 101 and 103, for example. Well, the first step would have been that 103 is 1 * 101 + 2 and then we'd get 101 is 50 * 2 + 1 and then you get 2 is 2 * 1. So that actually ends really quickly. >> Okay, but you're asking what would have gone long. >> What could have gone long? And the answer is consecutive Fibonacci numbers. >> I would not have guessed that. So what that essentially means if you have Fibonacci numbers is every one of these steps is one time something plus something. So here's a small example for Fibonacci numbers. Uh let's say we've got 55 and 34. And you'll already notice I'm writing the numbers smaller because I know this is going to take a while. So we've got 55 is going to be 1 * 34 plus well actually by nature we're going to get the next Fibonacci number right so it's going to be 21 and 34 is 1 * 21 plus well what's the next smallest Fibonacci number 13 21 is 1 * 13 + 8 13 is 1 * 8 + 5 8 is 1 * 5 + 3. 5 is 1 * 3 + 2. 3 is 1 * 2 + 1. And then two is finally 2 * 1. >> And you told me if you ever get a one as your remainder, >> yeah, they're co-prime. >> That's co-prime. >> And you'll see because of all these ones, this took as many steps as you can. >> Yeah. So I took a lot with mine. >> You took a fair amount. We took a while to get to twos and threes here. >> It was this two that >> so this was nearly as inefficient as it could be but it could have been worse if they were Fibonacci numbers. Um and the historical reason why this is interesting is that in finding this um it was said it was the first foray into complexity theory. So the first time that anyone considered how long could an algorithm take what's the maximum complexity. Um, and it has also been described as the first practical use of Fibonacci numbers. Fibonacci numbers have been discovered way before anyone started to apply it in this situation. Uh, but no one had found anything they were useful for until this algorithm. If you like number five file videos, you're going to love some of the mathematical content here on Brilliant. It's clever, it's fun, beautifully designed, and it's also super interactive. You can personalize everything. Just get it how you want it, how you want to learn. There's no doubt the people who know all this stuff, who excel at problem solving, have a huge advantage in life and in the professional world. So why not up your game and check out Brilliant today. Learn for free on Brilliant for 30 days by going to brilliant.org/numberfile. You can also scan the QR code there on the screen and I'll pop links down below. That link is also going to get our viewers 20% off an annual premium subscription. A huge thanks to Brilliant for supporting this episode I believe is 34,560. So these are some values of super factorials. Now I also just want to pause side note the super factorial notation I think is boring. We have like exclamation marks factorials and we've just got the letter SF. So I want to propose a few changes. Now some people do write it as a dollar sign.