Extended Euclidean Algorithm
The extended Euclidean algorithm is a refinement of the Euclidean algorithm that not only computes the greatest common divisor (GCD) of two numbers but also finds the coefficients \( x \) and \( y \) in Bézout's identity: \[ a \cdot x + n \cdot y = \text{GCD}(a, n) \]
Bézout’s identity states that for any two integers \( a \) and \( n \), there exist integers \( x \) and \( y \) such that:
\[ a \cdot x + n \cdot y = \text{GCD}(a, n) \]
If the greatest common divisor is 1 (meaning the numbers are coprime integers) the equation simplifies to:
\[ a \cdot x + n \cdot y = 1 \]
In this case, \( x \) is the modular multiplicative inverse of \( a \) modulo \( n \), meaning it satisfies:
\[ a \cdot x \equiv 1 \pmod{n} \]
As a result, the extended Euclidean algorithm is particularly useful for computing \( x \), which is the modular inverse when two numbers are coprime.
What is it used for? The algorithm is widely applied in solving modular equations, which are fundamental in cryptography, number theory, and computer science. It can also be used to solve a Diophantine equation, but only in specific cases—namely, when the equation is linear and has integer solutions. The equation \( ax + by = c \) has integer solutions if and only if the GCD of \( a \) and \( b \) divides \( c \): \[ \text{GCD}(a, b) \mid c \] If this condition is not met, no integer solutions exist.
How the Extended Euclidean Algorithm Works
The algorithm follows these main steps:
- Applying the Standard Euclidean Algorithm
First, use the classic Euclidean algorithm to compute the greatest common divisor (GCD) of \( a \) and \( n \) through successive divisions: \[ n = a \cdot q + r \] where \( n \) is the dividend, \( a \) is the divisor, \( q \) is the quotient, and \( r \) is the remainder. The process continues by replacing \( a \) with \( r \) and repeating until the remainder is 1, confirming that \( a \) and \( n \) are coprime. - Working Backward to Express the GCD
Starting from the last division step, express each remainder as a linear combination of \( a \) and \( n \), working backward until 1 is written as a combination of \( a \) and \( n \). The coefficient \( x \) that multiplies \( a \) in this final expression is the modular inverse of \( a \) modulo \( n \).
Note. In the final step, \( x \) should always be positive. If the computed value of \( x \) is negative, it can be adjusted by adding \( n \): \[ x_{\text{pos}} = x + n \]
A Practical Example
Example 1: Finding a Modular Multiplicative Inverse
We need to determine the modular inverse of 23 modulo 40.
In other words, we are looking for an integer \( x \) such that:
\[ 23 \cdot x \equiv 1 \pmod{40} \]
To find \( x \), we use the extended Euclidean algorithm.
First, we compute the greatest common divisor (GCD) of 23 and 40 using the Euclidean algorithm:
\[ 40 = 23 \cdot 1 + 17 \]
We continue applying the algorithm to the divisor (23) and the remainder (17):
\[ 23 = 17 \cdot 1 + 6 \]
\[ 17 = 6 \cdot 2 + 5 \]
\[ 6 = 5 \cdot 1 + 1 \]
\[ 5 = 1 \cdot 5 + 0 \]
Since the GCD is 1, this confirms that 23 and 40 are coprime, meaning a modular inverse exists.
Next, we work backward to express 1 as a linear combination of 23 and 40:
\[ 1 = 6 - 5 \cdot 1 \]
Substituting \( 5 = 17 - 6 \cdot 2 \):
\[ 1 = 6 - (17 - 6 \cdot 2) \]
\[ 1 = 6 \cdot 3 - 17 \]
Now, substituting \( 6 = 23 - 17 \cdot 1 \):
\[ 1 = (23 - 17) \cdot 3 - 17 \]
\[ 1 = 23 \cdot 3 - 17 \cdot 4 \]
Replacing \( 17 = 40 - 23 \):
\[ 1 = 23 \cdot 3 - (40 - 23) \cdot 4 \]
\[ 1 = 23 \cdot (3 + 4) - 40 \cdot 4 \]
\[ 1 = 23 \cdot 7 + 40 \cdot (-4) \]
The coefficient of 23 is 7, which means the modular inverse of 23 modulo 40 is:
\[ 23^{-1} \equiv 7 \pmod{40} \]
Note. To verify, we check that \( 23 \cdot 7 \equiv 1 \pmod{40} \): $$ 23 \cdot 7 = 161 \equiv 1 \pmod{40} $$ This confirms that the result is correct.
Example 2: Solving a Diophantine Equation
Consider the linear Diophantine equation:
\[ 23x + 40y = 7 \]
The greatest common divisor (GCD) of 23 and 40 is:
\[ \text{GCD}(23, 40) = 1 \]
Since \( 1 \) divides \( 7 \), integer solutions must exist.
Using the extended Euclidean algorithm, we proceed as follows:
\[ 40 = 23 \cdot 1 + 17 \]
\[ 23 = 17 \cdot 1 + 6 \]
\[ 17 = 6 \cdot 2 + 5 \]
\[ 6 = 5 \cdot 1 + 1 \]
\[ 5 = 1 \cdot 5 + 0 \]
Now, we work backward to express 1 as a linear combination of 23 and 40.
\[ 6 = 5 \cdot 1 + 1 \]
Rewriting this equation:
\[ 1 = 6 - 5 \]
Our goal is to express this in terms of 23 and 40.
Since \( 5 = 17 - 6 \cdot 2 \), we substitute:
\[ 1 = 6 - (17 - 6 \cdot 2) \]
\[ 1 = 6 - 17 + 6 \cdot 2 \]
\[ 1 = 6 \cdot 3 - 17 \]
Since \( 6 = 23 - 17 \), we replace \( 6 \):
\[ 1 = (23 - 17) \cdot 3 - 17 \]
\[ 1 = 23 \cdot 3 - 17 \cdot 3 - 17 \]
\[ 1 = 23 \cdot 3 - 17 \cdot 4 \]
And since \( 17 = 40 - 23 \), we substitute:
\[ 1 = 23 \cdot 3 - (40 - 23) \cdot 4 \]
\[ 1 = 23 \cdot 3 - 40 \cdot 4 + 23 \cdot 4 \]
\[ 1 = 23 \cdot 7 - 40 \cdot 4 \]
Thus, the equation \( 23x + 40y = 1 \) has a particular solution: \( x = 7 \) and \( y = -4 \).
To solve our original equation \( 23x + 40y = 7 \), we multiply both solutions by 7:
$$ x_0 = 7 \cdot 7 = 49 $$
$$ y_0 = -4 \cdot 7 = -28 $$
So, the particular solution to our equation is \( x_0 = 49 \) and \( y_0 = -28 \).
Verifying:
\[ 23x_0 + 40y_0 = 7 \]
\[ 23 \cdot 49 + 40 \cdot (-28) = 7 \]
\[ 1127 - 1120 = 7 \]
\[ 7 = 7 \]
The general solution to a linear Diophantine equation follows the formula:
\[ x = x_0 + k \cdot \frac{b}{\text{GCD}(a,b)} \]
\[ y = y_0 - k \cdot \frac{a}{\text{GCD}(a,b)} \]
where \( k \) is any integer.
Substituting \( x_0 = 49 \) and \( y_0 = -28 \), we obtain the general solution for \( 23x + 40y = 7 \):
\[ x = 49 + k \cdot 40 \]
\[ y = -28 - k \cdot 23 \]
where \( k \) is any integer.
By varying \( k \), we generate infinitely many solutions (e.g., \( k = 0, 1, -1, 2, -2, \dots \)).
Note. The extended Euclidean algorithm can only be applied if \( \text{GCD}(a,b) \) divides the constant term \( c \) in the Diophantine equation. For example, consider:
\[ 6x + 9y = 5 \]
Here, \( \text{GCD}(6,9) = 3 \), but 3 does not divide 5. Therefore, the equation has no integer solutions.
And so on.
