# The Euclidean Algorithm

You can choose to read this entire page or watch a video instead. Both explain the same.

The video is at the bottom of this page

**Greatest Common Divisor (gcd)**

This is the greatest number that divides two other numbers a and b.

__Examples__

When you have two numbers a and b, with a = 8 and b = 12, then gcd(a, b) = gcd(8,12) = 4.

Note that gcd(b, a) = gcd(a, b), so gcd(12, 8) also equals 4.

Other examples:

gcd(12, 60) = 12

gcd(5, 7) = 1

gcd(10, 2) = 2

gcd(35, 45) = 5

gcd(-44, -22) = 22.

Note: it's not -22 in the last case, because we are looking for the

**common divisor. -22 divides them both, but so does 22. And 22 is greater than -22.**

__greatest____Try it yourself__

**Answer**: gcd(0, 0) = 0

__Properties of the gcd you should remember__

1. gcd(a, b) = gcd(b, a)

2. gcd(a, b) = gcd(-a, b) = gcd(a, -b) = gcd(-a, -b).

3. gcd(a, b) = gcd(b, remainder of (a/b))

4. gcd(a, 0) = |a|

(i.e. the absolute value of a)

Property 3 and 4 are important for the Euclidean Algorithm.

**Euclidean Algorithm**

Calculating the gcd of two numbers by hand is more difficult, especially if you have somewhat large numbers. But using property 3 and 4 mentioned above, we can simplify the calculation of the gcd of two numbers by reducing it to the calculation of the gcd of two smaller numbers.

__Example__

Calculate gcd(36, 10).

Using property 3, we know that gcd(36, 10) = gcd(10, remainder of (36/10)).

The greatest number below 36 that is divisible by 10 is 30.

The quotient is 30/10 = 3 and the remainder is the part of 36 that we didn't divide by 10, which is 36-30=6. So now we know that gcd(36, 10) = gcd(10, 6).

Similarly, we could find out that gcd(10, 6) = gcd(6, 4)

and gcd(6, 4) = gcd(4, 2) and gcd(4,2) = gcd(2, 0)

Now pay attention to the zero in gcd(2, 0). We want a zero to appear there, because then we can use property 4.

In this case: gcd(2, 0) = 2. Now we are done!

We have just discovered that gcd(36, 10) = 2 by using the Euclidean Algorithm.

Here is the calculation again, without the explanation:

gcd(36, 10) =

gcd(10, 6) =

gcd(6, 4) =

gcd(4, 2) =

gcd(2, 0) = 2

So gcd(36, 10) = 2.

__Try it yourself__

Enter two numbers to the calculation of their gcd using the Euclidean Algorithm

**Answer**:

gcd(0,0) = 0

__Notation using a table__

In the above notation you have to write "gcd" and the parentheses each time.

This isn't really necessary for the calculation, so we might as well skip it.

It is also not necessary to write down the quotient, but this could actually be useful (e.g. for verifying that your calculation is correct).

So therefore you could also use a table instead of the above calculation of gcd(36, 10), that looks like this:

a | b | q | r |
---|---|---|---|

36 | 10 | 3 | 6 |

10 | 6 | 1 | 4 |

6 | 4 | 1 | 2 |

4 | 2 | 2 | 0 |

q=quotient and r=remainder of dividing a by b (a/b).

When r = 0, you are done and there is no need to write down the next row (even though you could write another row where b reaches 0).

The answer of the whole calculation is then the

**b**in the last row. In this case

**2**, as b=2 on the last row.

Note that, once you wrote down an entire row, it is very easy to find the a and b of the next row: a = [b of the previous row], b = [r of the previous row].

**Learn about the extended version**

> Continue to the Extended Euclidean Algorithm

**It is probably quicker to read this page if you want to learn about the Euclidean Algorithm.**

Video

But if you still prefer watching a video instead (or if you want to understand it better), you can watch the video below.

The video covers the same material as the rest of this page, so if you've already read this page and you think you understand it, then there is no need for watching this video.

0:00 Introduction

0:14 What is the "gcd" of two numbers?

2:27 Four properties of the gcd to remember, especially properties 3 and 4

3:26 The idea of the Euclidean Algorithm

3:58 An Example of the Euclidean Algorithm (regular notation)

8:15 The "table notation" with the same example

11:33 Which notation is better: regular notation or "table notation"?

11:58 Another example of the Euclidean Algorithm (table notation)

14:28 The online calculator for the Euclidean Algorithm

14:51 Summary of the "table notation"

15:49 Thank you for watching, have a look at the description