Euclidean Algorithms and Congruences
The Extended Euclidean Algorithm and Bezout Coefficients
Computing Bezout coefficients alongside the GCD, modular inversion as its principal application, and controlling coefficient growth.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0515
The extended algorithm returns not only the GCD but integers expressing it as a combination of the inputs. This is what makes modular inversion possible, and modular inversion is required everywhere from finite field arithmetic to elliptic curve group law.
Bezout's identity
The coefficients are obtained by carrying two auxiliary sequences through the same recurrence that drives the GCD, each updated with the quotient at every step.
Extended Euclidean algorithm
- InitialiseTwo coefficient pairs representing a and b in terms of themselves.
- DivideCompute quotient and remainder as in the classical algorithm.
- UpdateApply the same linear update to both coefficient sequences using the quotient.
- TerminateWhen the remainder is zero, the previous row holds the GCD and its coefficients.
Modular inversion
If a and N are coprime, the Bezout identity gives u a + v N = 1, so u is the inverse of a modulo N. If the GCD is not one, no inverse exists — and the GCD itself is a non-trivial factor of N, which several factoring methods exploit deliberately.
Coefficient growth
The Bezout coefficients grow, bounded roughly by the ratio of the inputs to the GCD. For a bare GCD this is harmless, but when the extended algorithm runs inside a larger computation the growth compounds.
Variants
Half-extended
Computes only one of the two coefficients. Sufficient for modular inversion and cheaper, since one sequence can be dropped.
Binary extended
The Stein variant with coefficient tracking. Avoids division at the cost of more steps.
Normalised
Reduces the coefficient modulo the input at each step to keep it bounded. Essential when only the modular inverse is wanted.
Frequently Asked Questions
Do I need both Bezout coefficients?
What if the inverse does not exist?
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.3.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.