The GCD Trick You Need to See
43sIt’s a simple yet mind-blowing algorithm that feels like magic.
▶ Play ClipAI Summary
This video explains Euclid's algorithm for finding the greatest common divisor (GCD) of two numbers, using 484 and 781 as an example. It also covers the extended Euclidean algorithm to express the GCD as a linear combination of the original numbers, and discusses why consecutive Fibonacci numbers are the worst-case input for the algorithm's efficiency.
Chapters
[00:59]
First Step of Euclid's Algorithm
781 = 1 * 484 + 297, establishing the initial division.
[01:27]
Iterative Division Steps
Each step replaces the larger number with the remainder from the previous division: 484 = 1*297 + 187, 297 = 1*187 + 110, 187 = 1*110 + 77, 110 = 1*77 + 33, 77 = 2*33 + 11, and finally 33 = 3*11 + 0.
[02:23]
GCD Found: 11
The last nonzero remainder, 11, is the greatest common divisor of 484 and 781.
[02:54]
Verification that 11 is a Common Divisor
By back-substituting, 11 divides all remainders and thus divides both original numbers.
[04:19]
Proof that 11 is the Greatest
Any common divisor of 484 and 781 must divide 11 by tracing through the equations, so 11 is the largest.
[05:33]
Extended Euclidean Algorithm: Reversing Steps
Starting from the bottom equation, express 11 as a linear combination of 77 and 33, then replace 33 using the previous equation, etc., to eventually get 11 = 21*484 - 13*781.
[07:54]
General Result: Bezout's Identity
For any integers a and b, there exist integers u and v such that ua + vb = gcd(a, b).
[08:33]
Worst-Case Input: Consecutive Fibonacci Numbers
Consecutive Fibonacci numbers (e.g., 55 and 34) require the maximum number of steps in Euclid's algorithm, making them the worst case.
[10:34]
Historical Significance
Euclid's algorithm is considered the first foray into complexity theory, and using Fibonacci numbers to analyze its worst-case runtime is the first practical application of Fibonacci numbers.
Euclid's algorithm efficiently computes the GCD of two numbers, and its extension provides a linear combination that proves the GCD is the largest common divisor. The algorithm's worst-case performance on consecutive Fibonacci numbers highlights its connection to complexity theory and the practical use of the Fibonacci sequence.
Mentioned in this Video
Tutorial Checklist
2
01:27
Replace the larger number with the previous divisor (484) and the smaller with the remainder (297); divide to get remainder 187.
Study Flashcards (7)
What is Euclid's algorithm used for?
easy
Click to reveal answer
What is Euclid's algorithm used for?
easy
Click to reveal answer
To find the greatest common divisor (GCD) of two integers.
00:01
In Euclid's algorithm, what do you do if the remainder is zero?
easy
Click to reveal answer
In Euclid's algorithm, what do you do if the remainder is zero?
easy
Click to reveal answer
The last nonzero remainder is the GCD.
02:23
Express 11 as a linear combination of 484 and 781 using the extended Euclidean algorithm.
hard
Click to reveal answer
Express 11 as a linear combination of 484 and 781 using the extended Euclidean algorithm.
hard
Click to reveal answer
11 = 21 * 484 - 13 * 781
05:33
What is Bezout's identity?
medium
Click to reveal answer
What is Bezout's identity?
medium
Click to reveal answer
For integers a and b, there exist integers u and v such that ua + vb = gcd(a, b).
07:54
What is the worst-case input for Euclid's algorithm in terms of number of steps?
medium
Click to reveal answer
What is the worst-case input for Euclid's algorithm in terms of number of steps?
medium
Click to reveal answer
Consecutive Fibonacci numbers.
08:33
Why is Euclid's algorithm historically significant for complexity theory?
medium
Click to reveal answer
Why is Euclid's algorithm historically significant for complexity theory?
medium
Click to reveal answer
It was the first time anyone considered the maximum number of steps an algorithm could take.
10:34
What is the GCD of 484 and 781?
easy
Click to reveal answer
What is the GCD of 484 and 781?
easy
Click to reveal answer
11
02:23
💡 Key Takeaways
🔧
Verification of GCD
Demonstrates a rigorous proof that 11 is a common divisor by back-substitution through the equations.
02:54
💡
Proof that 11 is the Greatest Common Divisor
Shows that any common divisor must divide 11, establishing 11 as the maximum.
04:19
📊
Worst-Case Numbers: Fibonacci
Reveals that consecutive Fibonacci numbers require the most steps, linking number theory to algorithm efficiency.
08:33
💡
First Foray into Complexity Theory
Euclid's algorithm analysis is considered the birth of complexity theory and the first practical use of Fibonacci numbers.
10:34Full Transcript
[00:01] So today we're going to talk about Uklid's algorithm. Um so give me two Let's say >> three-digit numbers. >> 484 >> 781
[00:14] >> 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
[00:31] is definitely not prime. Um because 484 is 22. Um so we could actually already that way. But I'm going to show you this algorithm. And this algorithm I was
[00:44] 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
[00:59] 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,
[01:11] nine there, and two. >> That's just one, subtract the other, is 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
[01:27] 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
[01:39] but this time it's with a remainder of 187. Okay, so now we repeat. 297 goes 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
[01:52] easy. 110. And we keep going and hope we don't run out of paper. Plus 77. don't run out of paper. Plus 77. 110 = 1 * 77 + 33. 77 = 2 * 33.
[02:08] >> + 11. Okay. 33 then equals 3 * 11 with no remainder. >> Stop point when we've got no remainder.
[02:23] for picking a number that takes the length of the paper. >> Is it Is it not normally you wouldn't have expected it to take that long? have done some that are done in two steps. Um, it can really depend. Um, and
[02:41] I can't reiterate more, we did not prepare this. So, prepare this. So, >> this tells us this last remainder term is our greatest common divisor. >> The 11. the 11 obviously in maths often
[02:54] 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 want to know we want to know that it is a divisor and we want to know that any
[03:08] a divisor and we want to know that any divisor of 484 and 781 is at most 11 so 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
[03:23] 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,
[03:38] 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
[03:50] well. So, 11 divides 77. Okay. 11 divides 33 and 77. So it divides all of 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
[04:03] 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
[04:19] 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. So, any number that divides 781 and 484 has to divide 297. So, if it
[04:34] 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
[04:51] 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
[05:04] 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
[05:19] 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. either. I'm really pleased with myself. >> I I am very very happy with that one as
[05:33] >> 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
[05:47] 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 >> So you've rearranged >> So I've rearranged this equation.
[06:00] >> 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
[06:18] 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
[06:36] 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
[06:52] 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 because it's going to be a whole bunch of repeated calculations.
[07:20] And then final step, we're going to replace the 297. So this becomes 8 * 484 replace the 297. So this becomes 8 * 484 minus 13 * 781 take 484 which is 21 * 484 minus 13 *
[07:39] 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 numbers, >> right?
[07:54] >> 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.
[08:08] brackets, I'm going to call this d. Using this algorithm, we can always find 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
[08:20] 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
[08:33] 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 numbers that Brady could have chosen in terms of taking time to write down?
[08:48] >> So >> cuz if I had chosen prime numbers, 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
[09:03] example. Well, the first step would have been that 103 is 1 * 101 + 2 and then been that 103 is 1 * 101 + 2 and then we'd get 101 is 50 * 2 + 1 and then you really quickly. >> Okay, but you're asking what would have
[09:18] >> 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 that essentially means if you have Fibonacci numbers is every one of these
[09:32] 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
[09:46] know this is going to take a while. So we've got 55 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
[09:59] Fibonacci number right so it's going to be 21 and 34 is 1 * 21 plus well what's be 21 and 34 is 1 * 21 plus well what's the next smallest Fibonacci number 13 21 the next smallest Fibonacci number 13 21 is 1 * 13 + 8 13 is 1 * 8 + 5
[10:18] is 1 * 13 + 8 13 is 1 * 8 + 5 8 is 1 * 5 + 3. 5 is 1 * 3 + 2. 3 is 1 * 8 is 1 * 5 + 3. 5 is 1 * 3 + 2. 3 is 1 * 2 + 1. And then two is finally 2 * 1.
[10:34] your remainder, >> yeah, they're co-prime. >> And you'll see because of all these ones, this took as many steps as you >> Yeah. So I took a lot with mine. >> You took a fair amount. We took a while
[10:47] >> 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
[11:03] 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
[11:17] 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
[11:30] 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.
[11:45] 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
[12:00] 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
[12:15] subscription. A huge thanks to Brilliant for supporting this episode factorials. Now I also just want to
[12:30] pause side note the super factorial notation I think is boring. We have like just got the letter SF. So I want to propose a few changes. Now some people propose a few changes. Now some people do write it as a dollar sign.
