Interactive Greatest Common Factor (or Divisor)
We use GCF for 'greatest common factor' in this article.
There are various methods to find the GCF, we will examine two.
1. Listing the factors: this is the brute force method. We just factor both numbers and see what is the largest they have in common. Works great for smaller numbers.
2. Using an algorithm: this method is easy, fast, and efficient. This method scales better than the brute force method.
Our interactive finds the GCF both ways.
We notice that listing the factors works fine for small numbers, but the bigger the number the more difficult it is. Try Finding the GCF of 1732 and 2431 by listing out their factors, it will take a while.
How Does the Algorithm Work
The key to this algorithm is the remainder of the division Here's an example implementation in JavaScript:
function gcf(a, b) {
if (b === 0) return a;
return gcf(b, a % b);
}
}
This implementation uses recursion, where the function ('gcf") calls itself with the updated values of a and b until b becomes 0. The GCD is then returned as the result.
We can see this step by step in our interactive above. Notice how the numbers shift to the left.
Why Can't GCF Be Greater Than the Difference
It's important to note that the GCF can never be larger than the difference between our two numbers.
Multiplying the GCF by some integer, we should be able to reach both the smaller and larger number. If the GCF were to be larger than the difference between the two numbers, it would be impossible to multiply it by any integer to reach both numbers because the smaller number plus the GCF would 'overshoot' the larger number.
We can see this concept illustrated in the interactive.
Resources