Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 40 ยท Math Foundations

GCD and the Extended Euclidean Algorithm

Compute the greatest common divisor with Euclid's algorithm, find Bezout coefficients with the extended version and use it to build modular inverses by hand.

The greatest common divisor (GCD) of two integers is the largest number that divides both of them. The GCD of 12 and 18 is 6; the GCD of 8 and 15 is 1. It looks like schoolbook material, but it is one of the most-used tools in cryptography. The GCD tells you whether a modular inverse exists, it lets you test whether two RSA moduli share a prime factor, and the algorithm that computes it also produces the inverse itself.

That algorithm is over 2,300 years old and is credited to Euclid. It is fast even for numbers with thousands of digits, and it never needs to factor anything, which is the crucial point: factoring is hard, but GCD is easy. In this lesson you will write it, extend it to find Bezout coefficients, and use it to compute inverses without pow(a, -1, m).

Euclid's algorithm

The key observation: any number that divides both a and b also divides a - b, and more generally a mod b. So gcd(a, b) = gcd(b, a mod b). Repeat until the remainder is 0; the last non-zero value is the answer.

For example, gcd(252, 105):

  • 252 = 2 x 105 + 42, so gcd(252, 105) = gcd(105, 42)
  • 105 = 2 x 42 + 21, so gcd(105, 42) = gcd(42, 21)
  • 42 = 2 x 21 + 0, so the answer is 21.
Python Euclid's algorithm

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 loop shrinks the numbers quickly: after two steps the larger value is at least halved, so the number of steps is proportional to the number of digits, not to the size of the numbers. A 2048-bit gcd takes only a few thousand steps.

flowchart TD
    S["a, b"] --> Q{"b = 0 ?"}
    Q -- "yes" --> R["answer: a"]
    Q -- "no" --> T["a, b = b, a mod b"]
    T --> Q

Euclid's algorithm: swap and take the remainder until the second number reaches zero.

Two numbers whose GCD is 1 are called coprime (or relatively prime). Coprimality shows up everywhere: a number has an inverse modulo m exactly when it is coprime to m.

Bezout's identity

Here is a surprising fact. For any integers a and b, there exist integers x and y such that:

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

These numbers x and y are called the Bezout coefficients; one of them is usually negative. For example, 252 x (-2) + 105 x 5 = -504 + 525 = 21. The extended Euclidean algorithm finds them by carrying along the extra bookkeeping as it runs.

The idea: each remainder in Euclid's algorithm is a combination of a and b. Track, for every remainder, how many as and bs it contains. Start with a = 1*a + 0*b and b = 0*a + 1*b, and in each step subtract the quotient multiple of the previous line.

Python Extended Euclid 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.

Read the trace row by row: on each line, r = 252*x + 105*y. The final non-zero row gives the GCD together with its coefficients. The last row, where r becomes 0, is the stop signal.

Inverses without pow

Suppose gcd(a, m) = 1. Then Bezout gives a x + m y = 1 for some integers x and y. Reduce both sides modulo m: the m y term vanishes, leaving a x โ‰ก 1 (mod m). So x is the inverse of a, and the extended Euclidean algorithm computes it. If the GCD is bigger than 1, no inverse exists.

Python Modular inverse via extended 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.

This version is recursive, a compact way to write the same algorithm: extended_gcd(a, b) calls itself on (b, a mod b) and fixes up the coefficients on the way back. The value 2753 is the inverse of 17 modulo 3120, a pair used in a classic RSA demonstration that you will meet in RSA from scratch.

Note: In real code, call pow(a, -1, m). Knowing the extended Euclidean algorithm matters because you will meet it inside other algorithms (RSA key generation, elliptic-curve arithmetic, Chinese remaindering) and in languages or libraries that have no built-in inverse.

Solving linear congruences

An equation like 7x โ‰ก 3 (mod 26) is solved by multiplying both sides by the inverse of 7. The same idea solves any a x โ‰ก c (mod m) with gcd(a, m) = 1. This is exactly how the affine cipher is decrypted.

Python Solving a x = c (mod m)

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.

When the GCD g of a and m divides c, there are exactly g solutions. When it does not, there are none. This case analysis returns in the Chinese remainder theorem.

Why GCD matters for security

GCD is also an attack tool. If two RSA public keys were generated by a device with poor randomness, they might accidentally share one of their two prime factors. Factoring either modulus is infeasible, but the GCD of the two moduli instantly reveals the shared prime. Researchers have found real-world keys broken this way. You will see this in RSA padding and common pitfalls.

Python A shared prime gives it all away

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.

Euclid's algorithm needed no factoring at all. That makes it a classic example of the gap between a hard problem (factoring one number) and an easy one (finding a common factor of two numbers).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

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

    48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0. The last non-zero value is 6.
  2. 2. What does Bezout's identity say?

    Bezout coefficients x and y always exist, and the extended Euclidean algorithm finds them.
  3. 3. How does the extended Euclidean algorithm give the inverse of a modulo m?

    When gcd(a, m) = 1, ax + my = 1. Modulo m, the m*y term disappears, so x is the inverse.
  4. 4. Two RSA moduli n1 and n2 have gcd(n1, n2) greater than 1. What follows?

    The GCD is the shared prime. Dividing each modulus by it reveals the other prime, so both private keys can be computed.

Summary

  • Euclid's algorithm computes gcd(a, b) by repeating a, b = b, a mod b; it is fast and needs no factoring.
  • Coprime numbers have GCD 1; an inverse mod m exists exactly for numbers coprime to m.
  • The extended Euclidean algorithm also returns Bezout coefficients x, y with a*x + b*y = gcd(a, b).
  • Reducing Bezout's identity mod m gives the modular inverse; pow(a, -1, m) does this for you.
  • GCD can break keys that accidentally share a prime factor.

Next: Primes and Primality Testing.