Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 37 Β· Divisibility and Primes

GCD, LCM and the Euclidean Algorithm

Find the greatest common divisor and least common multiple, prove why Euclid's algorithm works, count its steps, and understand coprime numbers, with Python.

The greatest common divisor gcd(a, b) is the largest positive integer that divides both a and b. The least common multiple lcm(a, b) is the smallest positive integer that both divide. Two numbers with gcd 1 are called coprime (or relatively prime): they share no prime factor, like 8 and 15.

The Euclidean algorithm computes the gcd without factoring anything, and it is one of the oldest algorithms still in everyday use. This lesson proves why it works, measures how fast it is, and shows how lcm and coprimality follow from it.

Euclid's algorithm

Euclid's idea is that the pair (a, b) has the same common divisors as the pair (b, r), where r = a mod b. If d divides a and b, it divides a βˆ’ bq = r (by the linear-combination rule). If d divides b and r, it divides bq + r = a. Same common divisors, so same greatest one:

gcd(a, b) = gcd(b, a mod b), and gcd(a, 0) = a.

Repeat until the remainder is 0. Each step shrinks the numbers, so the process must stop.

Python Euclid's algorithm with a trace

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 for 1071 and 462 is 1071 = 462Β·2 + 147, 462 = 147Β·3 + 21, 147 = 21Β·7 + 0, so the gcd is 21. Three divisions, no factoring.

How fast is it?

LamΓ©'s theorem (1844) says the number of division steps is at most five times the number of decimal digits of the smaller number. The worst case is two consecutive Fibonacci numbers, because every quotient is 1 and the remainders shrink as slowly as possible. In practice, gcd of two 1000-digit numbers takes a few thousand steps.

Python Steps for Fibonacci pairs and random pairs

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.

For random 30-digit numbers the average is about 58 steps (theory predicts roughly 0.843 · ln of the number, which is 58 for 10³⁰), well under the worst case.

Properties of the gcd

For positive integers a, b, c:

  • gcd(a, b) = gcd(b, a), and gcd(a, a) = a.
  • gcd(ka, kb) = k Β· gcd(a, b).
  • If d = gcd(a, b), then a/d and b/d are coprime.
  • gcd(a, b) = gcd(a, b + ka) for any integer k, the heart of Euclid.
  • Multiplicativity trick: if gcd(a, b) = 1 and gcd(a, c) = 1 then gcd(a, bc) = 1.

For three or more numbers fold the function: gcd(a, b, c) = gcd(gcd(a, b), c). Python's math.gcd accepts any number of arguments.

From gcd to lcm

The least common multiple satisfies gcd(a, b) Β· lcm(a, b) = a Β· b for positive a and b. Compute it as a // gcd(a, b) * b, dividing first to keep numbers small. A real use: two traffic lights that repeat every 12 and 18 seconds both turn green together every lcm(12, 18) = 36 seconds.

Python lcm and the product identity

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.

Coprime numbers

Coprime pairs matter everywhere: fractions in lowest terms have coprime numerator and denominator, and a modular inverse of a mod m exists exactly when a and m are coprime. A surprising fact: if you pick two random positive integers, the probability that they are coprime is 6/π² β‰ˆ 0.6079.

Python How often are two numbers coprime?

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 two values agree to about two decimal places, a first glimpse of how primes and Ο€ are tied together. Primality and coprimality are related but different: 9 and 16 are both composite yet coprime.

Reducing fractions and Farey-style checks

To reduce 252/198 divide both parts by gcd(252, 198) = 18, giving 14/11. The fractions.Fraction class does this automatically.

Python Lowest terms by gcd

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.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What is gcd(1071, 462)?

    1071 = 4622 + 147, 462 = 1473 + 21, 147 = 21*7 + 0, so the gcd is 21.
  2. 2. Why does gcd(a, b) = gcd(b, a mod b)?

    A common divisor of a and b divides a - bq, and a common divisor of b and r divides bq + r.
  3. 3. If gcd(a, b) = 6, what is lcm(a, b) when a * b = 216?

    gcd * lcm = a * b, so lcm = 216 / 6 = 36.
  4. 4. Which input pair makes Euclid's algorithm slowest for its size?

    Every quotient is 1, so the remainders shrink as slowly as possible.

Summary

  • gcd(a, b) is the largest common divisor; a and b are coprime when it is 1.
  • Euclid's algorithm repeats gcd(a, b) = gcd(b, a mod b) until the remainder is 0.
  • The number of steps grows with the number of digits (LamΓ©), with Fibonacci pairs as the worst case.
  • gcd(a, b) Β· lcm(a, b) = a Β· b, so lcm = a // gcd * b.
  • Two random integers are coprime with probability about 6/π².

Next: Extended Euclid and Bezout's Identity