Euclidean Algorithm

In this lesson, we'll talk about the Euclidean Algorithm.

Before learning the algorithm, we need to understand what it does. Basically, given two numbers and , it give us the greatest common divisor (gcd) of and .

But what is the greatest common divisor of two numbers? Greatest common divisor of and is the maximum integer such that and is a multiple of ( is a divisor of and ). For example, and .

Now, let's talk about the algorithm. It will use two gcd properties: