Greatest Common Factor Calculator

Greatest Common Factor

The greatest common factor (GCF) of two or more numbers, is the largest natural number that can divide each number into another (or the same) natural number. A natural number is any whole positive number, e.g. 1, 2, 3 ... and so on. The greatest common factor is sometimes also called the largest common factor (LCF), the greatest common divisor (GCD) or other variants thereof.

Example

What is the greatest common factors of the numbers 12, 18 and 24?

Factors of 12: 1, 2, 3, 4, 6, 12

Factors of 18: 1, 2, 3, 6, 9, 18

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24

The common factors are: 1,2,3,6, of which the greatest common factor is 6

Calculation method: Euclidean algorithm

There are multiple ways for calculating the greatest common factor. This calculator uses the Euclidean algorithm. Fundamental for its understanding is knowing that the GCF of two numbers, a and b (where a > b), is the same for numbers b and a % b ¹.

The algorithms goes as follows:

1. Calculate c = a % b (where a > b)

2. Set a = b and b = c

3. Repeat step 1 until c = 0

4. The value in b is the GCF of the two numbers

Example; find the least common multiple for the numbers 48 and 18

Step 1. a = 48, b = 18, c = 48 % 18 = 12

Step 2. a = 18, b = 12, c = 18 % 12 = 6

Step 3. a = 12, b = 6, c = 12 % 6 = 0. We can stop now as c = 0

Step 4. When c = 0, b = 6. Thus the GCF of 48 and 18 is 6

¹ The "%" symbol in this context refers to the modulo operator. The result of a % b is the remainder of the division. If we were to divide a 10-piece pie over 3 people evenly, one piece will be left over, thus 10 % 3 = 1. Dividing an 8-piece pizza over 2 people evenly, no pieces will be left over. Thus 8 % 2 = 0.