### 1 video in "Euclid's Algorithm"

## Lecture 18: Euclid's Algorithm

Lecture 18: Euclid's Algorithm

5434 views, 2 ratings - 01:18:23

Part of video series ArsDigita Discrete Math Course

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/

http://www.aduni.org/courses/discrete

Licensed under Creative Commons Attribution ShareAlike 2.0:

http://creativecommons.org/licenses/by-sa/2.0/

(
download video
)

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

- 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?

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.

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.