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
Since the larger number should go first, we swap them: 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 = 1512, b = 444:
The remainder is 0, so the gcf of 1512 and 444 is 12
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;
}