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.

• Greatest Common Divisor (gcd)
• Euclidean Algorithm
• Euclidean Algorithm in a table

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.

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:

We see 4 columns:

• Column a and column b:
  The numbers in these first two columns are exactly the same as the numbers in gcd(..., ...) on each line in our previous calculation.
• Column r (the last column):
  This is the remainder we talked about earlier. We didn't write it down before, but we did use it for our calculations. So it's handy to write it down. So in each row here r is the remainder of (a divided by b) where a and b are the values in the first two columns on that row.
  So r ≡ a mod b.
• The column with the "q"
  This q stands for quotient.
  Just like you can calculate the remainder of X/Y, you can also calculate the quotient of X/Y.
  It's not really necessary for the Euclidean algorithm, but we do need it for the Extended Euclidean Algorithm later. So it's better to already get used to it, plus it can be useful when doing the Euclidean Algorithm by hand.

• On each row, a = [b from the previous row] and b = [r from the previous row]
• In the last row, r=0. When r=0, you are done and then b in that last row is the answer.
  So in this case the answer is 2 (like we saw before).
  (You could add another row, then the answer is a on that row (since then gcd(a, b) = gcd(a, 0) = |a|).
  But that's not necessary, since b already contains that same answer on the row where r=0).

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.

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.

Video

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.