Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 37 ยท Divisibility and Primes

Extended Euclid and Bezout's Identity

Prove Bezout's identity ax + by = gcd(a, b), compute the coefficients with the extended Euclidean algorithm, and use them to prove Euclid's lemma. Python code included.

Euclid's algorithm tells you the gcd of two numbers. The extended version tells you more: it finds integers x and y such that

aยทx + bยทy = gcd(a, b).

This statement is Bezout's identity, and it is the key that unlocks the rest of the course. It proves that primes behave well in products, it solves linear equations in integers, and it computes modular inverses, which are the heart of RSA.

Bezout's identity

Theorem. For integers a and b, not both zero, there exist integers x, y with ax + by = gcd(a, b). Moreover gcd(a, b) is the smallest positive integer that can be written as ax + by.

Proof. Consider the set S of all positive integers of the form ax + by. It is non-empty, so by well-ordering it has a smallest member d = axโ‚€ + byโ‚€. Divide a by d: a = dq + r with 0 โ‰ค r < d. Then r = a โˆ’ dq = a(1 โˆ’ qxโ‚€) + b(โˆ’qyโ‚€) is also of the form ax + by. If r > 0 it would be a smaller member of S, contradiction. So r = 0 and d | a. The same argument gives d | b. So d is a common divisor. And any common divisor c of a and b divides axโ‚€ + byโ‚€ = d, so c โ‰ค d. Thus d is the greatest common divisor. โˆŽ

Computing x and y

Run Euclid's algorithm, but track at every step how the current remainder is made from a and b. Start with rโ‚€ = a = aยท1 + bยท0 and rโ‚ = b = aยท0 + bยท1. Each new remainder is rโ‚–โ‚Šโ‚ = rโ‚–โ‚‹โ‚ โˆ’ qยทrโ‚–, and the coefficients follow the same recurrence.

Python Extended Euclid with a table

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 240 and 46 the gcd is 2 and one solution is x = โˆ’9, y = 47, because 240ยท(โˆ’9) + 46ยท47 = โˆ’2160 + 2162 = 2. The pair (x, y) is not unique: if (x, y) works, so does (x + 46k/2, y โˆ’ 240k/2) for every integer k, because the added terms cancel.

Python Many solutions, all valid

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 lemma

Bezout's identity gives the property that makes primes special.

Euclid's lemma. If a prime p divides a product ab, then p | a or p | b.

Proof. Suppose p โˆค a. Since p is prime, gcd(p, a) = 1 (its only positive divisors are 1 and p, and p does not divide a). By Bezout, px + ay = 1 for some x, y. Multiply by b: pbx + aby = b. Now p divides pbx and p divides abยทy, so p divides their sum, which is b. โˆŽ

This fails for composite numbers: 6 | 2ยท3 but 6 divides neither factor. Euclid's lemma is the missing ingredient that proves unique factorization, which comes in the next lesson.

A generalization: coprime to a product

If gcd(a, m) = 1 and gcd(b, m) = 1 then gcd(ab, m) = 1. Proof: write ax + my = 1 and bu + mv = 1, then multiply: ab(xu) + m(...) = 1, so the combination equals 1 and the gcd divides 1. In the same way, if m | ab and gcd(m, a) = 1, then m | b.

Inverses mod m

Suppose gcd(a, m) = 1. Then ax + my = 1, and taking this equation modulo m gives ax โ‰ก 1, so x is a multiplicative inverse of a modulo m. That is exactly how pow(a, -1, m) works. Later chapters use this heavily, but you can already compute one.

Python Modular inverse from egcd

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 recursive version above reads like the algorithm: gcd(b, a mod b) = bยทx + (a mod b)ยทy, and since a mod b = a โˆ’ (a // b)ยทb, a little algebra gives the update for the coefficients of a and b.

Check against sympy

Python Cross-check egcd on random inputs

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.

Bezout in four facts

Identity ax + by = gcd(a, b).
Algorithm Extend Euclid and track x and y.
Euclid's lemma A prime dividing ab divides a or b.
Inverses x is the inverse of a mod m.
1 / 2

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Bezout's identity says that ax + by = gcd(a, b)...

    There are always integer solutions, and infinitely many of them.
  2. 2. Find x with 3x = 1 (mod 11).

    3 * 4 = 12, and 12 = 1 (mod 11), so 4 is the inverse of 3.
  3. 3. Which statement is false?

    6 | 2*3 but 6 divides neither 2 nor 3, so Euclid's lemma needs a prime.
  4. 4. Given 240*(-9) + 46*47 = 2, what other pair solves 240x + 46y = 2?

    Adding 46/2 = 23 to x and subtracting 240/2 = 120 from y gives (14, -73).

Summary

  • Bezout: ax + by = gcd(a, b) always has integer solutions, and the gcd is the smallest positive such value.
  • The extended Euclidean algorithm tracks coefficients alongside the remainders.
  • Euclid's lemma (a prime dividing ab divides a or b) follows from Bezout and fails for composites.
  • If gcd(a, m) = 1, the x in ax + my = 1 is the inverse of a modulo m.
  • Solutions (x, y) are not unique: shift by (b/g, โˆ’a/g).

Next: The Fundamental Theorem of Arithmetic