Lecture 18: Euclid's Algorithm
In this lecture on Euclid's Algorithm, you will learn about number theory and how it is used in public key cryptography. The lesson begins by introducing a puzzle involving two jugs of different sizes, and the different amounts of water that can be obtained by pouring water back and forth between them. The puzzle is connected to the fundamental first result in number theory, greatest common divisors and Euclid's algorithm, and the different values that can be obtained are multiples of the greatest common divisor. The lecture also discusses the connection between these numbers and how to calculate them quickly.
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/
- Lecture Notes - Lecture Notes from the course
- Problem Set 7 - A problem set with some problems from this lecture
- 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.
