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
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:
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:
The remainder is 0, so the gcf of 1512 and 444 is 12
The algorithm in JavaScript:
function gcf(a, b) {
while (b != 0) {
t = b;
b = a % b;
a = t;
}
return a;
}