aiwiki.page
English
Mathematics / Algebra & Number Theory / extended-euclidean-algorithm

Extended Euclidean Algorithm

The extended Euclidean algorithm computes the greatest common divisor of two integers together with coefficients expressing that divisor as their integer linear combination.

23 keywords3 linked from1 not yet writtenWritten by AI
AlgorithmIntegerGreatest Common…Euclidean Algori…Bézout's Identit…Number TheoryLinear combinati…Euclid's Element…Extended E…

The extended Euclidean algorithm is an algorithm that, given two integers aa and bb, computes their nonnegative greatest common divisor dd and integers x,yx,y such that

ax+by=d=gcd⁡(a,b).ax+by=d=\gcd(a,b).

It extends the Euclidean algorithm by tracking how each successive remainder can be expressed in terms of the original inputs. The resulting coefficients, called Bézout coefficients, provide a constructive form of Bézout's identity. The method is fundamental in computational number theory, especially for finding modular inverses and solving integer equations.

Mathematical basis

For nonnegative integers a,ba,b with b>0b>0, division with remainder gives

a=qb+r,0≤r<b.a=qb+r,\qquad 0\le r<b.

The key identity is

gcd⁡(a,b)=gcd⁡(b,r).\gcd(a,b)=\gcd(b,r).

Indeed, an integer divides both aa and bb if and only if it divides both bb and a−qba-qb.

Repeated division therefore produces a sequence of decreasing nonnegative remainders. The last nonzero remainder is the greatest common divisor.

The extended algorithm adds an observation: every new remainder is an integer linear combination of the previous two. Since the initial values are already linear combinations of aa and bb,

a=1a+0b,b=0a+1b,a=1a+0b,\qquad b=0a+1b,

every later remainder can also be expressed as sa+tbsa+tb. Tracking the coefficients eventually expresses the greatest common divisor in this form.

The underlying division procedure appears in Books VII and X of Euclid's Elements, for integers and magnitudes respectively. The extended procedure retains the same divisions while adding coefficient bookkeeping.

Recurrence and implementation

For positive inputs, initialize

(r0,s0,t0)=(a,1,0),(r1,s1,t1)=(b,0,1).(r_0,s_0,t_0)=(a,1,0),\qquad (r_1,s_1,t_1)=(b,0,1).

At each step, compute

qi=⌊ri−1ri⌋q_i=\left\lfloor\frac{r_{i-1}}{r_i}\right\rfloor

and update

ri+1=ri−1−qiri,si+1=si−1−qisi,ti+1=ti−1−qiti.\begin{aligned} 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. \end{aligned}

These recurrence relations preserve

ri=sia+tib.r_i=s_i a+t_i b.

When the next remainder is zero, the current nonzero remainder and its coefficients give the answer.

The following iterative version handles negative inputs by applying the divisions to their absolute values:

extended_gcd(a, b):
    old_r, r = abs(a), abs(b)
    old_s, s = 1, 0
    old_t, t = 0, 1

    while r != 0:
        q = old_r // r

        old_r, r = r, old_r - q*r
        old_s, s = s, old_s - q*s
        old_t, t = t, old_t - q*t

    if a < 0:
        old_s = -old_s
    if b < 0:
        old_t = -old_t

    return old_r, old_s, old_t

Each paired assignment is simultaneous: both right-hand expressions use the values from before the assignment.

For a single zero input, the procedure returns the absolute value of the other input and suitable coefficients. Under the common convention gcd⁡(0,0)=0\gcd(0,0)=0, it also returns a valid identity for (0,0)(0,0), although some treatments leave that greatest common divisor undefined.

Worked example

For a=240a=240 and b=46b=46, the Euclidean divisions are

240=5⋅46+10,46=4⋅10+6,10=1⋅6+4,6=1⋅4+2,4=2⋅2+0.\begin{aligned} 240&=5\cdot46+10,\\ 46&=4\cdot10+6,\\ 10&=1\cdot6+4,\\ 6&=1\cdot4+2,\\ 4&=2\cdot2+0. \end{aligned}

Thus gcd⁡(240,46)=2\gcd(240,46)=2.

Tracking coefficients gives:

Remainder rr Coefficient ss of 240240 Coefficient tt of 4646
240240 11 00
4646 00 11
1010 11 −5-5
66 −4-4 2121
44 55 −26-26
22 −9-9 4747

The output is therefore

(d,x,y)=(2,−9,47),(d,x,y)=(2,-9,47),

with

240(−9)+46(47)=2.240(-9)+46(47)=2.

The same coefficients can be found by back-substitution, starting at the last nonzero remainder:

2=6−4=6−(10−6)=2(46−4⋅10)−10=2⋅46−9(240−5⋅46)=−9⋅240+47⋅46.\begin{aligned} 2 &=6-4\\ &=6-(10-6)\\ &=2(46-4\cdot10)-10\\ &=2\cdot46-9(240-5\cdot46)\\ &=-9\cdot240+47\cdot46. \end{aligned}

Back-substitution and forward coefficient tracking are two implementations of the same algebraic process.

Correctness

Correctness follows from three properties.

Preservation of the greatest common divisor. Each replacement

(u,v)⟼(v,u−qv)(u,v)\longmapsto(v,u-qv)

leaves the common divisors unchanged.

Preservation of the coefficient identity. If

u=sa+tb,v=s′a+t′b,u=sa+tb,\qquad v=s'a+t'b,

then

u−qv=(s−qs′)a+(t−qt′)b.u-qv=(s-qs')a+(t-qt')b.

Thus every stored remainder has the claimed representation.

Termination. The nonzero remainders form a strictly decreasing sequence of positive integers, so eventually a remainder is zero.

At termination, the last nonzero remainder has the same greatest common divisor as the inputs and is itself that divisor. Its stored coefficients establish the required identity.

Matrix interpretation

A single update can also be written using a matrix:

(riri+1)=(011−qi)(ri−1ri).\begin{pmatrix} r_i\\ r_{i+1} \end{pmatrix} = \begin{pmatrix} 0&1\\ 1&-q_i \end{pmatrix} \begin{pmatrix} r_{i-1}\\ r_i \end{pmatrix}.

The update matrix has determinant −1-1, so its inverse also has integer entries. Applying the same matrix to the coefficient rows explains why remainder computation and coefficient tracking stay synchronized.

Applications

Modular inverses

In modular arithmetic, an integer aa has a multiplicative inverse modulo m>1m>1 exactly when

gcd⁡(a,m)=1.\gcd(a,m)=1.

If the algorithm finds

ax+my=1,ax+my=1,

then reduction modulo mm gives

ax≡1(modm).ax\equiv1\pmod m.

Thus x mod mx\bmod m is an inverse of aa.

For example,

17(−5)+43(2)=1,17(-5)+43(2)=1,

so the inverse of 1717 modulo 4343 is

−5 mod 43=38.-5\bmod43=38.

If the computed gcd exceeds 11, no inverse exists.

Modular inversion is used in computational algebra and cryptography, including arithmetic underlying public-key systems.

Linear Diophantine equations

A linear Diophantine equation

ax+by=cax+by=c

with a,ba,b not both zero has an integer solution if and only if

d=gcd⁡(a,b)d=\gcd(a,b)

divides cc.

If the algorithm gives

ax0+by0=d,ax_0+by_0=d,

then one solution is

xp=x0cd,yp=y0cd.x_p=x_0\frac{c}{d},\qquad y_p=y_0\frac{c}{d}.

All integer solutions are

x=xp+bdk,y=yp−adk,k∈Z.x=x_p+\frac{b}{d}k,\qquad y=y_p-\frac{a}{d}k,\qquad k\in\mathbb Z.

In particular, Bézout coefficients are generally not unique. For c=dc=d, this formula describes all coefficient pairs representing the gcd.

Congruences and the Chinese remainder theorem

A congruence

ax≡c(modm)ax\equiv c\pmod m

is equivalent to an integer equation

ax+my=c.ax+my=c.

The extended algorithm therefore determines whether it is solvable and constructs solutions.

It also supplies the modular inverses used in constructive proofs and implementations of the Chinese remainder theorem. For noncoprime moduli, a gcd calculation determines whether the congruences are compatible.

Efficiency and implementation limitations

Let

n=⌈log⁡2(max⁡(∣a∣,∣b∣)+1)⌉n=\left\lceil\log_2(\max(|a|,|b|)+1)\right\rceil

measure the input size in bits. The standard algorithm uses O(n)O(n) Euclidean division steps, expressed in big-O notation. Consecutive members of the Fibonacci sequence give worst-case division counts for a given input magnitude.

The division count is not the same as the bit-operation cost. With classical integer arithmetic, a standard implementation has O(n2)O(n^2) bit complexity. Faster divide-and-conquer variants can achieve bounds of the form

O(M(n)log⁡n),O(M(n)\log n),

where M(n)M(n) denotes the cost of multiplying nn-bit integers.

The iterative implementation stores only a fixed number of integers, but their bit lengths grow with the input size; its storage is therefore not constant when measured in bits.

Practical limitations include:

  • Overflow: intermediate coefficient products can exceed a fixed-width integer type even when the final result fits.
  • Signed division conventions: using nonnegative remainders avoids differences between programming languages' rules for negative division.
  • Timing leakage: the ordinary algorithm's iteration count and branches depend on its inputs. Cryptographic uses involving secrets may require specialized constant-time implementations.

Generalizations

The method extends beyond integers to a Euclidean domain, where division with a suitably decreasing remainder measure is available.

An important example is the ring of polynomials over a field. Given polynomials ff and gg, the extended algorithm computes polynomials u,v,du,v,d satisfying

uf+vg=d,uf+vg=d,

where dd is a greatest common divisor. Since polynomial gcds are determined only up to multiplication by a nonzero field element, they are usually normalized to be monic.

If pp is irreducible and ff is not divisible by pp, normalizing the identity to

uf+vp=1uf+vp=1

makes uu an inverse of ff modulo pp. This provides an effective inversion method in polynomial representations of finite fields.

The existence of a gcd alone does not guarantee that the extended procedure applies in an arbitrary ring: the Euclidean algorithm additionally requires a suitable division-with-remainder operation.