GCD and LCM Calculator With Prime Factors and Modular Inverse

Greatest common divisor, least common multiple, prime factors, divisors, next prime and modular inverse of two whole numbers.

Calculated from standard textbook formulas, with every step shown. The formulas are fixed, so the working does not need checking: what matters is the numbers you type in. Use these calculators only if you are competent to choose the inputs (loads, material strength, dimensions, supports) and check your units and assumptions. For learning and checking your own working: design and sign-off are for a qualified engineer. Drafting Central does not store the numbers you type.

How this calculator works

Enter two whole numbers. The calculator finds the greatest common divisor (GCD) with Euclid's method, showing the divisions, and the least common multiple (LCM) from a b divided by the GCD. It also factorises each number into primes and counts its divisors.

If the two numbers are coprime (GCD of 1), it also gives the modular inverse: the number x with a x equal to 1 more than a multiple of b. That is the core of the RSA cryptosystem and of solving linear congruences.

Useful for cancelling fractions, finding when two repeating cycles line up (gear teeth, schedules, blinking lights), and checking whether a number is prime.

Formulas used

  • \gcd(a,b) = \gcd(b,\ a \bmod b)
  • \operatorname{lcm}(a,b) = \frac{ab}{\gcd(a,b)}
  • a\,x \equiv 1 \pmod{b}

Worked example

With the default numbers in the calculator above:

  1. Euclid's method: divide, then divide the divisor by the remainder: 2 divisions, last divisor 12
  2. Greatest common divisor: 12
  3. Least common multiple: 252
  4. Prime factors of a: 2^2 x 3 x 7
  5. Prime factors of b: 2^2 x 3^2
  6. Number of divisors of a and of b: 12 and 9
  7. Next prime above a: 89
  8. Remainder of a divided by b: 12

Change the numbers in the calculator to see the full working, every step, for your own case.

A second worked example

A different case, with these numbers: First whole number a 17; Second whole number b 5.

  1. Euclid's method: divide, then divide the divisor by the remainder: 3 divisions, last divisor 1
  2. Greatest common divisor: 1
  3. Least common multiple: 85
  4. Prime factors of a: 17 is prime
  5. Prime factors of b: 5 is prime
  6. Number of divisors of a and of b: 2 and 2
  7. Next prime above a: 19
  8. Remainder of a divided by b: 2
  9. Modular inverse of a, modulo b: 3

Common questions

What is the difference between GCD and LCM?

The GCD is the biggest number that divides both. The LCM is the smallest number that both divide into.

How big can the numbers be?

Up to 1,000,000,000 (one billion).

Why is there sometimes no modular inverse?

An inverse of a modulo b exists only when a and b have no common factor, that is, when their GCD is 1.

Related calculators

Got a question about this? Ask an engineering question and get a plain-language answer with references.

Further reading: Euclid, Elements Book VII; any number theory text (the Euclidean algorithm and modular arithmetic).

Need a calculator we do not have?

Tell us what you would like to calculate. We read every request and build the most asked-for ones.

We store your request (and your email if you give it) to decide what to build. We do not store the numbers you type into calculators.

Embed this calculator on your own page

Copy this code into your page. The calculator runs inside the frame and links back to Drafting Central.

Need this drawn, designed or checked?

Drafting Central is a mechanical engineering and drafting business working with customers across Australia and around the world. A calculator gives you the numbers; we can turn them into drawings and designs.

Need help with a real project?

Talk to Drafting Central →

← All engineering calculators