## Lecture 18: Euclid's Algorithm

Lecture 18: Euclid's Algorithm
• Currently 4.0/5 Stars.
5434 views, 2 ratings - 01:18:23
Part of video series ArsDigita Discrete Math Course
Taught by ArsDigita
Learn about Euclid's Algorithm and how it is used.
• 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?
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.
• Currently 4.0/5 Stars.
Reviewed by MathVids Staff on April 17, 2009.
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.
• Currently 5.0/5 Stars.
Reviewed by dauclair on June 09, 2009.  