standarddeviationcalculator.net

Updated Free · runs in your browser

Math

GCD and LCM calculator

Enter two or more whole numbers to get their greatest common divisor and least common multiple, worked two ways. For exactly two numbers the calculator also finds the Bézout coefficients.

Two or more, separated by commas or spaces. Bézout coefficients are shown when there are exactly two.

GCD and LCM of 252, 198 GCD 18, LCM 2,772
GCD (HCF)18
LCM2,772
Check: GCD × LCM = |a × b|18 × 2,772 = 49,896
Coprime (GCD = 1)?no
Bézout coefficientsx = 4, y = −5
Exponent of each prime in each number
Prime252198GCD (lowest)LCM (highest)
22112
32222
71001
110101
Extended Euclidean algorithm: each row is r = s × 252 + t × 198
Quotient qRemainder rst
—25210
—19801
1541−1
336−34
1184−5
20−1114
Show the working, step by step

  1. Euclidean algorithm on 252 and 198. Divide, then divide the divisor by the remainder, until the remainder is 0. The last non-zero remainder is the GCD.

    252 = 1 × 198 + 54 198 = 3 × 54 + 36 54 = 1 × 36 + 18 36 = 2 × 18 + 0 GCD(252, 198) = 18

  2. LCM from the GCD: the product divided by the GCD.

    LCM = 252 × 198 ÷ 18 = 49,896 ÷ 18 = 2,772

  3. Check by prime factorisation.

    252 = 2² × 3² × 7 198 = 2 × 3² × 11

  4. GCD: take each prime to the lowest power it appears with in every number (a prime missing from any number counts as power 0).

    GCD = 2 × 3² = 18

  5. LCM: take each prime to the highest power it appears with in any number.

    LCM = 2² × 3² × 7 × 11 = 2,772

  6. Bézout’s identity: run the Euclidean algorithm again, tracking s and t so that every remainder equals s × 252 + t × 198. Each new row is the row two above minus q times the row above. The row with the GCD gives the coefficients.

    252 × (4) + 198 × (−5) = 1,008 − 990 = 18

The formulas

GCD(a, b) = GCD(b, a mod b), GCD(a, 0) = a LCM(a, b) = |a × b| ÷ GCD(a, b) a·x + b·y = GCD(a, b) (Bézout)

Method 1: the Euclidean algorithm

For the default numbers 252 and 198:

252 = 1 × 198 + 54 198 = 3 × 54 + 36 54 = 1 × 36 + 18 36 = 2 × 18 + 0

The last non-zero remainder is 18. Then LCM = 252 × 198 ÷ 18 = 49,896 ÷ 18 = 2,772. The algorithm needs very few steps even for huge numbers, which is why computers use it rather than factorising.

Method 2: prime factorisation

252 = 2² × 3² × 7 and 198 = 2 × 3² × 11. Line up the exponents:

Prime252198GCD (lowest)LCM (highest)
22112
32222
71001
110101

GCD = 2 × 3² = 18 and LCM = 2² × 3² × 7 × 11 = 2,772. This method shows why the answers are what they are, and it extends to any number of inputs at once.

Bézout coefficients

The extended Euclidean algorithm tracks, for every remainder, how to write it as a combination of 252 and 198. The remainder 18 turns out to be 4 × 252 − 5 × 198, so the coefficients are x = 4 and y = −5. They are not unique: adding 11 to x and subtracting 14 from y (198 ÷ 18 and 252 ÷ 18) gives another pair.

Why the Euclidean algorithm is correct

If d divides both a and b, it divides a − q·b for any q, and in particular the remainder a mod b. The reverse is also true, so the pairs (a, b) and (b, a mod b) have exactly the same common divisors, and so the same greatest one. The remainders shrink every step, so the process must reach 0, and GCD(g, 0) = g. The number of steps grows only with the number of digits: two 100-digit numbers need at most a few hundred divisions.

Where you meet them

  • GCD: simplifying fractions and ratios, cutting things into the largest equal pieces.
  • LCM: common denominators, and when repeating events coincide (buses every 12 and 18 minutes meet every 36).
  • Bézout: modular inverses, solving linear Diophantine equations, and RSA key generation.

Common questions

What are the GCD and LCM?

The greatest common divisor (GCD, also called the highest common factor, HCF, or greatest common factor, GCF) is the largest number that divides all the numbers exactly. The least common multiple (LCM) is the smallest positive number they all divide into. For 252 and 198 the GCD is 18 and the LCM is 2,772.

How does the Euclidean algorithm work?

Divide the larger number by the smaller, then divide the smaller by the remainder, and keep going until the remainder is 0. The last non-zero remainder is the GCD. For 252 and 198: 252 = 1 × 198 + 54, 198 = 3 × 54 + 36, 54 = 1 × 36 + 18, 36 = 2 × 18 + 0, so the GCD is 18. It works because any common divisor of two numbers also divides their remainder.

How do I find the LCM from the GCD?

For two numbers, LCM(a, b) = a × b ÷ GCD(a, b). So LCM(252, 198) = 49,896 ÷ 18 = 2,772. For three or more numbers, apply it two at a time: LCM(a, b, c) = LCM(LCM(a, b), c).

What are Bézout coefficients?

Whole numbers x and y with a·x + b·y = GCD(a, b). They always exist, and the extended Euclidean algorithm finds them. For 252 and 198, x = 4 and y = −5: 252 × 4 − 198 × 5 = 1,008 − 990 = 18. When the GCD is 1, x is the modular inverse of a mod b, which is how inverses are computed in cryptography.

What does it mean if the GCD is 1?

The numbers are coprime (relatively prime): they share no prime factor. Their LCM is then simply their product. 8 and 15 are coprime even though neither is prime.

Written and reviewed by our editorial team. Last updated . Method and sources: how these numbers are computed.