Extended Euclidean Algorithm and Modular Inverses

The Euclidean Algorithm Revisited

Let's begin with a quick review of the standard Euclidean Algorithm. Its purpose is to efficiently find the greatest common divisor of two integers. The algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with any multiple of the smaller number. This is usually expressed by the identity gcd(a, b) = gcd(b, a mod b).

To formalize this and see a proof of correctness, which aligns with your preference for a rigorous approach, please review the first section of the following notes.

The key takeaway is that the algorithm is guaranteed to terminate because the arguments get smaller with each recursive step, and its correctness hinges on the gcd(x, y) = gcd(y, x mod y) identity.

Bézout's Identity and Modular Inverses

The "extended" part of the Euclidean algorithm comes from its ability to not just find the GCD, d, of two integers a and b, but also to find a pair of integers x and y that satisfy Bézout's Identity:

This identity is more than a mathematical curiosity; it's the key to computing modular inverses. A multiplicative inverse of an integer a modulo m is an integer a⁻¹ such that a * a⁻¹ ≡ 1 (mod m). Such an inverse exists if and only if a and m are coprime, meaning gcd(a, m) = 1.

How does Bézout's identity help? If gcd(a, m) = 1, then we know there exist integers x and y such that:

If we consider this equation modulo m, the my term becomes zero:

This shows that the integer x found by the Extended Euclidean Algorithm is precisely the multiplicative inverse of a modulo m.

For a clear explanation of this connection, watch the following segment.

The Extended Euclidean Algorithm: Formalism and Proof

Now, let's look at the algorithm itself and prove that it correctly finds the coefficients x and y. We'll examine a recursive formulation that elegantly demonstrates its correctness.

The proof presented in the notes is a classic example of structural induction following the recursion. Let's summarize the main argument:

• Base Case: If y = 0, then gcd(x, 0) = x. The algorithm returns (x, 1, 0). This is correct because 1*x + 0*y = x.
• Inductive Step: Assume the recursive call extended-gcd(y, x mod y) correctly returns (d, a', b') such that d = a'y + b'(x mod y). This is our inductive hypothesis.
  The algorithm then returns (d, b', a' - floor(x/y) * b'). We must prove that these new coefficients satisfy the identity for x and y.
  Let's substitute the definition x mod y = x - floor(x/y) * y into our hypothesis: $$\begin{array}{rl}d& =a^{\prime }y+b^{\prime }(x-\lfloor x/y\rfloor y)\\ & =a^{\prime }y+b^{\prime }x-b^{\prime }\lfloor x/y\rfloor y\\ & =b^{\prime }x+(a^{\prime }-\lfloor x/y\rfloor b^{\prime })y\end{array}$$ This is exactly the form Ax + By where A = b' and B = a' - floor(x/y) * b'. This confirms that the values returned by the algorithm are correct, completing the proof.

The Algorithm in Practice: The Tabular Method

While the recursive formulation is excellent for proofs, an iterative version known as the tabular method is often more convenient for manual computation and implementation. This method tracks the same values (s and t coefficients) in a table, updating them at each step of the Euclidean algorithm.

The core of this method lies in the following recurrence relations, where r_i are the remainders, q_i are the quotients, and s_i, t_i are the coefficients for r_i = s_i * a + t_i * b.

• r_{i+1} = r_{i-1} - q_i * r_i
• s_{i+1} = s_{i-1} - q_i * s_i
• t_{i+1} = t_{i-1} - q_i * t_i

The initial values are set as:

• r_0 = a, s_0 = 1, t_0 = 0
• r_1 = b, s_1 = 0, t_1 = 1

The following image provides a compact visualization of this process for a=68 and b=30. The table on the right shows the values of r_i (first column) and the corresponding coefficients s_i and t_i (second and third columns).

To see this method worked out in detail, the following video provides an excellent step-by-step guide.

Example: Computing a Modular Inverse

Let's use the tabular method to solve a practical problem: find the multiplicative inverse of 17 modulo 101.

We need to find an integer x such that 17x ≡ 1 (mod 101). This means we run the Extended Euclidean Algorithm on a=101 and b=17.

The last non-zero remainder is 1, which confirms that gcd(101, 17) = 1. The corresponding row in the table tells us that:

Taking this equation modulo 101, we get:

Therefore, the multiplicative inverse of 17 modulo 101 is 6.

From Algorithm to Code

As a CSE student, you'll appreciate how directly these recurrence relations translate into an iterative program. The tabular method avoids the overhead of recursion and is straightforward to implement in a loop.

The video resource we used earlier also includes a Python implementation that directly follows this logic.

Conclusion

In this lesson, we established a crucial tool for our cryptographic toolkit. We have seen that the Extended Euclidean Algorithm is a fast, efficient method for solving ax + by = gcd(a, b). You now understand not only how to execute the algorithm using the tabular method but also why it works, thanks to the formal inductive proof based on its recursive structure. Most importantly, you can now apply it to its primary cryptographic purpose: the computation of modular multiplicative inverses.

Key Takeaways:

• Bézout's Identity guarantees that for any integers a and b, there exist integers x and y such that ax + by = gcd(a, b).
• The Extended Euclidean Algorithm is a constructive proof of this identity, providing a method to find x and y.
• The algorithm's correctness can be formally proven by induction.
• When gcd(a, m) = 1, the coefficient x in ax + my = 1 is the modular multiplicative inverse of a modulo m.
• The tabular method provides a systematic and implementable way to compute the GCD and the Bézout coefficients simultaneously.

In our next lesson, we will move to another pillar of number theory for cryptography: Euler's totient theorem and Fermat's Little Theorem. These theorems will give us a powerful theoretical framework for reasoning about exponents in modular arithmetic, which is the foundation for cryptosystems like RSA.