Greatest Common Factor Calculator
Please provide numbers separated by a comma "," and click the "Calculate" button to find the GCF.
What is the Greatest Common Factor (GCF)?
In arithmetic, the greatest common factor (GCF), also referred to as the greatest common divisor, of two (or more) non‑zero integers a and b is the largest positive integer that can divide both numbers exactly. It is normally written as GCF(a, b). For example, GCF(32, 256) equals 32.
Prime Factorization Method
There are several techniques to determine the greatest common factor of given numbers. One approach is to break each integer down into its prime factors, identify the primes they share, and multiply those common primes together to obtain the GCD. See the illustration below for a concrete example.
| EX: |
GCF(16, 88, 104) 16 = 2 × 2 × 2 × 2 88 = 2 × 2 × 2 × 11 104 = 2 × 2 × 2 × 13 GCF(16, 88, 104) = 2 × 2 × 2 = 8 |
Using prime factorisation works well only for relatively small values. When the numbers become large, performing the factorisation and then extracting the shared factors turns into a labor‑intensive task.
Euclidean Algorithm
A more efficient alternative for finding the GCF is the Euclidean algorithm. This method outperforms prime‑factor based calculations by repeatedly applying a division step and exploiting the fact that the GCD of two integers also divides their difference. The procedure is outlined as follows:
|
GCF(a, a) = a GCF(a, b) = GCF(a-b, b), when a > b GCF(a, b) = GCF(a, b-a), when b > a |
In practice:
- Given two positive integers, a and b, where a is larger than b, subtract the smaller number b from the larger number a, to arrive at the result c.
- Continue subtracting b from a until the result c is smaller than b.
- Use b as the new large number, and subtract the final result c, repeating the same process as in Step 2 until the remainder is 0.
- Once the remainder is 0, the GCF is the remainder from the step preceding the zero result.
| EX: |
GCF(268442, 178296) 268442 - 178296 = 90146 178296 - 90146 = 88150 90146 - 88150 = 1996 88150 - 1996 × 44 = 326 1996 - 326 × 6 = 40 326 - 40 × 8 = 6 6 - 4 = 2 4 - 2 × 2 = 0 |
Applying the method to the numbers above shows that GCF(268442, 178296) = 2. If additional integers are introduced, the same routine is used: first find the GCF of the first two numbers, then combine that result with the next integer, and so on. For instance, to compute GCF(268442, 178296, 66888), we start with GCF(268442, 178296) = 2 and then evaluate GCF(66888, 2), which also yields 2. Consequently, GCF(268442, 178296, 66888) = 2.