The Extended Euclidean Algorithm is an important computational method in number theory. The ordinary Euclidean algorithm calculates the greatest common divisor of two integers through repeated division with remainders. The extended version goes further by keeping track of the coefficients used in each division step and expressing the final GCD as a linear combination of the original integers.
Suppose a and b are integers with a ≥ b > 0. The Euclidean algorithm repeatedly applies the division identity a = bq + r, where q is the quotient and r is the remainder. The process continues until the remainder becomes zero. The last nonzero remainder is gcd(a, b).
The extended algorithm then works backward through the remainder equations. Each remainder is expressed in terms of the preceding two values, allowing the final GCD to be written in the form ax + by. The resulting integers x and y are Bézout coefficients.
For example, to find gcd(30, 18), the divisions are 30 = 1(18) + 12 and 18 = 1(12) + 6, followed by 12 = 2(6) + 0. Thus, gcd(30, 18) = 6. Working backward gives 6 = 18 − 12 = 18 − (30 − 18) = 2(18) − 30. Therefore, one pair of Bézout coefficients is x = −1 and y = 2.
The Extended Euclidean Algorithm is especially useful for solving linear Diophantine equations and calculating modular inverses. It is also widely used in computational number theory and cryptographic algorithms.
Extended Euclidean Algorithm
The Extended Euclidean Algorithm is an extension of the Euclidean algorithm that calculates the greatest common divisor of two integers and also finds integers x and y satisfying ax + by = gcd(a, b).
| Name | Expression | Description |
|---|---|---|
Euclidean Division | a = bq + r, where 0 ≤ r < |b| | Each division step expresses the dividend in terms of the divisor and remainder. |
GCD Recurrence | gcd(a, b) = gcd(b, r) | The GCD remains unchanged when the larger integer is replaced by its remainder after division by the smaller integer. |
Bézout Representation | ax + by = gcd(a, b) | The extended algorithm finds the integer coefficients x and y. |
Explanation
Variables
A, b
The original integers.
Q
The quotient obtained in a division step.
R
The remainder obtained in a division step.
X, y
The Bézout coefficients.
D
The greatest common divisor gcd(a, b).
Example or application
A worked example has not yet been added.
Definition
The Extended Euclidean Algorithm is a procedure that calculates gcd(a, b) and finds integers x and y satisfying ax + by = gcd(a, b).
Purpose
Its purpose is to calculate both the greatest common divisor and the corresponding Bézout coefficients efficiently, allowing integer equations and modular inverse problems to be solved systematically.
Importance
It provides an efficient method for finding Bézout coefficients.
It solves linear Diophantine equations when integer solutions exist.
It calculates modular multiplicative inverses.
It is fundamental to many algorithms in computational number theory.
It supports important operations in RSA and other cryptographic systems.
It demonstrates the constructive relationship between the GCD and Bézout's Identity.
Key Concepts
| Name | Description |
|---|---|
Euclidean Algorithm | A repeated-division procedure for calculating the GCD of two integers. |
Extended Euclidean Algorithm | An extension that also calculates the integer coefficients representing the GCD. |
Quotient | The integer q obtained during a division step. |
Remainder | The value r left after dividing one integer by another. |
Back Substitution | The process of replacing remainders with their earlier expressions to obtain a linear combination of the original integers. |
Bézout Coefficients | The integers x and y satisfying ax + by = gcd(a, b). |
Characteristics
It is based on repeated integer division.
The final nonzero remainder is the GCD.
The extended version records information needed to calculate Bézout coefficients.
It works for positive and negative integers, with suitable sign handling.
It terminates after a finite number of division steps.
Its computational complexity is logarithmic in the size of the input integers.
It can be implemented iteratively or recursively.
Types
| Name | Description |
|---|---|
Ordinary Euclidean Algorithm | Calculates only the greatest common divisor using repeated division. |
Extended Euclidean Algorithm | Calculates the GCD together with Bézout coefficients. |
Recursive Extended Euclidean Algorithm | Uses recursive calls to calculate the GCD and coefficients. |
Iterative Extended Euclidean Algorithm | Uses repeated updates of variables to calculate the GCD and coefficients without recursive calls. |
Components
| Name | Description |
|---|---|
Input Integers | The two integers a and b for which the GCD and coefficients are required. |
Division Steps | Repeated equations of the form a = bq + r. |
Final Nonzero Remainder | The greatest common divisor of the input integers. |
Back Substitution | The process used to express the GCD in terms of the original integers. |
Bézout Coefficients | The final integer values x and y satisfying the Bézout identity. |
Properties
gcd(a, b) = gcd(b, a mod b), for b ≠ 0.
The algorithm terminates when the remainder becomes zero.
The last nonzero remainder is the GCD.
Back substitution expresses the GCD as an integer linear combination.
The Bézout coefficients may not be unique.
If gcd(a, b) = 1, the coefficients satisfy ax + by = 1.
The algorithm can be used to calculate a modular inverse when the relevant integers are coprime.
Examples
| Title | Problem | Solution | Answer |
|---|---|---|---|
Finding the GCD and Bézout Coefficients | Apply the Extended Euclidean Algorithm to 30 and 18. | First perform the divisions: 30 = 1 × 18 + 12; 18 = 1 × 12 + 6; 12 = 2 × 6 + 0. The last nonzero remainder is 6. Work backward: 6 = 18 − 12. Since 12 = 30 − 18, substitute to obtain 6 = 18 − (30 − 18) = 2 × 18 − 30. | gcd(30, 18) = 6, with x = −1 and y = 2. |
Finding a Modular Inverse | Find the inverse of 7 modulo 26. | Apply the extended Euclidean algorithm: 26 = 3 × 7 + 5; 7 = 1 × 5 + 2; 5 = 2 × 2 + 1. Work backward: 1 = 5 − 2 × 2 = 5 − 2(7 − 5) = 3 × 5 − 2 × 7 = 3(26 − 3 × 7) − 2 × 7 = 3 × 26 − 11 × 7. Therefore, −11 × 7 ≡ 1 (mod 26). | The modular inverse of 7 modulo 26 is 15, because −11 ≡ 15 (mod 26). |
Applications
Finding modular multiplicative inverses.
Solving linear Diophantine equations.
Calculating Bézout coefficients.
Implementing arithmetic in modular number systems.
Supporting RSA key generation and related cryptographic operations.
Developing efficient algorithms for integer computation.
Prerequisites
Integer arithmetic
Division algorithm
Greatest common divisor
Bézout's Identity
Basic modular arithmetic
Learning Objectives
Explain how the ordinary Euclidean algorithm calculates the GCD.
Describe the additional purpose of the Extended Euclidean Algorithm.
Perform repeated division steps correctly.
Use back substitution to obtain Bézout coefficients.
Verify the resulting Bézout identity.
Apply the algorithm to calculate modular inverses.
Explain why the algorithm terminates.
Common Mistakes
Stopping after finding the GCD without calculating the coefficients.
Making errors when substituting earlier remainder equations.
Confusing quotients with remainders.
Reversing the order of the Bézout coefficients.
Forgetting to verify the final linear combination.
Assuming a modular inverse exists when the two integers are not coprime.
Practice Questions
Apply the Extended Euclidean Algorithm to 48 and 18.
Find integers x and y satisfying 35x + 22y = 1.
Use the algorithm to find gcd(101, 23).
Find the modular inverse of 11 modulo 26.
Explain the difference between the Euclidean Algorithm and its extended version.
Why does the final nonzero remainder represent the GCD?
How does back substitution produce Bézout coefficients?
Key Takeaway
The Extended Euclidean Algorithm calculates both the GCD and the integer coefficients that express it as a linear combination. It is a fundamental tool for solving integer equations and finding modular inverses.
Related Topics
Greatest Common Divisor
Bézout's Identity
Linear Diophantine Equations
Modular Inverses
Modular Arithmetic
RSA Cryptography
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Arithmetic & Number Theory