Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 68 · Number Theory

GCD, LCM and the Euclidean Algorithm

Compute the greatest common divisor and least common multiple, trace Euclid's algorithm, use the extended version for Bezout coefficients, and see why it is fast.

The greatest common divisor of two integers is the largest integer that divides both. It sounds like a small idea, yet it sits underneath fractions in lowest terms, repeating schedules, modular inverses and the key generation in public-key cryptography. The remarkable part is that you can find it without factoring either number, using a procedure more than two thousand years old: the Euclidean algorithm.

In this lesson you will define the gcd and the least common multiple, trace Euclid's algorithm step by step, extend it to find the integer combination that produces the gcd (Bezout's identity), and see why it needs only a handful of steps even for enormous numbers. You should be comfortable with divisibility from Divisibility and Primes.

GCD and LCM

For integers a and b that are not both zero, gcd(a, b) is the largest positive integer that divides both. For example the divisors of 252 include 1, 2, 3, 4, 6, 7, 9, 12, 14, 18, ... and the divisors of 198 include 1, 2, 3, 6, 9, 11, 18, ...; the largest they share is 18. Two numbers with gcd 1 are called coprime (or relatively prime), like 35 and 12: they share no prime factor.

The least common multiple lcm(a, b) is the smallest positive integer that both a and b divide. It is the length of the combined cycle when one event repeats every a days and another every b days. The two quantities are tied together by a neat identity for positive integers:

gcd(a, b) · lcm(a, b) = a · b

so once you have the gcd, the lcm costs one division: a // gcd * b. Dividing first keeps the intermediate numbers small.

gcd and lcm side by side

gcd Largest number dividing both.
lcm Smallest number both divide.
The link gcd times lcm equals a times b.

Coprime means gcd is 1, so the lcm is just the product.

1 / 2

The most direct way to get a gcd is to try every candidate from the smaller number downward. That works for small inputs and is a good reference for checking the clever method.

Euclid's algorithm

Euclid noticed that any number dividing both a and b also divides the remainder when a is divided by b. Write a = b·q + r with 0 ≤ r < b. A common divisor of a and b divides a − b·q = r, and a common divisor of b and r divides b·q + r = a. So the pairs (a, b) and (b, r) have exactly the same common divisors, hence the same gcd:

gcd(a, b) = gcd(b, a mod b)

Repeat until the remainder is 0. If r = 0 then b divides a, so gcd(a, b) = b, and the last nonzero remainder is the answer.

Python Brute force versus Euclid

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The trace shows four divisions, ending with remainder 0 after 36 = 18 · 2. The brute-force version looped 198 times; Euclid did four divisions. Python ships both operations in the math module: math.gcd accepts any number of arguments, treats gcd(0, n) as n, and math.lcm does the same for the least common multiple.

Why it is fast

Each step replaces (a, b) by (b, a mod b), and the remainder is smaller than b. A closer look shows that every two steps at least halve the larger number, so the number of divisions is at most about 2·log₂(b). For a 1,000-digit number that is a few thousand steps, not 10^1000.

The slowest inputs are consecutive Fibonacci numbers, because each quotient is 1 and the remainders shrink as slowly as possible. The next example measures the steps.

Python Worst case: Fibonacci numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The most steps for any pair below 100 is 9, reached by the Fibonacci pair 89 and 55. Every extra step costs a larger Fibonacci number, which is exactly the logarithmic growth the bound promises.

Bezout's identity and the extended algorithm

Euclid's algorithm can do more than report the gcd. Bezout's identity says that for any integers a and b there are integers x and y with

a·x + b·y = gcd(a, b)

The numbers x and y can be negative and are not unique. The extended Euclidean algorithm finds one pair by working backward through the division steps. A recursive version is short. If b = 0 then gcd = a with x = 1, y = 0. Otherwise compute (g, x', y') for the pair (b, a mod b), which satisfies b·x' + (a mod b)·y' = g. Since a mod b = a − (a // b)·b, substituting gives a·y' + b·(x' − (a // b)·y') = g, so x = y' and y = x' − (a // b)·y'.

Python Extended Euclid and Bezout coefficients

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The identity gcd · lcm = a · b holds for all 1,521 pairs tested, which is a nice check but not a proof. It follows from prime factorizations: gcd takes the smaller exponent of each prime and lcm the larger, and min + max equals the sum of the two exponents.

Bezout's identity solves linear Diophantine equations: a·x + b·y = c has integer solutions exactly when gcd(a, b) divides c. For 6x + 10y = 8 the gcd is 2, which divides 8, so solutions exist; egcd(6, 10) gives 6·2 + 10·(−1) = 2, and multiplying by 4 gives 6·8 + 10·(−4) = 8. The same coefficients give modular inverses in Modular Arithmetic.

A gcd of 1 is the condition for an inverse modulo n to exist, which is why coprimality appears all over cryptography.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What is gcd(48, 18)?

    48 = 18 * 2 + 12, 18 = 12 * 1 + 6, 12 = 6 * 2 + 0, so the last nonzero remainder is 6.
  2. 2. If gcd(a, b) = 4 and a = 20, b = 28, what is lcm(a, b)?

    gcd * lcm = a * b, so lcm = 20 * 28 / 4 = 140.
  3. 3. Why does gcd(a, b) = gcd(b, a mod b) hold?

    A common divisor of a and b divides a - bq = a mod b, and a common divisor of b and a mod b divides bq + r = a. The sets of common divisors are identical.
  4. 4. For which c does 6x + 10y = c have integer solutions?

    The gcd of 6 and 10 is 2, and a linear Diophantine equation is solvable exactly when the gcd divides c.
  5. 5. Which inputs make Euclid's algorithm slowest for numbers of a given size?

    Consecutive Fibonacci numbers give a quotient of 1 at every step, so the remainders shrink as slowly as possible.

Summary

  • gcd(a, b) is the largest common divisor; lcm(a, b) is the smallest common multiple; gcd · lcm = a · b for positive integers.
  • Euclid's algorithm uses gcd(a, b) = gcd(b, a mod b) and stops when the remainder is 0.
  • The number of steps grows with the logarithm of the inputs; consecutive Fibonacci numbers are the worst case.
  • Bezout's identity says a·x + b·y = gcd(a, b) has integer solutions, and the extended algorithm finds them.
  • math.gcd and math.lcm do the job in Python; write egcd yourself when you need the coefficients.

Next: Modular Arithmetic, where Bezout coefficients become inverses.