The Extended Algorithm

The extended Euclidean algorithm computes the GCD of two integers \(a\) and \(b\) and also finds integers \(x\) and \(y\) such that

\[ \operatorname{GCD}(a, b) = ax + by. \]

This equation is called an integral linear combination of \(a\) and \(b\). The algorithm finds the coefficients \(x\) and \(y\) by reversing the divisions used to compute the GCD.

Example

The Euclidean algorithm finds that \(\operatorname{GCD}(15, 26) = 1\) by the calculations

\[\begin{split} \begin{aligned} 26 &= 1\cdot 15 + 11, \\ 15 &= 1\cdot 11 + 4, \\ 11 &= 2\cdot 4 + 3, \\ 4 &= 1\cdot 3 + 1, \\ 3 &= 3\cdot 1 + 0. \end{aligned} \end{split}\]

The last nonzero remainder is \(1\), so \(\operatorname{GCD}(15, 26)=1\). To write this GCD as a combination of \(15\) and \(26\), work backward from the equation \(1=4-3\) and substitute the earlier remainders:

\[\begin{split} \begin{aligned} 1 &= 4 - 3 \\ &= 4 - (11 - 2\cdot 4) = 3\cdot 4 - 11 \\ &= 3\cdot (15 - 11) - 11 = 3\cdot 15 - 4\cdot 11 \\ &= 3\cdot 15 - 4\cdot (26 - 15) = 7\cdot 15 - 4\cdot 26. \end{aligned} \end{split}\]

Therefore, \(\operatorname{GCD}(15, 26)=1=15\cdot 7+26\cdot(-4)\), so \(x = 7\) and \(y = -4\).

Instead of tracking all of the divisions explicitly, the algorithm can be implemented recursively.

The Recursion

Assume \(a\) and \(b\) are not both zero. The extended algorithm follows the same recursion as the standard Euclidean algorithm,

\[ \operatorname{GCD}(a, b) = \operatorname{GCD}(b,\ a \bmod b), \]

stopping when the second entry is \(0\).

Base Case

If \(b = 0\), then \(a \neq 0\), and \(\operatorname{GCD}(a, b) = \operatorname{GCD}(a, 0) = |a|\). There are two subcases.

  • If \(a > 0\), then \(|a| = a\), so that \(\operatorname{GCD}(a, b) = a = a \cdot 1 + b \cdot 0\). Thus, \(x = 1\) and \(y = 0\).

  • If \(a < 0\), then \(|a| = -a\), so that \(\operatorname{GCD}(a, b) = -a = a \cdot (-1) + b \cdot 0\). Thus, \(x = -1\) and \(y = 0\).

Recursive Case

Now suppose \(b \neq 0\). Let \(a = qb + r\), where \(r = a \bmod b\). The next step in the Euclidean algorithm is to find \(\operatorname{GCD}(b, r)\), which equals \(\operatorname{GCD}(a, b)\). Here is where the recursive structure is exposed: if there is an integral linear combination for \(\operatorname{GCD}(b, r)\) in terms of \(b\) and \(r\), then it can be transformed into an integral linear combination for \(\operatorname{GCD}(a, b)\) in terms of \(a\) and \(b\). Specifically, if \(e\) and \(f\) are integers such that \(\operatorname{GCD}(b, r) = be + rf\), then using \(r = a - qb\),

\[ \begin{aligned} \operatorname{GCD}(a, b) = \operatorname{GCD}(b, r) = be + rf = be + (a - qb)f = af + b(e - qf), \end{aligned} \]

which is \(\operatorname{GCD}(a, b) = ax + by\) with \(x = f\) and \(y = e - qf\).

Problem 3

Write a function named xgcd() that accepts two integers \(a\) and \(b\), not both zero. Run the extended Euclidean algorithm recursively. In each case (the base case with \(a > 0\) or \(a < 0\), and the recursive case) return three integers: \(d = \operatorname{GCD}(a, b)\), \(x\), and \(y\) such that \(d = ax + by\).

Test Cases

print(xgcd(15, 26))
print(xgcd(112233, 445566))
print(xgcd(12, -53))
print(xgcd(-12, -53))
print(xgcd(-7, 0))
(1, 7, -4)
(33, -4633, 1167)
(1, -22, -5)
(1, 22, -5)
(7, -1, 0)

Cryptography and GCD

The GCD is important for many cryptographic systems. For example, an affine cipher, a generalization of the Caesar cipher, encrypts a letter \(x\) as \((ax + b) \bmod 26\). It can be decrypted only when \(a\) and \(26\) are relatively prime, so that \(a\) has a multiplicative inverse modulo \(26\).

The more powerful RSA method, named for its inventors Rivest, Shamir, and Adleman, is a public-key cryptosystem. An RSA public key includes a modulus \(n = pq\), the product of two secret primes \(p\) and \(q\), and a public exponent \(e\). The private exponent \(d\) satisfies \(ed \equiv 1 \pmod{(p-1)(q-1)}\). During key generation, \(e\) is chosen relatively prime to \((p-1)(q-1)\), and the extended Euclidean algorithm can be used to compute \(d\).

Keeping \(p\) and \(q\) secret is essential. If two distinct RSA moduli \(n_1\) and \(n_2\) accidentally share a prime factor, their GCD reveals that factor and makes both moduli easy to factor. In 2012, researchers used GCDs to find weak RSA keys among public keys collected from the internet and recovered private keys from hosts whose moduli shared factors because of poor randomness.