GCD and LCM Calculator

Enter two whole numbers and the calculator returns their greatest common divisor and least common multiple side by side. Results update as you type. The greatest common divisor is the largest whole number that divides both inputs exactly; the least common multiple is the smallest whole number that both inputs divide into. Decimal entries are refused rather than rounded, because both quantities are only defined for integers. The least common multiple is worked out in exact integer arithmetic and shown with thousands separators, so it stays right to the last digit however large it grows.

How Euclid's algorithm finds the GCD

The calculator uses the Euclidean algorithm. Divide the larger number by the smaller and keep the remainder. Then divide the previous divisor by that remainder. Repeat until the remainder reaches zero; the last remainder before that is the GCD.

With the defaults, 36 and 60:

1. 60 ÷ 36 = 1 remainder 24
2. 36 ÷ 24 = 1 remainder 12
3. 24 ÷ 12 = 2 remainder 0

The last non-zero remainder is 12, so gcd(36, 60) = 12. Three divisions replace the chore of listing every divisor of both numbers and comparing the two lists. The saving grows sharply with size. Gabriel Lamé proved in 1844 that the algorithm never needs more than five times as many division steps as the smaller number has digits in base ten, a result often cited as the first theorem in what became computational complexity theory.

A method older than the man it is named for

Euclid set the procedure down in the Elements around 300 BC, in Book VII, Propositions 1 and 2 for whole numbers, and again in Book X, Propositions 2 and 3, for geometric magnitudes that share a common measure. Euclid was a compiler as much as an inventor, and this algorithm was almost certainly not his own discovery. The underlying idea belongs to earlier Greek geometry, where it was called anthyphairesis, or reciprocal subtraction: repeatedly taking the smaller quantity away from the larger. The term appears in the works of both Euclid and Aristotle, and the technique was probably known to Eudoxus of Cnidus around 375 BC, some seventy-five years before Euclid wrote.

The same reasoning surfaced far from Greece. The Indian astronomer Aryabhata, born in 476 and writing in the late fifth century, set out a version in the Aryabhatiya under the name kuttaka, Sanskrit for pulverizer, and used it to find whole-number solutions of linear equations of the form ax + by = c. His account was terse enough that Bhaskara I had to expand it with worked astronomical examples a century afterwards. In China, Qin Jiushao gave a general rule for simultaneous remainder problems, the dayan procedure behind what is now called the Chinese remainder theorem, in his Mathematical Treatise in Nine Sections of 1247. Much later the algorithm broke out of pure number theory: Charles Sturm showed in 1829 that applying it to a polynomial and its derivative yields a chain that counts the real roots in any chosen interval, so a rule built for integers carried over almost unchanged into algebra. Few procedures have stayed in continuous everyday use for more than two thousand years; this is one of them.

Getting the LCM from the GCD

Once the GCD is known, the least common multiple follows from a single identity — the product of two positive integers always equals the product of their GCD and their LCM:

lcm(x, y) = x × y ÷ gcd(x, y)

For the defaults that is 36 × 60 = 2,160, and 2,160 ÷ 12 = 180. A quick check confirms it: 180 = 5 × 36 and 180 = 3 × 60, and no smaller number is a multiple of both. Computing the LCM this way is a deliberate shortcut. Finding it directly would mean listing multiples of each number until they first agree, which is slow; reusing the GCD from Euclid's three quick divisions turns the whole job into one multiplication and one division. That multiplication runs in exact arbitrary-precision integer arithmetic rather than ordinary floating-point numbers, so 123,456,789 and 987,654,321 return 13,548,070,123,626,141 exactly rather than a figure quietly rounded in its last digits.

The prime-factorization alternative

There is an older and more visual way to reach both answers: break each number into its prime factors. Writing 36 = 2² × 3² and 60 = 2² × 3 × 5, the GCD takes each shared prime to the lower of its two powers, giving 2² × 3 = 12, while the LCM takes every prime that appears in either number to the higher power, giving 2² × 3² × 5 = 180. The two approaches always agree, because the fundamental theorem of arithmetic guarantees that every whole number above 1 has exactly one prime factorization, apart from the order in which the factors are written.

Factoring is easy to picture and works well for small numbers, but it hides a practical trap. No fast general method for factoring very large numbers is known, and modern cryptography leans on that difficulty. Euclid's algorithm sidesteps factoring completely — it never asks what the prime factors are — which is why it stays fast even when the inputs run to hundreds of digits.

Where these two numbers earn their keep

Reducing fractions is the classic GCD job. To put 36/60 in lowest terms, divide numerator and denominator by their GCD: 36 ÷ 12 = 3 and 60 ÷ 12 = 5, giving 3/5 in one move instead of repeated halving and thirding.

The LCM answers scheduling questions of the form "when do repeating events next coincide". If one bus leaves every 36 minutes and another every 60, both are at the stop together every 180 minutes. The same arithmetic sets gear ratios, aligns rotating work shifts, and finds the common denominator when adding fractions — the least common denominator of 1/36 and 1/60 is exactly lcm(36, 60) = 180. Because the product identity ties the two together, any tool that computes one has effectively computed the other.

One concept, several names

American classrooms mostly say greatest common factor (GCF). Schools in the UK, India, Australia and much of the Commonwealth teach highest common factor (HCF). University mathematics settles on greatest common divisor, usually written gcd. Older texts sometimes call it the greatest common measure, a phrase that still carries Euclid's geometric picture of a length that measures two others a whole number of times. All of these name the same computation, so material found under any of the labels applies equally, and the answer this calculator returns does not depend on which one you were taught.

Limits worth knowing

Both inputs must be at least 1; zero and negative entries are rejected rather than silently reinterpreted, since a negative sign does not change which whole numbers divide evenly and gcd with zero is a separate convention. The LCM itself has no size ceiling: it is computed with exact arbitrary-precision integer arithmetic, so however far the answer runs past the reach of ordinary floating-point numbers, every digit shown is right. Each entry does have to be a whole number the browser can hold exactly, meaning 9,007,199,254,740,991 or less — that is 2⁵³ − 1, the largest safe integer in the JavaScript number format — and anything larger is reported as an error rather than silently rounded. Two coprime entries just under that ceiling still produce an exact 32-digit least common multiple. Coprime pairs such as 8 and 15 share no factor beyond 1, so their GCD is 1, which makes their LCM the full product, 120. Consecutive whole numbers are coprime for the same reason, which is why a fraction like 20/21 is already in lowest terms.

Frequently asked questions

What is the GCD of 36 and 60?

It is 12. Euclid's algorithm gets there in three steps: 60 divided by 36 leaves remainder 24, 36 divided by 24 leaves remainder 12, and 24 divided by 12 leaves remainder 0. The last non-zero remainder, 12, is the answer.

How do you find the LCM if you already know the GCD?

Multiply the two numbers and divide by their GCD. For 36 and 60 that is 2160 divided by 12, which gives 180. This works because the product of any two positive integers always equals the product of their GCD and LCM.

Is the LCM still exact for very large numbers?

Yes. The least common multiple is built with exact arbitrary-precision integer arithmetic rather than ordinary decimal numbers, so nothing is rounded at any size. For 123,456,789 and 987,654,321 the GCD is 9 and the LCM is 13,548,070,123,626,141, a seventeen-digit answer given to the final digit. Each individual entry must still be 9,007,199,254,740,991 or less, but the multiple built from two such numbers has no ceiling.

Are GCF, HCF and GCD the same thing?

Yes, all three names refer to the same number. American schools usually say greatest common factor, schools in the UK, India and Australia say highest common factor, and mathematicians write gcd. The calculation is identical under every name.

What is the GCD of two numbers when one divides the other?

The smaller number itself, and the LCM is then simply the larger number. For 12 and 60 the GCD is 12 and the LCM is 60, because 60 is already a multiple of 12. This is the quickest special case to spot by eye.

Can the GCD of two numbers be 1?

Yes, and such numbers are called coprime. 8 and 15 share no factor beyond 1, so their GCD is 1 and their LCM is the full product, 120. Consecutive integers like 20 and 21 are always coprime.