Lecture 18: Euclid's Algorithm
5661 views
|
2
ratings
Lesson Description:
Learn about Euclid's Algorithm and how it is used.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
Additional Resources:
- Lecture Notes - Lecture Notes from the course
- Problem Set 7 - A problem set with some problems from this lecture
Questions answered by this video:
- What is number theory?
- Why / how does public key cryptography work?
- If you have two jugs of sizes 7 and 17, what other values of volume can you obtain in the 17 jug?
- How can you use greatest common divisors (GCD) to solve puzzles with jugs and water?
- What is Euclid's Algorithm and what does it have to do with Greatest Common Divisor?
- What is the fastest and easiest way to find the greatest common divisor of two numbers?
-
Staff Review
Number theory is introduced and explained in this lecture in order to lead to cryptography. It starts off with the famous water jugs problem in which you have two jugs of different volume and you need to obtain a certain different volume. It is analyzed in depth from a number theory perspective, which is quite interesting. Euclidâs Algorithm is then tackled, and the process of finding the greatest common divisor of two numbers is made more concrete, and a theorem is shown to be true at the end. -
dauclair
I really like this instructor. His explanation of Euclid's Algorithm was excellent, which he introduces by first showing the water jug problem. Next, he shows how Euclid's Algorithm can be used to quickly find the GCD of two numbers and then he shows how to easily write the GCD as a linear combination by using back substitution.
