Skip to main content
ponderloop
Menu

GCF and LCM Calculator

The greatest common factor (GCF, also called GCD or HCF) is the largest number that divides every number in the list, and the least common multiple (LCM) is the smallest positive number they all divide. For 84, 126, 210: GCF = 42 and LCM = 1260. For two numbers such as 48 and 180, GCF = 12 and LCM = 720, and the two always satisfy GCF × LCM = 48 × 180 = 8640. The calculator takes 2 to 20 whole numbers of up to 30 digits (negatives and 0 are handled by the usual conventions), shows Euclid’s algorithm step by step, the prime-factor method and, for small inputs, a list of multiples, and also simplifies a fraction with its GCF and finds Bézout coefficients.

Updated Runs in your browser: nothing you enter is uploadedHow this tool works

Negatives and 0 are fine: signs are ignored, GCF(0, n) = |n|, GCF(0, 0) is reported as 0 and any LCM with 0 is 0.

For adding and multiplying fractions, or turning decimals into fractions, use the fraction calculator.

GCF(84, 126, 210) = 42; LCM(84, 126, 210) = 1260

GCF 42 · LCM 1260

Numbers
3
GCF (GCD, HCF)
42
LCM
1260

The working, three ways

1. Euclid’s algorithm

Divide the larger by the smaller and keep the remainder until it is 0; the last non-zero remainder is the GCF. For a list, the GCF so far is combined with the next number.

GCF(84, 126): a = q × b + r
Stepa = q × b + r
1126 = 1 × 84 + 42
284 = 2 × 42 + 0

The last non-zero remainder is 42, so GCF(84, 126) = 42.

GCF(42, 210): a = q × b + r
Stepa = q × b + r
1210 = 5 × 42 + 0

The last non-zero remainder is 42, so GCF(42, 210) = 42.

  • LCM(84, 126) = 84 ÷ 42 × 126 = 252.
  • LCM(252, 210) = 252 ÷ 42 × 210 = 1260.

2. Prime factors

  • 84 = 2² × 3 × 7
  • 126 = 2 × 3² × 7
  • 210 = 2 × 3 × 5 × 7
Exponent of each prime in each number, in the order typed
PrimeExponentsLowestHighest
22, 1, 112
31, 2, 112
50, 0, 101
71, 1, 111

GCF: Multiply the primes common to all, each to its lowest power: 2 × 3 × 7 = 42.

LCM: Multiply every prime that appears, each to its highest power: 2² × 3² × 5 × 7 = 1260.

3. Listing multiples

Listing multiples is shown only while the LCM is 200 or less (here it is 1260); the other two methods work for any size.

Also worth knowing

GCF × LCM = product

For the first two numbers, 84 and 126: GCF = 42 and LCM = 252.

42 × 252 = 10584 = |84 × 126|

So the LCM of two numbers is |a × b| ÷ GCF: 10584 ÷ 42 = 252. It holds for exactly two numbers; for three or more, use the pairwise steps above.

Bézout coefficients (extended Euclid)

Extended Euclid for 84 and 126: each remainder r = a × s + b × t
Rowqrst
0–8410
1–12601
208410
3142−11
4203−2

The row where r reaches its last non-zero value gives the coefficients: x = −1, y = 1.

84 × (−1) + 126 × 1 = −84 + 126 = 42

Every solution has the form x = −1 + k × 3, y = 1 − k × 2 for a whole number k.

Simplify a fraction

18/24 = 3/4

  1. Find the GCF of the top and bottom: GCF(18, 24) = 6.
  2. Divide both by 6: 18 ÷ 6 = 3 and 24 ÷ 6 = 4.
  3. Result in lowest terms: 3/4.

Worked examples

Each row is computed by the calculator above. The last column checks that GCF × LCM equals the product of the two numbers.
NumbersGCFLCMGCF × LCM = a × b
12, 186366 × 36 = 216
8, 124244 × 24 = 96
48, 1801272012 × 720 = 8640
21, 63423 × 42 = 126
35, 64122401 × 2240 = 2240
84, 1264225242 × 252 = 10584
100, 752530025 × 300 = 7500
1071, 462212356221 × 23562 = 494802

Zero, negatives and other edge cases

Signs are ignored and the results are never negative. The GCF of 0 and 0 is a convention: some texts leave it undefined, and this calculator reports 0.
NumbersGCFLCMWhy
12, 0120Every number divides 0, so GCF(0, n) = |n|; the only common multiple is 0
0, 000Every number divides 0, so there is no greatest divisor; reported as 0
−12, 18636Signs are dropped first
−12, −18636Signs are dropped first
1, 717Coprime numbers share only the factor 1, so the LCM is their product
7, 777A number is its own GCF and LCM

Euclid’s algorithm for 240 and 46, with Bézout coefficients

Each row is a = q × b + r, then the pair (b, r) repeats. The extended algorithm tracks coefficients so that 240 × s + 46 × t = r on every row; the last non-zero row gives −9 and 47.
qrst
–24010
–4601
5101−5
46−421
145−26
12−947
2023−120

How to find the GCF and LCM

  1. Use Euclid’s algorithm for the GCF. Divide the larger number by the smaller and keep the remainder; repeat with the smaller number and the remainder until it is 0. For 240 and 46: 240 = 5 × 46 + 10, then 46 = 4 × 10 + 6, then 10 = 1 × 6 + 4, then 6 = 1 × 4 + 2, then 4 = 2 × 2 + 0. The last non-zero remainder, 2, is the GCF.
  2. Or compare prime factors. Factor each number into primes. Multiply the primes common to all, each to its lowest power: 2 × 3 = 6. Multiply every prime that appears, each to its highest power: 2² × 3² = 36. For 12 and 18 that gives GCF 6 and LCM 36.
  3. Get the LCM from the GCF. For two numbers, LCM = |a × b| ÷ GCF. For 48 and 180: 48 × 180 ÷ 12 = 720. For more numbers, fold left: LCM(6, 4, 10) = LCM(LCM(6, 4), 10) = LCM(12, 10) = 60.
  4. Or list multiples for small numbers. Write multiples of each number until one appears in every list. For 4 and 6 the lists 4, 8, 12 and 6, 12 meet at 12.
  5. Simplify a fraction with the GCF. Divide the numerator and denominator by their GCF: the GCF of 18 and 24 is 6, so 18/24 = 3/4.

Frequently asked questions

What is the difference between GCF, GCD and HCF?
Nothing: greatest common factor (GCF), greatest common divisor (GCD) and highest common factor (HCF) are three names for the same number, the largest whole number that divides every number given. The GCF of 48 and 180 is 12.
How do you find the LCM of two numbers?
Divide the product by the GCF: LCM(a, b) = |a × b| ÷ GCF(a, b). For 48 and 180 that is 8640 ÷ 12 = 720. You can also list multiples of each number until one appears in both lists, or take every prime at its highest power.
How do you find the GCF and LCM of three or more numbers?
Combine them one at a time, because GCF(a, b, c) = GCF(GCF(a, b), c) and the same holds for the LCM. For 84, 126, 210 the GCF is 42 and the LCM is 1260. Note that GCF × LCM = product holds for exactly two numbers, not for three or more.
How does Euclid’s algorithm work?
It rests on GCF(a, b) = GCF(b, a mod b). Repeat the division a = q × b + r until the remainder is 0; the last non-zero remainder is the GCF. For 240 and 46 it takes 5 divisions to reach 2. It needs far fewer steps than factoring, and it works on numbers far too big to factor.
What are Bézout coefficients?
They are whole numbers x and y with a × x + b × y = GCF(a, b). The extended Euclidean algorithm finds them by tracking the coefficients through each division. For 240 and 46: 240 × −9 + 46 × 47 = 2. They are not unique: adding k × b/GCF to x and subtracting k × a/GCF from y gives another pair. When the GCF is 1, x is the modular inverse of a modulo b (up to adding b).
What is the GCF or LCM when one number is 0?
Every number divides 0, so GCF(0, n) = |n|; for example GCF(0, 12) = 12. The only common multiple of 0 and anything is 0, so the LCM is 0. GCF(0, 0) has no greatest divisor, since every number divides 0. Some texts call it undefined and many programming libraries return 0, which is what this calculator reports (0).
Can the GCF or LCM be negative?
By the usual convention no: the GCF and LCM are taken on absolute values and are never negative. GCF(−12, 18) = 6 and LCM(−12, 18) = 36. Bézout coefficients keep the signs of the inputs, so a × x + b × y still equals the GCF.
What if the GCF is 1?
Then the numbers are coprime (relatively prime): they share no factor above 1, and for two numbers the LCM is their product. GCF(8, 15) = 1 and LCM(8, 15) = 120. A fraction whose numerator and denominator are coprime is already in lowest terms.
How do you simplify a fraction with the GCF?
Divide both the numerator and the denominator by their GCF. For 18/24 the GCF is 6, so 18/24 = 3/4. A negative denominator is moved to the numerator, so 3/−6 = −1/2. To add or compare fractions, use the fraction calculator.
How big can the numbers be?
Each number can have up to 30 digits, because the calculator uses exact arbitrary-size integers (BigInt) and never rounds. The prime-factor method uses trial division, so it is shown only for numbers up to 1,000,000,000,000; the multiples method only while the LCM is 200 or less. Euclid’s algorithm and the extended algorithm work at any size here.

How it works

Every number is read as an exact integer (BigInt), so nothing is rounded. Signs are dropped: GCF(a, b) = GCF(|a|, |b|), with GCF(0, n) = |n| and GCF(0, 0) = 0 by convention, and the LCM is |a × b| ÷ GCF(a, b), or 0 when either number is 0. A list is combined from the left: GCF(a, b, c) = GCF(GCF(a, b), c), and the same for the LCM. Euclid’s algorithm repeats a = q × b + r on the larger and smaller number until the remainder is 0, as described in Knuth’s The Art of Computer Programming, volume 2, section 4.5.2. The extended algorithm carries two extra columns, s and t, through the same divisions so that every remainder equals a × s + b × t. The prime-factor method divides out 2 and then odd candidates up to the square root, using a small factorizer written for this page; then the GCF takes each shared prime at its lowest power and the LCM takes every prime at its highest. The multiples method lists the multiples of each number up to the LCM. Fractions are reduced by dividing top and bottom by their GCF, with the sign kept on the top. Everything runs in your browser and nothing you type is sent anywhere.

Sources

More free tools

All toolsHome & DIY calculators