Euclidean Algorithm

The Euclidean Algorithm is a special way to find the Greatest Common Factor of two integers.

Division with Remainders

It uses the concept of division with remainders (no decimals or fractions needed).

7 / 2 = 3 R 1 (remainder 1)

Example: 7 divided by 2

7 ÷ 2 = 3 R 1

7 can be divided into 2 equal parts of 3 each with 1 left over

So we are finding how many times one number fits into the other exactly, and how much is left over.

Example: 35 divided by 10

35 ÷ 10 = 3 R 5

The Euclidean Algorithm

The algorithm works by continuing to do this type of division until we get a remainder of zero. And each time around we reduce the size of the numbers.

The goal is to find the the Greatest Common Factor of a and b which we will call gcf(a,b)

To find gcf(a,b):

The last value of b is the gcf of the original two integers.

Example: Find gcf(35,10), the Greatest Common Factor of 35 and 10

Make sure a > b:
a=35, b=10
Calculate a/b:
35/10 = 3 R 5
Again but with a=b (10) and b=r (5):
10/5 = 2 R 0

The remainder is 0, so gcf(35,10) is 5

So we keep trying division until we get a remainder of zero which tells us "hey, that last b value divides perfectly!" and we are done.

Another example:

Example: Find the Greatest Common Factor of 42 and 112

Since the larger number should go first, we swap them:

Make sure a > b:
a=112, b=42
Calculate a/b:
112/42 = 2 R 28
Next with a=b (42) and b=r (28):
42/28 = 1 R 14
Next with a=b (28) and b=r (14):
28/14 = 2 R 0

The remainder is 0, so the gcf of 42 and 112 is 14

One more example:

Example: Find the Greatest Common Factor of 1512 and 444

Make sure a > b:
Yes
Calculate a/b:
1512/444 = 3 R 180
Next with a=b (444) and b=r (180):
444/180 = 2 R 84
Next with a=b (180) and b=r (84):
180/84 = 2 R 12
Next with a=b (84) and b=r (12):
84/12 = 7 R 0

The remainder is 0, so the gcf of 1512 and 444 is 12

Did you know? The algorithm comes from Euclid's Elements written in the third century BC!

Being over 2,300 years old, it is one of the oldest known algorithms still in use today.

The algorithm in JavaScript:

function gcf(a, b) {
	while (b != 0) {
		t = b;
		b = a % b;
		a = t;
	}
	return a;
}
25369, 25370, 25371, 25372