E.E.A. .com
It doesn't have to be difficult if someone just explains it right.

The Euclidean Algorithm

The basic version of the algorithm. Useful to understand the table notation.

Text or video?

You can choose to read this page or watch the video at the bottom of this page. Both cover the same material, so there's no need to look at both. Reading this page might be quicker, but the video could feel a little more detailed.

Table of contents:

Greatest Common Divisor (gcd)

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


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.

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.


Calculate gcd(36, 10).

Using property 3 from above, we know that gcd(36, 10) = gcd(10, remainder of (36/10)).
How do we calculate the remainder of X divided by Y? For now, just use X mod Y. So in this case the remainder of (36/10) = 36 mod 10 ≡ 6.
So we have gcd(36, 10) = gcd(10, remainder of (36/10)) = gcd(10, 6).
So we get gcd(10, 6), which means we can now simplify gcd(10, 6) the same way:
gcd(10, 6) = gcd(6, remainder of (10/6)) = gcd(6, 4). Similarly, we can now simplify gcd(6, 4) and you'll get gcd(4, 2). And if you simplify gcd(4, 2), you'll get 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.
Property 4 states that gcd(a, 0) = |a|, so in this case: gcd(2, 0) = 2.
Now we are done!
We started with gcd(36, 10) and we finished with 2. So we have just discovered that gcd(36, 10) = 2 by using the Euclidean Algorithm.

Here is the same calculation again, but without all that text:
gcd(36, 10) =
gcd(10, 6) =
gcd(6, 4) =
gcd(4, 2) =
gcd(2, 0) = 2
So gcd(36, 10) = 2.

Euclidean algorithm in a table

In the example above we had to write "gcd" and the parentheses over and over again.
This isn't really necessary for the calculation, so we might as well skip it and just write down the numbers in a table.
If we calculate gcd(36, 10) just like we did before, but now we use a table to write down the numbers, it looks like this:

What do we see here?

We see 4 columns:

Also notice that:

q = quotient of a/b
r = remainder of a/b

We said before that remainder of a/b = a mod b.
But you can also derive the remainder from the quotient. This can be useful when you do the calculations by hand, or when we need to calculate the quotient anyway (e.g. in the Extended Euclidean Algorithm).
In order to do that, we first need to find the greatest number below a, that can be divided by b.
So in the case of a=36 and b=10, what is the greatest number below 36 that can be divided by 10? It's 30. If you divide 30 by 10, you get 3. That's the quotient.


So the quotient q = [the greatest number below a divisible by b] divided by b.


The remainder r = a - [that greatest number below a divisible by b] = a - (q*b).
So as you can see, once you have q, you can easily calculate r by doing a - (q*b). In this case: 36-(3*10)=6

You might wonder:

  • is calculating this quotient really necessary?
    Not for the Euclidean algorithm, but it can be useful if you this by hand.
    Also, we do need it for the Extended Euclidean algorithm.
  • why can't we just use [the greatest number below a divisible by b] in the table instead of q?
    For the Euclidean Algorithm, we actually could. But for the Extended Euclidean Algorithm, we need this q for other columns. So it's better to get used to using q, instead of some other number we're not going to use again.

At this point you know enough to create your own table. But let's give you a quick step-by-step overview anyway just to make things clearer.

Let's say you want to calculate gcd(a, b). With a=36 and b=10 again.
Where do we start and when do we stop?

  • Create a table and write down the column names above the columns:
    a, b, q and r.
  • Then start with the first row. Fill in the numbers for a and b.
    In this case: 36 and 10.
  • Calculate the quotient.
    q = [the greatest number below a divisible by b] divided by b.
    In this case: q = 30/10=3
  • Calculate the remainder.
    Use r = a-(q*b) or just r=a mod b.
    In this case: r = 36-(3*10) = 36 mod 10 = 6
  • Now we finished the first row. Let's continue to the next row.
    Copy b and r from the previous row to a and b on this row.
    So a = [b from the previous row] = 10. And b = [r from the previous] row = 6.
  • Now calculate the quotient and the remainder on this row again.
  • Copy b and r to a and b on the next row again and calculate q and r on that row again.
  • Continue until you have finished a row where r=0.
    If that's the case, then the answer is b on that row.

Want to see and practice more examples?

Have a look at our awesome calculator.
If you want to practice more: make up two numbers and create the table yourself. Then use the calculator to verify your answer.


For those who like to hear someone explain it instead of having to read a lot.
This video covers the same material as this page, so you don't have to watch it if you already read this page
Unless you feel like you need to understand it better.

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