GCF and LCM calculator with steps
Enter two to six whole numbers separated by spaces or semicolons and the calculator returns the GCF (also called GCD) and the LCM. It shows the Euclidean algorithm line by line, the prime factorization with an exponent table, and the check that GCF × LCM = a × b for two numbers.
- ✅ Free
- 🔒 No sign-up
- 📱 Works on mobile
- ⚡ Instant results
🔒 Everything runs in your browser. Your data and files never leave your device.
Finding the GCF with the Euclidean algorithm
The greatest common factor (GCF, also called the greatest common divisor or GCD) of two whole numbers is the largest number that divides both. The Euclidean algorithm uses GCF(a, b) = GCF(b, r), where r is the remainder when a is divided by b. Repeat until the remainder is 0.
| Step | Division |
|---|---|
| 1 | \( 252 = 105 \times 2 + 42 \) |
| 2 | \( 105 = 42 \times 2 + 21 \) |
| 3 | \( 42 = 21 \times 2 + 0 \) |
The last nonzero remainder is 21, so GCF(252, 105) = 21. Two numbers whose GCF is 1 are relatively prime.
The LCM and its link with the GCF
The least common multiple (LCM) is the smallest positive number that both numbers divide into. For two numbers it comes straight from the GCF.
\[ \operatorname{GCF}(a ,\ b) \times \operatorname{LCM}(a ,\ b) = a \times b \quad \text{so} \quad \operatorname{LCM}(a ,\ b) = \dfrac{a \times b}{\operatorname{GCF}(a ,\ b)} \]
For more numbers, chain the results: LCM(a, b, c) = LCM(LCM(a, b), c). The LCM gives the least common denominator for adding fractions and solves repeating-cycle problems, such as two buses that leave a station together.
| a and b | GCF | LCM | Check a × b |
|---|---|---|---|
| 12 and 18 | 6 | 36 | \( 6 \times 36 = 216 = 12 \times 18 \) |
| 48 and 36 | 12 | 144 | \( 12 \times 144 = 1{,}728 = 48 \times 36 \) |
| 17 and 5 | 1 | 85 | \( 1 \times 85 = 85 = 17 \times 5 \) |
Using prime factorization
Factor each number: \( 12 = 2^{2} \times 3 \) and \( 18 = 2 \times 3^{2} \). The GCF is the product of the shared primes with the smallest exponents: \( 2 \times 3 = 6 \). The LCM is the product of all primes with the largest exponents: \( 2^{2} \times 3^{2} = 36 \).
This works for any number of values, which is what the exponent table shows. The Euclidean algorithm is faster for very large numbers, where factoring gets slow, so the table appears only for numbers of 12 digits or fewer.
3 real-life examples
GCF and LCM of 48 and 36
Euclid: \( 48 = 36 \times 1 + 12 \), then \( 36 = 12 \times 3 + 0 \). GCF = 12. LCM = 48 × 36 ÷ 12 = 1,728 ÷ 12 = 144.
Simplify 84/126 with the GCF
\( 126 = 84 \times 1 + 42 \) and \( 84 = 42 \times 2 + 0 \), so the GCF is 42. Divide top and bottom by 42: \( \dfrac{84}{126} = \) 2/3.
Two buses that meet again
One bus runs every 12 minutes, another every 18 minutes, and both leave at 8:00 a.m. The LCM of 12 and 18 is 36, so they leave together again 36 minutes later, at 8:36 a.m.