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 read

Intuition

The plain Euclidean algorithm on the previous page answers “what is $\gcd(a, b)$ ?” and stops there. Encryption needs a second, related 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 — it never costs more work than the plain version, and it hands back the modular inverse as a byproduct.

Mechanism

For integers $a$ and $b$ , the extended Euclidean algorithm finds not just $d = \gcd(a, b)$ but two integers $x$ and $y$ satisfying $ax + by = d = \gcd(a, b).$ It does this by running the same division steps as the plain Euclidean algorithm, while 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.

Worked example

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$ .

Mechanism

This reproduces the same 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$ , i.e. $x = -9$ , $y = 47$ . The table method and the back-substitution method are the same algorithm; the table just keeps the running $s$ and $t$ instead of unwinding the equations afterward.

Mechanism

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$ .

Worked example

Answer3^-1 mod 11 = 4

Run the table on $a = 3$ , $b = 11$ .

$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$ — 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}$ .

Aside

This reaches the same coefficient the lecture’s back-substitution gets from the same two division steps, $11 = 3 \times 3 + 2$ and $3 = 1 \times 2 + 1$ : working backward gives $1 = 3 \times 4 - 11$ , so $4$ is the coefficient of $3$ — the modular inverse. Typing $a = 3$ , $b = 11$ into the stepper above reproduces this exact table, including the leading $q=0$ row.

Mechanism

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$ .

Worked example

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$ .

Exam detail

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. Both arguments — the gcd test and the direct enumeration — agree, and either is an acceptable exam answer.

Pitfall

A modular inverse requires $\gcd(a, n) = 1$ , full stop — not “small,” not “close to coprime.” $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.

Formula

Bezout identity

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

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

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.

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.

Source

Week 4 Number Theory PDF