GCD & LCM calculator
Find the GCD and LCM of a list of integers, with prime factorisation, Euclid steps, Bézout coefficients, continued-fraction expansion and the reduced ratio.
Runs in your browserEvery computation happens in your browser — your data never leaves this device.
Result
Everything runs on BigInt, so even integers far beyond the safe float range stay exact. Prime factorisation is limited to 10^12.
67212 = 2^2 × 3 18 = 2 × 3^2 24 = 2^3 × 3
What this tool does
- Reduce a fraction or a ratio: take the GCD of numerator and denominator, then divide both by it.
- Find a common period with the LCM — when two gears, schedules or loops line up again.
- Check your homework steps: the Euclidean divisions and the prime factorisation are printed line by line.
- Explore the theory behind modular inverses: Bézout coefficients and continued fractions are the building blocks of the extended Euclidean algorithm.
Example
Input
12 18 24
Output
GCD = 6, LCM = 72, factorisation: 12 = 2^2 × 3, 18 = 2 × 3^2, 24 = 2^3 × 3
The Euclidean steps, Bézout coefficients and the continued fraction are only shown for exactly two numbers; with more inputs you get the GCD, the LCM and the factorisations.
Frequently asked questions
Can large integers be wrong?
No. Every intermediate value is a BigInt, so the results stay exact well past 2^53. Only prime factorisation is capped at 10^12, because larger inputs would need Pollard-Rho style algorithms and would visibly stall the page.
Are negative numbers and decimals supported?
Negatives are fine — the GCD and LCM work on absolute values and the factorisation adds a -1 factor. Decimals are rejected: turn them into a fraction and enter the numerator and denominator instead.
How does the LCM avoid overflow?
It divides by the GCD first: |a ÷ gcd × b|. That keeps the intermediate value small. Because everything is a BigInt it would still be correct without that trick, but this way it is also cheap.
Are Bézout coefficients unique?
No. There are infinitely many pairs satisfying a·x + b·y = gcd(a, b); they differ by multiples of (b/g, -a/g). The pair shown here is the one the extended Euclidean algorithm produces, which is the smallest in absolute value.
What is the continued fraction good for?
It is the standard way to find the best rational approximations of a number: the convergents approach the true value alternately from below and above. It is the same process as the Euclidean algorithm, just recording the quotients.
Keywords：gcdlcmgreatest common divisorleast common multipleeuclidean algorithmbezoutprime factorizationcontinued fraction最大公约数最小公倍数质因数分解辗转相除法约分