Euclidean algorithm to find GCF

0:00- [Instructor] What we're going to do in this video is get some practice applying the Euclidean algorithm, named after the famous mathematician, Euclid, who's done so much work in geometry and other places. But this is kind of a cool one and surprisingly useful.

0:15We're not going to prove it in this video, exactly why it works, but I'll show you how to use it, and I'll do it with a very real example. So let's say we wanna find the greatest common factor, and we're gonna do two pretty large numbers that it would be hard for me to do in my head.

0:30So the greatest common factor of 252 and 198. And just as a reminder, this would be the largest number that is a factor of both. Well, what the Euclidean algorithm tells us is, this is going to be the same thing as the greatest common factor of the difference between these two numbers, so 252 minus 198, and the smaller of these two, and 198.

0:57So 252 minus 198 is 54. So it's the same thing as the greatest common factor of 54 and 198. Well, we could either try to figure that out with some other method, or we could keep applying the Euclidean algorithm. This is going to be the same thing as the greatest common factor of the difference between the two, 198 minus 54, and the smaller of the two, and that's now 54.

1:25Well, what's 198 minus 54? That is 144. And we can keep going. This is going to be the greatest common factor of the difference between these two, 144 minus 54, and the smaller of the two is still 54. So 144 minus 54, that is going to be... Did I do that right?

1:52Yeah, that's going to be equal to 90. And so, I can keep going. This is going to be equal to the greatest common factor of the difference between these two, 90 minus 54, and the smaller of these two, that's still 54. So it's going to be the greatest common factor of 36 and 54.

2:13And I could keep going. That's going to be the greatest common factor of the difference between these two, 54 minus 36, and now, the smaller one is 36. 54 minus 36 is 18. You might already be able to do this in your head, but I'll keep going. That's gonna be the greatest common factor of the difference between the two, 36 minus 18, and the smaller of these two, and 18.

2:3636 minus 18 is 18. And now, it's hitting us over the head. What's the largest number that will divide into both 18 and 18? Well, that of course is going to be equal to 18. So hopefully you appreciate that. This would've not been easy to do with any other method.

2:53We would factor each of those, either just looking at traditional factors or prime factors, and you try to rebuild to get to your greatest common factor, while the Euclidean algorithm, with just repeated subtraction essentially, lets us get there. Now, I didn't explain why it works.

3:08And if you're inspired, I encourage you to think about why it's working. And hopefully, if I get some time, I might make a video that actually proves why it works.