﻿ The Euclidean Algorithm

# The Euclidean Algorithm

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

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 greatest common divisor. -22 divides them both, but so does 22. And 22 is greater than -22.

Try it yourself
a b:

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
a b:
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
361036
10614
6412
4220
The columns a and b denote the numbers that you put in gcd(a, b).
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].

> Continue to the Extended 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