The greatest common divisor and lowest common multiple of any whole numbers at any size, with the Euclidean algorithm written out, Bezout coefficients, and the two answers checked against each other.
Initializing in your browser…
Whether a number is prime, at any size, decided by deterministic Miller-Rabin rather than trial division. Prime factorisation, every divisor, the primes either side and Goldbach pairs.
Exact arithmetic on rationals, with both evaluation conventions named and the precedence table the parser runs on printed on the page.
Plot functions with a real expression parser, poles drawn as gaps, and roots, turning points and integrals found by bracketing with the check printed.
You need the lowest common multiple of 123,456,789 and 987,654,321.
Numbers
123456789 and 987654321
Result
GCD = 9, LCM = 13,548,070,123,626,141
The textbook formula for an LCM is |a x b| / gcd, and it overflows here: the product is 121,932,631,112,635,269, past the 2^53 a double holds exactly, so that formula returns 13,548,070,123,626,140. One short, and completely plausible. Dividing FIRST, as |a| / gcd x |b|, is exact, and the arithmetic is on whole numbers with no size limit. The page checks itself: gcd x lcm must equal the product of the two numbers, and both sides are computed and compared rather than the identity being printed as a fact. Underneath, the Euclidean algorithm is written out line by line, the Bezout coefficients x and y with ax + by = gcd are given, and the common divisors are listed, which are exactly the divisors of the GCD.
The greatest common divisor and the lowest common multiple of any set of whole numbers, at any size, with the Euclidean algorithm written out step by step and the answers checked against each other.
The lowest common multiple is computed as |a| divided by the GCD, then multiplied by |b|. Doing the division FIRST is the whole thing: the textbook formula |a x b| / gcd overflows, and it overflows quietly. The product of 123,456,789 and 987,654,321 is 121,932,631,112,635,269, which is past the 2^53 a double can hold exactly, so the answer comes back as 13,548,070,123,626,140 where the truth is 13,548,070,123,626,141. Off by one, entirely plausible, and impossible to notice. Everything here is on whole numbers of unlimited size, so an eighteen-digit input is as exact as a two-digit one, and every digit of the answer is shown rather than an exponent.
**The working, four ways.** The Euclidean algorithm is written out line by line, each as "a = q x b + r", down to the zero remainder whose predecessor is the GCD. The prime factorisation of every number is shown, because that is the other way to see the answer: the GCD takes the lowest power of every prime they share and the LCM the highest power of every prime any of them has. The common divisors are listed, and they are exactly the divisors of the GCD, which is what makes it the greatest of them. And Bezout's identity gives whole numbers x and y with ax + by = gcd, which is the part of a GCD that actually gets used: it is how a modular inverse is found and how a linear equation is solved in whole numbers.
**It checks itself.** For two numbers, gcd x lcm must equal the product of the two, always. The page computes both sides and says whether they agree, so the claim is a measurement on this calculation rather than a fact printed next to it.
**Zero is computed rather than dropped.** gcd(0, n) is n, because every number divides zero, and lcm(0, n) is 0, because nothing but zero is a multiple of zero. Both are defined and both are answered. A number that is not whole is refused by name, because a common divisor is a question about whole numbers.
The GCD of the numerator and denominator is what you divide both by.
The LCM of the denominators is the lowest common denominator.
Two events every 12 and 18 units line up every 36, which is their LCM.
The Bezout coefficients give a modular inverse directly, which is what a GCD is for in cryptography.
Every line of the Euclidean algorithm is on the page in the form it is written by hand.
Any size. The arithmetic is on whole numbers with no 53-bit limit, which matters more than it sounds: computing an LCM as |a x b| / gcd gives a wrong answer for two nine-digit inputs, and the wrong answer looks right.
The number itself, because every number divides zero. The LCM of zero and anything is zero, because nothing else is a multiple of zero. Both are computed here rather than refused.
It gives whole numbers x and y with ax + by = gcd(a, b). That is how a modular inverse is computed and how a linear equation is solved in whole numbers, and it is the reason the extended algorithm exists.
Because they are the same answer seen differently: the GCD takes the lowest power of each shared prime and the LCM the highest power of each prime present. Seeing both makes the result checkable by eye.
That the only number dividing both is one, so their GCD is 1 and their LCM is their product. The page says so when it happens.
Every calculation runs locally in your browser. Your numbers and expressions are not transmitted or stored.