GCD Calculator
Enter a list — 2 numbers or 20 — to get the greatest common divisor and the least common multiple, with 3 methods shown side by side: the Euclidean chain, the prime factor grid, and the upside-down division ladder.
- Any number of inputs
- GCD and LCM together
GCD & LCM
LiveThe greatest common divisor and the least common multiple.
- GCD
- —
- LCM
- —
- Numbers given
- —
- Coprime?
- —
The GCD and LCM working, step by step
Three methods, one answer. The chain folds the list pair by pair, the factor grid takes the lowest exponent of every shared prime, and the ladder divides everything down at once.
Euclidean chain, pair by pair
Prime factor grid
Upside-down division ladder
What Is the Greatest Common Divisor (GCD)?
The greatest common divisor (GCD) is the largest whole number that divides every number in a set exactly. Dividing 48, 180 and 210 by 6 leaves a remainder of 0 in all 3 cases, and no number above 6 manages the same, so 6 is their greatest common divisor.
The GCD carries 3 names depending on the textbook. Greatest common divisor (GCD) is standard in number theory and computing, greatest common factor (GCF) is the American school term, and highest common factor (HCF) is the British and Indian one. All 3 describe the same number.
Two numbers with a GCD of 1 are coprime, also called relatively prime. 8 and 15 are coprime, since 8 = 2³ and 15 = 3 × 5 share no prime factor — neither number has to be prime for the pair to be coprime.
The GCD appears in 5 everyday places, and most of the time nobody names it:
- Simplifying fractions. Dividing 48/180 by their GCD of 12 gives 4/15 in one step, already in lowest terms.
- Reducing aspect ratios. 1920 and 1080 share a GCD of 120, which turns the resolution into 16:9.
- Tiling a surface. The largest square tile that covers a wall with no cutting has a side equal to the GCD of the wall's 2 dimensions.
- Splitting into equal groups. The largest identical groups that several piles can be split into is exactly their GCD.
- Testing coprimality. A modular inverse exists only when the GCD is 1, which is the first check inside RSA key generation.
Tiling makes the definition concrete. A wall measuring 210 cm by 90 cm (2.1 m × 0.9 m, or roughly 83 in × 35 in) takes square tiles of side 30 cm with none cut, since gcd(210, 90) = 30 — and 7 tiles across by 3 down covers it in 21 tiles exactly:
How to Use the GCD Calculator
To use the GCD calculator, type the numbers into the single field separated by commas or spaces, and read the greatest common divisor. The answer and the working appear together in 4 steps:
- Enter the numbers. Two is the minimum and 30 the
maximum, at up to 40 digits each. The field accepts
48, 180, 210and48 180 210equally. - Read the GCD and the LCM. Both come from the same run, since the least common multiple is derived from the greatest common divisor rather than computed separately.
- Check the coprime verdict and the reduced ratio, which shows every input divided through by the GCD.
- Open the working panel for the Euclidean chain, the prime factor grid and the upside-down ladder.
The calculator reports 5 results for every list: the GCD, the LCM, the coprime verdict, the reduced ratio, and the identity gcd × lcm = a × b for a pair of inputs. Arithmetic runs in arbitrary-precision integers, so the GCD and LCM stay exact at any size. The prime factor grid and the ladder are worked out for numbers up to a trillion, since factoring is genuinely hard while the Euclidean algorithm is not.
Other tools reach the same answer under other names.
Python has math.gcd(48, 180, 210),
which accepts any count of arguments since version 3.9.
C++ has std::gcd in
<numeric> from C++17.
Java has BigInteger.gcd,
Haskell has gcd in the
Prelude, and Excel has
GCD(number1, number2, …). The
TI-84 Plus keeps
gcd( under MATH ▸ NUM, and it takes 2
arguments at a time, so a list has to be folded by hand.
The tool works on whole numbers. Polynomials use the same Euclidean structure with polynomial division in place of integer division, which the polynomial remainder theorem calculator covers. Gaussian integers and other rings have their own GCD, defined up to multiplication by a unit, and fall outside this calculator.
How to Find the GCD
To find the GCD, pick 1 of 5 methods — prime factorisation, the Euclidean algorithm by subtraction, the modified Euclidean algorithm by modulo, upside-down division, or the binary algorithm. All 5 return the same number and differ only in how much work each demands.
Factor every number, then multiply the lowest power of each shared prime. 40 = 2³ × 5 and 60 = 2² × 3 × 5 share 2 and 5, at lowest powers 2² and 5¹, giving 4 × 5 = 20. The method is clear and stops being practical the moment factoring gets hard.
Subtract the smaller number from the larger and replace the larger with the result, until both are equal. Starting at 60 and 40 gives 20 and 40, then 20 and 20 — so the GCD is 20. Euclid's original version, and slow when the 2 numbers are far apart.
Replace the larger number with the remainder of the division instead of the difference. 60 mod 9 = 6, then 9 mod 6 = 3, then 6 mod 3 = 0, so the GCD is 3. One modulo replaces a whole run of subtractions, which is why this is the version in production code.
Divide every number by the smallest prime that divides them all, write the results underneath, and repeat until nothing but 1 divides the row. Multiplying the divisors used gives the GCD. The method handles a long list in one pass, which the pairwise methods cannot.
Apply 4 identities — gcd(0, a) = a, gcd(2a, 2b) = 2·gcd(a, b), gcd(2a, b) = gcd(a, b) for odd b, and gcd(a, b) = gcd(|a − b|, min(a, b)) for odd a and b — using only halving, subtraction and comparison. Stein's algorithm, and the fastest option on hardware where division costs more than a bit shift.
The Euclidean algorithm is what runs inside this calculator. Every common divisor of a and b divides the remainder a − qb as well, so replacing the pair (a, b) with (b, a mod b) leaves the set of common divisors untouched and the greatest one unchanged. The extended Euclidean algorithm steps tool shows every division for a single pair, along with the Bézout coefficients x and y in ax + by = gcd(a, b).
gcd(a, b) = gcd(b, a mod b) repeat until b = 0 gcd(g, 0) = g the stopping case lcm(a, b) = a ÷ gcd(a, b) × b divide first, so the value stays small gcd(a, b) × lcm(a, b) = a × b the identity behind itGCD Calculator Example
Finding the GCD of 48, 180 and 210 returns 6. The prime factor grid shows where the 6 comes from — take the lowest exponent down each column for the GCD, and the highest for the LCM:
| Number | Factorisation | 2 | 3 | 5 | 7 |
|---|---|---|---|---|---|
| 48 | 2⁴ × 3 | 4 | 1 | 0 | 0 |
| 180 | 2² × 3² × 5 | 2 | 2 | 1 | 0 |
| 210 | 2 × 3 × 5 × 7 | 1 | 1 | 1 | 1 |
| GCD = 6 | 2 × 3 | 1 | 1 | 0 | 0 |
| LCM = 5040 | 2⁴ × 3² × 5 × 7 | 4 | 2 | 1 | 1 |
The 5 column reads 0, 1, 1 — 48 contributes no factor of 5, so the minimum is 0 and 5 stays out of the GCD entirely. One number without a prime removes that prime for the whole set.
The upside-down division ladder reaches 6 by a different route, dividing all 3 numbers at once and multiplying the divisors used:
| 2 | 48 | 180 | 210 |
| 3 | 24 | 90 | 105 |
| — | 8 | 30 | 35 |
Running the Euclidean algorithm on the same numbers takes 4 divisions for the first pair alone. Dividing 210 by 48 leaves 18, dividing 48 by 18 leaves 12, dividing 18 by 12 leaves 6, and dividing 12 by 6 leaves 0 — so gcd(210, 48) = 6, and folding 180 into that result changes nothing.
GCD of Multiple Numbers
To find the GCD of multiple numbers, take the GCD of the first 2, then the GCD of that answer with the third, and carry on down the list. The operation is associative, so the order of the inputs never changes the result.
gcd(a, b, c) = gcd(gcd(a, b), c) gcd(48, 180, 210) = gcd(gcd(48, 180), 210) = gcd(12, 210) = 6The running GCD carries 2 properties worth watching. The value can only stay the same or shrink as numbers are added, since a new number can remove a shared factor and never create one. And the moment the running GCD reaches 1, the whole set is coprime and no later number can change the answer — which lets the calculator say so and stop early.
The LCM folds the same way, computed as
a ÷ gcd(a, b) × b rather than
a × b ÷ gcd(a, b). Dividing before
multiplying keeps the intermediate value below the final answer, which
matters once the numbers grow. lcm(48, 180, 210) works out at 5040.
Common GCD Mistakes
There are 5 common GCD mistakes, and 4 of them show up the moment the answer is divided back into every input.
Take the lowest exponent of each shared prime for the GCD. The highest exponent produces the LCM, which is the other answer entirely.
48 = 2⁴ × 3 180 = 2² × 3² GCD = 2⁴ × 3² = 144
48 = 2⁴ × 3 180 = 2² × 3² GCD = 2² × 3 = 12
Drop any prime missing from a single input. 48 carries no factor of 5, so 5 leaves the GCD of 48, 180 and 210 even though 180 and 210 both have one.
Check a composite divisor through prime powers that share nothing. Testing 12 as 2 and 6 lets 18 through, since 18 divides by both and 18 ÷ 12 leaves 6. Testing 12 as 4 and 3 rejects 18 correctly.
Continue the upside-down ladder until no prime divides the whole row. Halting 48, 180 and 210 after the single divisor 2 gives 2 rather than 6, since 24, 90 and 105 still share a factor of 3.
2 | 48 180 210 | 24 90 105 GCD = 2
2 | 48 180 210 3 | 24 90 105 | 8 30 35 GCD = 2 × 3 = 6
Report the GCD as positive. gcd(−48, 180) = 12 rather than −12, and gcd(0, 7) = 7 rather than 0, since every number divides 0 and 7 is the largest number dividing 7. Only gcd(0, 0) has no answer.
Check any GCD answer in 1 pass: divide every input by the result and confirm each division leaves a remainder of 0. 48 ÷ 6 = 8, 180 ÷ 6 = 30 and 210 ÷ 6 = 35 all come out exact, so 6 is a common divisor — and the Euclidean algorithm guarantees no larger one exists. The remainder calculator runs any of those checks on its own, and the divisibility rule checker confirms the same fact straight from the digits.