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).

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.

To find the Greatest Common Factor of a and b, gcf(a,b), make sure a > b then:

Calculate a/b = n R r
In other words, divide a by b and find n (the whole number of times b fits into a) and the remainder r.
Set a=b and b=r
Repeat until r=0

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

Start with: 35/10 = 3 R 5

Set a=b=10 and b=r=5: 10/5 = 2 R 0

The remainder is 0, so the gcf of 35 and 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

Swap a and b so a > b: a=112, b=42:

Start with: 112/42 = 2 R 28

Set a=b=42 and b=r=28: 42/28 = 1 R 14

Set 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

Swap a and b so a > b: a=112, b=42:

Start with: 1512/444 = 3 R 180

Set a=b=444 and b=r=180: 444/180 = 2 R 84

Set a=b=180 and b=r=84: 180/84 = 2 R 12

Set 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

Note: the algorithm comes from Euclid's Elements written in the third century BC!

The algorithm in JavaScript:

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