Math

GCD & LCM Calculator

What this does

Find the greatest common divisor of two integers with Euclid’s algorithm, plus the least common multiple derived from it.

Enter your details

Runs in your browser

Calculator inputs

How to use it

Using the gcd & lcm calculator

  1. 01

    Enter two whole integers

    Any magnitude up to about 15 digits works instantly.

  2. 02

    Read the GCD

    That is the largest integer dividing both inputs evenly.

  3. 03

    Use the LCM row

    Smallest number both inputs divide into; handy for adding fractions or aligning cycles.

Good to know

Why Euclid still wins after 2,300 years

One modulo operation per step shrinks the problem geometrically, so even 20-digit pairs finish in a handful of iterations. It is among the oldest recorded algorithms and remains the fastest practical method in every programming language.

Fractions and gears

Adding 5/18 + 7/48 wants the LCM as a common denominator; simplifying 48/18 wants the GCD. The same pair of numbers answers both directions, which is why this calculator always reports both.

Where you meet them outside class

Event scheduling (two buses every 12 and 18 minutes meet every LCM 36 minutes), gear tooth design, cryptographic key checks and music rhythm alignment all reduce to GCD/LCM questions.

How it's calculated

The math behind this calculator

GCD: Euclid’s algorithm; GCD(a, b) = GCD(b, a mod b) LCM = |a × b| / GCD(a, b)

Euclid’s algorithm repeatedly replaces the pair (a, b) with (b, a mod b) until the remainder hits zero; the surviving value is the greatest common divisor. The LCM then falls out for free from the identity |a×b| = GCD × LCM, dividing out the shared factors so nothing is double-counted.

Assumptions & limitations

  • Inputs must be non-zero integers within ±10¹⁵ to keep products exact.
  • Signs are ignored; results are positive by convention.
  • Both GCD and LCM are always shown together.

Worked example

For 48 and 18, Euclid reduces (48,18) → (18,12) → (12,6) → (6,0), giving GCD 6; and the LCM follows as 144.

FAQ

Frequently asked questions

Does order matter?
No; GCD and LCM are symmetric in their two arguments.
Can I use negative numbers?
Results are defined on magnitudes; the calculator reports the positive value regardless of input signs.
What if both numbers share no common factor?
They always share 1, so coprime inputs simply return GCD 1 and LCM equal to their product.
Why is my huge product slightly off?
Beyond roughly 10¹⁵ floating-point multiplication loses exactness; the calculator caps inputs to stay exact.

Keep exploring

Related calculators