1
The gcd is the smallest positive combination
{ax + by} over all integers x, y is exactly the set of multiples of gcd(a,b), so the gcd is its smallest positive member.
Lesson · Number Theory and Cryptography · The Euclidean algorithm
Bézout's Identity and Modular Inverses
gcd(a,b) = ax + by for some integers x, y, found by running Euclid's algorithm backwards. When gcd(a,m) = 1 the coefficient of a is its inverse modulo m.
gcd(a,b) = ax + by Bézout's identity
extended Euclid produces x and y
gcd(a,m) = 1 ⟹ ax ≡ 1 (mod m), so x = a⁻¹
Euclid's lemma: p | ab ⟹ p | a or p | b
The gcd, constructively
Core ideas
What this lesson establishes
Bézout upgrades the gcd from a number to an identity, and the identity is what produces inverses and proves unique factorisation.
2
The coefficients come from running Euclid backwards
Each division a = qb + r gives r = a − qb; substituting upward expresses the gcd in terms of the original inputs.
3
Coprimality gives an inverse
ax + my = 1 reduces mod m to ax ≡ 1, so x is a⁻¹. This is where every modular inverse in this course comes from.
The material
Bézout
The identity, the extended algorithm, and the two theorems it unlocks.
Theorem · Bézout's identity
For integers a, b not both zero there are integers x, y with ax + by = gcd(a,b). Moreover gcd(a,b) is the smallest positive integer expressible in that form.
Let S = {ax + by : x, y ∈ ℤ, ax + by > 0}, which is nonempty (it contains |a|). By well-ordering (“The Well-Ordering Principle” in Induction and Recursion) it has a least element d = ax₀ + by₀.
Divide: a = qd + r with 0 ≤ r < d. Then r = a − qd = a(1 − qx₀) + b(−qy₀), which is of the required form. Since 0 ≤ r < d and d is the smallest positive such value, r = 0, so d | a. Similarly d | b, so d is a common divisor.
Any common divisor c of a and b divides ax₀ + by₀ = d, so c ≤ d. Hence d = gcd(a,b).
□
The extended Euclidean algorithm
The proof establishes existence; the algorithm produces the coefficients. Run Euclid forward recording the quotients, then substitute backwards.
gcd(1071, 462):
1071 = 2·462 + 147 ⟹ 147 = 1071 − 2·462
462 = 3·147 + 21 ⟹ 21 = 462 − 3·147
147 = 7· 21 + 0
Back-substitute:
21 = 462 − 3·147
= 462 − 3(1071 − 2·462)
= 462 − 3·1071 + 6·462
= 7·462 − 3·1071
So 1071·(−3) + 462·(7) = 21 = gcd. ✓
The iterative form maintains the coefficients as it goes and avoids the back-substitution entirely: alongside each remainder r it keeps s and t with r = as + bt, updating all three by the same "subtract q times the row above" step. It is what the lab runs, row by row with the identity checked on every line, and what every implementation uses.
Theorem · Modular inverses
a has an inverse modulo m — an x with ax ≡ 1 (mod m) — if and only if gcd(a, m) = 1. The inverse is then unique modulo m.
If gcd(a,m) = 1, Bézout gives ax + my = 1, and reducing modulo m leaves ax ≡ 1.
Conversely if ax ≡ 1 (mod m) then ax − 1 = my for some y, so ax − my = 1, and any common divisor of a and m divides 1.
For uniqueness: if ax ≡ ax' ≡ 1 then x ≡ x(ax') = (xa)x' ≡ x'.
□
This is the theorem RSA runs on. The private exponent d is the inverse of the public exponent e modulo φ(n), and it is computed by exactly this algorithm.
Theorem · Euclid's lemma
If a prime p divides ab, then p | a or p | b.
Suppose p ∤ a. Since p is prime, gcd(p, a) = 1, so Bézout gives px + ay = 1. Multiplying by b: pbx + aby = b.
p divides pbx, and p divides ab hence aby. So p divides their sum, which is b.
□
Euclid's lemma is what makes prime factorisation unique, so “Primes and Unique Factorisation”'s fundamental theorem rests on Bézout, which rests on well-ordering. The chain of dependency is worth noticing: the most familiar fact in the course has the deepest justification.
Interactive
Number theory workbench
Algorithms with their traces
Method
Finding Bézout coefficients
Forward for the gcd, backward for the coefficients.
1
Run Euclid and record every quotient
Each line a = qb + r will be rearranged as r = a − qb.
2
Start from the last nonzero remainder
That is the gcd. Express it using the line that produced it.
3
Substitute upward, one line at a time
Replace each remainder by its expression in earlier terms, collecting coefficients as you go.
4
Verify the identity
Compute ax + by and check it equals the gcd. A sign error here is easy and the check is one multiplication.
Bézout
Score 0 / 0Choose the answer you can justify.
The inverse of 17 modulo 3120
The computation RSA needs, on the standard textbook key.
3120 = 183·17 + 9
17 = 1· 9 + 8
9 = 1· 8 + 1
8 = 8· 1 + 0 ⟹ gcd = 1, so an inverse exists
Back-substitute:
1 = 9 − 1·8
= 9 − 1(17 − 1·9) = 2·9 − 1·17
= 2(3120 − 183·17) − 1·17 = 2·3120 − 367·17
So −367 · 17 ≡ 1 (mod 3120), and −367 + 3120 = 2753
17 · 2753 = 46 801 = 15 · 3120 + 1 ✓
2753 is the private exponent d for the RSA key in “RSA Encryption”.
The negative coefficient is normal and is corrected by adding the modulus. This calculation is the entire key-generation step of RSA: everything else is multiplication and exponentiation.
Common mistakes
1
Leaving a negative inverse unreduced−367 is correct and 2753 is the representative in [0, m). Both satisfy the congruence; only one is conventional.
2
Looking for an inverse when the gcd is not 1None exists. Checking the gcd first costs one run of Euclid and saves the search.
3
Making a sign error in back-substitutionVerify ax + by = gcd at the end. One multiplication, and it catches the error every time.
Check your understanding
✓
Finish when you can produce a modular inverse on demand.
Find the inverse of 7 modulo 26 by the extended algorithm and verify it. That is the decryption key for the affine cipher in “Classical Ciphers”, and the same computation scaled up is RSA's private exponent.
Note: Bézout is the constructive content of the gcd. Knowing that a common divisor is greatest is a fact; knowing how to write it as a combination is a tool, and every modular inverse in cryptography comes from it.