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 gcd⁡(252,198)\gcd(252, 198), divide and keep the remainder:

252=1⋅198+54198=3⋅54+3654=1⋅36+1836=2⋅18+0\begin{aligned} 252 &= 1 \cdot 198 + 54\\ 198 &= 3 \cdot 54 + 36\\ 54 &= 1 \cdot 36 + 18\\ 36 &= 2 \cdot 18 + 0 \end{aligned}

At each step the divisor becomes the new dividend and the remainder becomes the new divisor. The last nonzero remainder, 1818, is the gcd. No factoring is needed, which matters when the numbers have hundreds of digits.

Why each step keeps the same gcd

If a=qb+ra = qb + r, then any dd that divides both aa and bb also divides r=a−qbr = a - qb. Conversely, any dd dividing bb and rr divides a=qb+ra = qb + r. So the pairs (a,b)(a, b) and (b,r)(b, r) 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 00, gcd⁡(d,0)=d\gcd(d, 0) = d.

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:

18=54−36=54−(198−3⋅54)=4⋅54−198=4(252−198)−198=4⋅252−5⋅198\begin{aligned} 18 &= 54 - 36\\ &= 54 - (198 - 3 \cdot 54) = 4 \cdot 54 - 198\\ &= 4(252 - 198) - 198 = 4 \cdot 252 - 5 \cdot 198 \end{aligned}

Check: 1,008−990=181{,}008 - 990 = 18. This is Bézout’s identity: gcd⁡(a,b)=ax+by\gcd(a, b) = ax + by for some integers xx and yy.

Worked examples

Common mistakes

Practice problems

  1. Find gcd⁡(210,45)\gcd(210, 45).

    Answer

    1515

    Full solution

    210=4⋅45+30210 = 4 \cdot 45 + 30, 45=1⋅30+1545 = 1 \cdot 30 + 15, 30=2⋅1530 = 2 \cdot 15.

  2. Find gcd⁡(391,299)\gcd(391, 299).

    Answer

    2323

    Full solution

    391=1⋅299+92391 = 1 \cdot 299 + 92, 299=3⋅92+23299 = 3 \cdot 92 + 23, 92=4⋅2392 = 4 \cdot 23.

  3. Write gcd⁡(210,45)\gcd(210, 45) as 210x+45y210x + 45y.

    Answer

    15=210(−1)+45(5)15 = 210(-1) + 45(5)

    Full solution

    15=45−30=45−(210−4⋅45)=5⋅45−21015 = 45 - 30 = 45 - (210 - 4 \cdot 45) = 5 \cdot 45 - 210.

  4. Write gcd⁡(1071,462)\gcd(1071, 462) as 1071x+462y1071x + 462y.

    Answer

    21=1071(−3)+462(7)21 = 1071(-3) + 462(7)

    Full solution

    21=462−3⋅147=462−3(1071−2⋅462)=7⋅462−3⋅107121 = 462 - 3 \cdot 147 = 462 - 3(1071 - 2 \cdot 462) = 7 \cdot 462 - 3 \cdot 1071.

  5. Find the inverse of 77 modulo 2626.

    Answer

    1515

    Full solution

    1=3⋅26−11⋅71 = 3 \cdot 26 - 11 \cdot 7, so the inverse is −11≡15-11 \equiv 15. Check: 105=4⋅26+1105 = 4 \cdot 26 + 1.

  6. Find the inverse of 2323 modulo 120120.

    Answer

    4747

    Full solution

    The extended algorithm gives 1=47⋅23−9⋅1201 = 47 \cdot 23 - 9 \cdot 120. Check: 23⋅47=1,081=9⋅120+123 \cdot 47 = 1{,}081 = 9 \cdot 120 + 1.

  7. Does 66 have an inverse modulo 1515?

    Answer

    No

    Full solution

    gcd⁡(6,15)=3≠1\gcd(6, 15) = 3 \ne 1, so 6x+15y=16x + 15y = 1 has no integer solution.

  8. A student finds gcd⁡(252,198)\gcd(252, 198) and answers 00, the last remainder. What went wrong?

    Answer

    The gcd is the last nonzero remainder, 1818.

    Full solution

    A remainder of 00 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.

What to learn next