Lecture 18: Euclid's Algorithm

Sick of ads?​ Sign up for MathVids Premium
Taught by ArsDigita
  • Currently 4.0/5 Stars.
5741 views | 2 ratings
Lesson Summary:

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.

Lesson Description:

Learn about Euclid's Algorithm and how it is used.

More information about this course:
Licensed under Creative Commons Attribution ShareAlike 2.0:

Additional Resources:
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

    • Currently 4.0/5 Stars.
    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

    • Currently 5.0/5 Stars.
    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.