Discrete Math · Undergraduate
The Euclidean Algorithm and Bézout's Identity
Quick answer
The Euclidean algorithm finds gcd(a, b) without factoring: divide, replace the pair by the divisor and the remainder, and repeat until the remainder is 0. The last nonzero remainder is the gcd. Running the steps backward writes the gcd as ax + by for integers x and y, Bézout's identity. When gcd(a, n) = 1, this gives ax ≡ 1 (mod n), so x is the inverse of a modulo n. The method is fast even for numbers with hundreds of digits, which is what makes RSA encryption practical.
What you'll learn
- Find a gcd with the Euclidean algorithm
- Explain why gcd(a, b) = gcd(b, r)
- Write the gcd as ax + by with the extended algorithm
- Compute a modular inverse
Division, again and again
To find , divide and keep the remainder:
At each step the divisor becomes the new dividend and the remainder becomes the new divisor. The last nonzero remainder, , is the gcd. No factoring is needed, which matters when the numbers have hundreds of digits.
Why each step keeps the same gcd
If , then any that divides both and also divides . Conversely, any dividing and divides . So the pairs and have exactly the same common divisors, and the same greatest one. The numbers shrink at every step, so the process ends, and when the remainder is , .
Running it backward
Each remainder is a combination of the two numbers before it. Substituting from the bottom up writes the gcd in terms of the original pair:
Check: . This is Bézout’s identity: for some integers and .
Worked examples
Common mistakes
Practice problems
-
Find .
Answer
Full solution
, , .
-
Find .
Answer
Full solution
, , .
-
Write as .
Answer
Full solution
.
-
Write as .
Answer
Full solution
.
-
Find the inverse of modulo .
Answer
Full solution
, so the inverse is . Check: .
-
Find the inverse of modulo .
Answer
Full solution
The extended algorithm gives . Check: .
-
Does have an inverse modulo ?
Answer
No
Full solution
, so has no integer solution.
-
A student finds and answers , the last remainder. What went wrong?
Answer
The gcd is the last nonzero remainder, .
Full solution
A remainder of signals that the previous remainder divides evenly; that divisor is the gcd.
Frequently asked questions
How does the Euclidean algorithm work?
Divide a by b to get a remainder r. Replace (a, b) with (b, r) and repeat. When the remainder reaches 0, the last nonzero remainder is gcd(a, b).
Why is gcd(a, b) = gcd(b, r)?
Since a = qb + r, any number dividing a and b divides r = a − qb, and any number dividing b and r divides a. The two pairs have the same common divisors.
What is Bézout's identity?
For any integers a and b, not both 0, there are integers x and y with ax + by = gcd(a, b).
How do you find a modular inverse?
Run the extended algorithm on a and n. If ax + ny = 1, then ax ≡ 1 (mod n), so x reduced mod n is the inverse.
Why not factor the numbers instead?
Factoring large numbers is extremely slow. The Euclidean algorithm takes a number of steps proportional to the number of digits.