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)

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.

Example

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:

abqr
361036
10614
6412
4220
What do we see here?

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.

Also notice that:
• 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).

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.

Quotient

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

Remainder

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.

Video

For those who like to hear someone explain it instead of having to read a lot.