✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-092

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

NameExpressionDescription

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

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.

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

NameDescription

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

NameDescription

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

NameDescription

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

TitleProblemSolutionAnswer

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