The extended Euclidean algorithm and modular inverses

The extended Euclidean algorithm worked as a full table, then used to compute a modular inverse and to show when one does not exist.

Run the extended Euclidean algorithm on two integers and produce every row of the table.
Read the Bezout coefficients x and y off the finished table and verify ax + by = gcd(a, b).
Compute a modular inverse with the extended Euclidean algorithm, and explain why one can fail to exist.

18 min readJump to the quiz ↓

The extended algorithm returns the gcd as a combination of a and b

The plain Euclidean algorithm on the previous page answers “what is $\gcd(a, b)$ ?” and stops there. Encryption needs a second question answered: given $a$ and a modulus $n$ , is there a number that “undoes” multiplication by $a$ , modulo $n$ ? That number is the modular inverse, and RSA’s private key is computed by finding exactly one. The extended Euclidean algorithm answers both questions in a single pass, and it hands back the modular inverse as a byproduct.

For integers $a$ and $b$ , it finds not just $d = \gcd(a, b)$ but two integers $x$ and $y$ satisfying $ax + by = d = \gcd(a, b).$ It runs the same division steps as the plain algorithm, carrying two extra running values, $s$ and $t$ , alongside the remainder $r$ at every row. Each row satisfies $r = sa + tb$ : the remainder expressed as a combination of the original $a$ and $b$ . The last row before the remainder hits $0$ gives $d$ , $x$ and $y$ together.

Formula

Bezout identity

ax + by = d = \gcd(a, b)

$a, b$: the two input integers
$d$: gcd(a, b)
$x, y$: the Bezout coefficients

Try it — worked example

Use the extended Euclidean algorithm on a = 240, b = 46. Find gcd and x, y with 240x + 46y = gcd.

Show answer and steps

Answergcd(240, 46) = 2, x = -9, y = 47

Start the table with $r_{-1} = a = 240$ ( $s=1, t=0$ ) and $r_0 = b = 46$ ( $s=0, t=1$ ). Each later row divides the previous remainder by the current one and updates $s$ and $t$ the same way.

$q = \lfloor 240/46 \rfloor = 5$ . $r = 240 - 5 \times 46 = 10$ . $s = 1 - 5 \times 0 = 1$ . $t = 0 - 5 \times 1 = -5$ . Row: $q=5, r=10, s=1, t=-5$ .
$q = \lfloor 46/10 \rfloor = 4$ . $r = 46 - 4 \times 10 = 6$ . $s = 0 - 4 \times 1 = -4$ . $t = 1 - 4 \times (-5) = 21$ . Row: $q=4, r=6, s=-4, t=21$ .
$q = \lfloor 10/6 \rfloor = 1$ . $r = 10 - 1 \times 6 = 4$ . $s = 1 - 1 \times (-4) = 5$ . $t = -5 - 1 \times 21 = -26$ . Row: $q=1, r=4, s=5, t=-26$ .
$q = \lfloor 6/4 \rfloor = 1$ . $r = 6 - 1 \times 4 = 2$ . $s = -4 - 1 \times 5 = -9$ . $t = 21 - 1 \times (-26) = 47$ . Row: $q=1, r=2, s=-9, t=47$ .
$q = \lfloor 4/2 \rfloor = 2$ . $r = 4 - 2 \times 2 = 0$ . The remainder has reached $0$ , so the table stops here.
The last row with a non-zero remainder is row 4: $r = 2$ , $s = -9$ , $t = 47$ . So $\gcd(240, 46) = 2$ , $x = -9$ , $y = 47$ . Check: $240 \times (-9) + 46 \times 47 = -2160 + 2162 = 2$ .

The table reproduces the five division steps the lecture writes out directly, $240 = 46 \times 5 + 10$ , $46 = 10 \times 4 + 6$ , $10 = 6 \times 1 + 4$ , $6 = 4 \times 1 + 2$ , $4 = 2 \times 2 + 0$ , and reaches the same coefficients the lecture finds by substituting each equation back into the last: $2 = 46 \times 47 - 240 \times 9$ . The table method and back-substitution are the same algorithm; the table keeps the running $s$ and $t$ instead of unwinding the equations afterward.

When gcd(a, n) = 1, the coefficient x is the modular inverse

For $a$ coprime to $n$ (that is, $\gcd(a, n) = 1$ ), the extended Euclidean algorithm on $a$ and $n$ gives $ax + ny = 1$ . Reducing both sides modulo $n$ makes the $ny$ term vanish, leaving $ax \equiv 1 \pmod{n}$ . So $x$ , reduced into the range $[0, n)$ , is the modular inverse of $a$ modulo $n$ , written $a^{-1} \bmod n$ .

Try it — worked example

Find the inverse of 3 mod 11.

Show answer and steps

Answer3^-1 mod 11 = 4

Run the table on $a = 3$ , $b = 11$ . The lecture’s back-substitution uses the same division steps, $11 = 3 \times 3 + 2$ and $3 = 1 \times 2 + 1$ , and working backward gives $1 = 3 \times 4 - 11$ , so $4$ is the coefficient of $3$ . Typing $a = 3$ , $b = 11$ into the stepper above reproduces this table.

$q = \lfloor 3/11 \rfloor = 0$ . $r = 3 - 0 \times 11 = 3$ . $s = 1$ , $t = 0$ . Row: $q=0, r=3, s=1, t=0$ . ( $a$ is smaller than $b$ , so the first quotient is $0$ and the algorithm still runs correctly.)
$q = \lfloor 11/3 \rfloor = 3$ . $r = 11 - 3 \times 3 = 2$ . $s = 0 - 3 \times 1 = -3$ . $t = 1 - 3 \times 0 = 1$ . Row: $q=3, r=2, s=-3, t=1$ .
$q = \lfloor 3/2 \rfloor = 1$ . $r = 3 - 1 \times 2 = 1$ . $s = 1 - 1 \times (-3) = 4$ . $t = 0 - 1 \times 1 = -1$ . Row: $q=1, r=1, s=4, t=-1$ .
$q = \lfloor 2/1 \rfloor = 2$ . $r = 2 - 2 \times 1 = 0$ . Remainder is $0$ , table stops.
Last non-zero remainder: row 3, $r = 1$ , $s = 4$ . Since $\gcd(3, 11) = 1$ , a modular inverse exists, and it is $x = 4$ . Check: $3 \times 4 = 12 \equiv 1 \pmod{11}$ .

Recall

Why does the extended Euclidean algorithm always find a modular inverse when one exists, without any extra searching?

Because it computes $x$ and $y$ with $ax + ny = \gcd(a, n)$ as a direct side effect of finding the gcd, not by trying candidate inverses one at a time. When $\gcd(a, n) = 1$ , that same $x$ , reduced mod $n$ , already is the inverse. No search step is needed.

No inverse exists unless a and n are coprime, and RSA relies on this

Not every $a$ has an inverse modulo $n$ . Since $ax + ny = \gcd(a, n)$ , reducing mod $n$ only isolates a $1$ on the right-hand side when $\gcd(a, n) = 1$ . If $\gcd(a, n) > 1$ , no $x$ satisfies $ax \equiv 1 \pmod{n}$ . The table still runs, but its final gcd is not $1$ .

Try it — worked example

Find the inverse of 2 mod 10, or show it does not exist.

Show answer and steps

Answer2x ≡ 1 (mod 10) has no solution

$q = \lfloor 2/10 \rfloor = 0$ . $r = 2$ . $s = 1$ , $t = 0$ . Row: $q=0, r=2, s=1, t=0$ .
$q = \lfloor 10/2 \rfloor = 5$ . $r = 10 - 5 \times 2 = 0$ . Remainder is $0$ , table stops.
Last non-zero remainder: row 0, $r = 2$ . So $\gcd(2, 10) = 2$ , not $1$ . Since $2$ and $10$ share the common factor $2$ , $2$ has no modular inverse mod $10$ .

The lecture’s own check confirms this the direct way: every product $2 \times k \bmod 10$ for $k \in \mathbb{Z}_{10}$ is even ( $0, 2, 4, 6, 8, 0, 2, 4, 6, 8$ ), and $1$ is odd, so it never appears. Either the gcd test or the direct enumeration is an acceptable exam answer.

Pitfall

A modular inverse requires $\gcd(a, n) = 1$ , full stop. $2$ and $10$ share only the factor $2$ , and that is already enough to rule out every inverse. Do not confuse this with ordinary division, where every non-zero number has a reciprocal: modular arithmetic on $\mathbb{Z}_n$ only grants that to the elements coprime to $n$ , which is exactly the property $\varphi(n)$ counts, on the next page.

Exam detail

This is the step RSA depends on directly. The private exponent is $d = e^{-1} \bmod \varphi(n)$ , the modular inverse of the public exponent $e$ modulo the totient of the modulus. Key generation runs exactly the algorithm on this page: if $\gcd(e, \varphi(n)) \neq 1$ , there is no valid $d$ , and $e$ must be rejected and chosen again. Module 6 relies on this fact without re-deriving it.

Check yourself

Source

Week 4 Number Theory PDF