- Home
- Tools
- Math
- GCD & LCM Calculator
- GCF Calculator (Greatest Common Factor)
GCF Calculator (Greatest Common Factor)
Enter two or more whole numbers to find their greatest common factor, also known as the GCD or HCF, with the steps that lead to it.
Two or more whole numbers, separated by commas, spaces or new lines.
Greatest common factor (GCF)
18
Least common multiple (LCM)
630
Euclidean algorithm
- 126 = 1 × 90 + 36
- 90 = 2 × 36 + 18
- 36 = 2 × 18 + 0
The remainder has reached 0, so the last divisor is the GCF: 18. The LCM follows from it: 126 × 90 ÷ 18 = 630.
Prime factorizations
| 126 | = 2 × 32 × 7 |
|---|---|
| 90 | = 2 × 32 × 5 |
| GCF | = 2 × 32 = 18 |
| LCM | = 2 × 32 × 5 × 7 = 630 |
The GCF takes each prime that all the numbers share, with the lowest exponent it has anywhere. The LCM takes every prime that occurs, with its highest exponent.
Three names for one number
The greatest common factor (GCF), the greatest common divisor (GCD) and the highest common factor (HCF) are the same thing: the largest whole number that divides every number in the list without a remainder. GCF is the name used most in American schools, HCF in British ones, and GCD in mathematics and programming.
By listing the factors
For small numbers you can write out all the factors of each and pick the largest one they share.
| Number | Its factors |
|---|---|
| 12 | 1, 2, 3, 4, 6, 12 |
| 18 | 1, 2, 3, 6, 9, 18 |
The shared factors are 1, 2, 3 and 6, so the GCF of 12 and 18 is 6.
By Euclid's algorithm
Listing gets tedious for larger numbers, and it is not what the calculator does. It divides the larger number by the smaller one, then the previous divisor by the remainder, and so on until the remainder is 0. For the two numbers the box above starts with, 126 and 90:
| Step | Division |
|---|---|
| 1 | 126 = 1 × 90 + 36 |
| 2 | 90 = 2 × 36 + 18 |
| 3 | 36 = 2 × 18 + 0 |
The last divisor, 18, is the GCF. Three divisions were enough, where the lists would have needed the twelve factors of each number.
What you do with it
- Simplify a fraction in one step by dividing the top and the bottom by their GCF: 90/126 becomes 5/7. The fraction calculator brings its answers to lowest terms the same way.
- Simplify a ratio the same way: 126 : 90 is 7 : 5.
- Cut into equal pieces. A floor of 126 by 90 cm can be laid with whole square tiles of 18 cm, and with no larger size.
A GCF of 1 means the numbers have no factor in common. 8 and 15 are an example, although neither of them is prime.
The GCD & LCM calculator page explains why Euclid's algorithm works and what happens with zero and with negative numbers.