The Euclidean algorithm and Bézout's identity

Theorem

The Euclidean algorithm and Bézout's identity

T-074Home MU-207Threads number

Statement

Let \( a, b \in \mathbb{Z} \) with not both \( a \) and \( b \) equal to \( 0 \). Let \( d = \gcd(a,b) \) denote the greatest common divisor of \( a \) and \( b \), i.e. the unique positive integer such that (i) \( d \mid a \) and \( d \mid b \), and (ii) for every \( c \in \mathbb{Z} \) with \( c \mid a \) and \( c \mid b \), we have \( c \mid d \). Then there exist integers \( x, y \in \mathbb{Z} \) (not in general unique) such that \[ ax + by = d. \] Moreover \( d \) is the smallest positive integer expressible in the form \( ax+by \) with \( x,y \in \mathbb{Z} \), and the set of all such integer combinations \( \{ax+by : x,y \in \mathbb{Z}\} \) is exactly the set of integer multiples of \( d \). The pair \( (x,y) \) — and, along the way, the value \( d \) itself — can be computed explicitly and in finitely many steps by the Euclidean algorithm.

Why it matters

Bézout's identity converts a purely divisibility-theoretic object, the gcd, into a linear algebraic one: an explicit \( \mathbb{Z} \)-linear combination. This single fact is the hinge on which most of elementary number theory turns. It is the reason Euclid's lemma holds (if \( p \) is prime and \( p \mid ab \) then \( p \mid a \) or \( p \mid b \)), which in turn is the engine behind the Fundamental Theorem of Arithmetic; it is what makes modular inverses computable (solving \( ax \equiv 1 \pmod n \) is exactly finding \( x \) with \( ax + ny = 1 \)), which underlies the Chinese Remainder Theorem and RSA-style cryptography; and it is the prototype for the far-reaching structural fact that \( \mathbb{Z} \) is a principal ideal domain.

Algorithmically, the theorem is not merely an existence statement: the Euclidean algorithm and its extended form give a genuinely efficient (polynomial-time, in fact logarithmic in the number of steps) method for producing \( d \), \( x \), and \( y \) simultaneously, which is why it is a working tool and not just a piece of pure existence theory.

Hypotheses

\( a, b \in \mathbb{Z} \), not both zero. If \( a = b = 0 \), then every integer divides both, so there is no greatest common divisor (the divisibility poset on \( \{c : c\mid 0, c\mid 0\} = \mathbb{Z} \) has no maximum under divisibility); \( \gcd(0,0) \) is conventionally left undefined or set to \( 0 \) by fiat, and the "smallest positive combination" argument below breaks because \( \{0\cdot x + 0\cdot y\} = \{0\} \) contains no positive integer at all.

Working over \( \mathbb{Z} \), a Euclidean domain (or at minimum a PID) — the argument uses the division algorithm. Over a general integral domain without a division algorithm, e.g. \( \mathbb{Z}[\sqrt{-5}] \), a gcd of \( 2 \) and \( 1+\sqrt{-5} \) need not exist, or if a "gcd" is defined via ideal containment it need not be expressible as a linear combination — \( \big(2,\,1+\sqrt{-5}\big) \) is a non-principal ideal, so no single pair \( x,y \) in that ring gives \( 2x + (1+\sqrt{-5})y \) equal to a generator of the gcd's ideal, because there is no such generator.

Proof

Reduce to \( a, b \geq 0 \), not both zero, using \( \gcd(a,b) = \gcd(|a|,|b|) \) and \( \gcd(a,0) = |a| \) for \( a \neq 0 \).

Divisibility is insensitive to sign: \( c \mid a \iff c \mid -a \), so the divisor set of \( a \) equals that of \( |a| \); and every integer divides \( 0 \), so the common divisors of \( a \) and \( 0 \) are exactly the divisors of \( a \). If \( x,y \) work for \( |a|,|b| \), replacing \( x \) by \( -x \) (resp. \( y \) by \( -y \)) when \( a \lt 0 \) (resp. \( b \lt 0 \)) recovers a combination for the original signs. A

(Division algorithm, cited.) For any \( m \in \mathbb{Z} \) and \( n \in \mathbb{Z}_{\gt 0} \) there exist unique \( q, r \in \mathbb{Z} \) with \( m = qn + r \) and \( 0 \leq r \lt n \).

This is the Division Algorithm for \( \mathbb{Z} \), proved separately (existence via well-ordering applied to \( \{m - qn : q \in \mathbb{Z}\} \cap \mathbb{Z}_{\geq 0} \), uniqueness by subtracting two representations). It is the one external input the whole theorem rests on. A

Define the remainder sequence: \( r_{-1} = a \), \( r_0 = b \) (with \( b \gt 0 \); if \( b = 0 \) the algorithm terminates immediately with \( d = a \), \( x=1,y=0 \)), and for \( i \geq 0 \), while \( r_i \neq 0 \), write \( r_{i-1} = q_i r_i + r_{i+1} \) with \( 0 \leq r_{i+1} \lt r_i \), via Step 2.

Each application of Step 2 is legitimate since \( r_i \gt 0 \) whenever it is used as a divisor (we only continue while \( r_i \neq 0 \), and all \( r_i \) for \( i \geq 0 \) are non-negative by construction). B

The sequence \( r_0 \gt r_1 \gt r_2 \gt \cdots \geq 0 \) is strictly decreasing among non-negative integers, hence some \( r_{N+1} = 0 \) is reached after finitely many steps \( N \).

A strictly decreasing sequence of non-negative integers cannot be infinite (well-ordering of \( \mathbb{N} \): an infinite strictly decreasing sequence would give a non-empty subset of \( \mathbb{N} \) with no least element). This is what guarantees the algorithm terminates. A

Claim: \( r_N = \gcd(a,b) \), where \( r_N \) is the last non-zero remainder.

Proved in the next two steps via two sub-claims: (i) \( r_N \) is a common divisor of \( a,b \); (ii) every common divisor of \( a,b \) divides \( r_N \). Together with positivity of \( r_N \) these characterise \( r_N \) as the gcd by definition. B

(i) Downward: \( r_N \mid r_{N-1} \) (since \( r_{N+1}=0=r_{N-1}-q_N r_N \)); then inductively, if \( r_N \mid r_i \) and \( r_N \mid r_{i+1} \), the relation \( r_{i-1} = q_i r_i + r_{i+1} \) gives \( r_N \mid r_{i-1} \). Descending to \( i=0 \) gives \( r_N \mid r_0 = b \) and \( r_N \mid r_{-1} = a \).

Lemma used: if \( c \mid u \) and \( c \mid v \) then \( c \mid (qu+v) \) for any \( q \in \mathbb{Z} \) (linearity of divisibility, immediate from the definition \( u = c u', v = cv' \Rightarrow qu+v = c(qu'+v') \)). Finite backward induction along the strictly decreasing index. B

(ii) Upward: if \( c \mid a \) and \( c \mid b \), i.e. \( c \mid r_{-1} \) and \( c \mid r_0 \), then inductively \( c \mid r_i \) and \( c \mid r_{i+1} \) together with \( r_{i+1} = r_{i-1} - q_i r_i \) give \( c \mid r_{i+1} \) at each forward step. Ascending to \( i = N \) gives \( c \mid r_N \).

Same linearity-of-divisibility lemma as Step 6, applied in the opposite (forward) direction of the recursion, rearranged as \( r_{i+1} = r_{i-1} - q_i r_i \). Together with Step 6 this proves the Claim of Step 5. B

Back-substitution: starting from \( r_N = r_{N-2} - q_{N-1} r_{N-1} \), repeatedly eliminate \( r_{N-1}, r_{N-2}, \ldots, r_1 \) using the defining relations \( r_{i+1} = r_{i-1} - q_i r_i \) in reverse order, at each stage expressing the current remainder as an integer combination of \( r_{-1} = a \) and \( r_0 = b \).

Formally, induct downward on \( i \) with the hypothesis "\( r_i = a x_i + b y_i \) for some \( x_i, y_i \in \mathbb{Z} \)", base cases \( r_{-1} = a\cdot 1 + b \cdot 0 \), \( r_0 = a \cdot 0 + b\cdot 1 \); inductive step substitutes \( r_i = r_{i-2} - q_{i-1}r_{i-1} = a(x_{i-2}-q_{i-1}x_{i-1}) + b(y_{i-2}-q_{i-1}y_{i-1}) \), so \( x_i, y_i \) are computed by the same recursion as the \( r_i \) (this is exactly the Extended Euclidean Algorithm). C

Terminating at \( i = N \): \( r_N = a x_N + b y_N \) for explicit integers \( x_N, y_N \) produced by the induction of Step 8. Setting \( x = x_N, y = y_N \), and recalling \( r_N = d = \gcd(a,b) \) from Step 5, we obtain \( ax+by = d \), proving existence.

Instantiation of the induction in Step 8 at \( i = N \), combined with the identification \( r_N = \gcd(a,b) \) from Step 5. A

Minimality and characterisation of the combination set: let \( S = \{ax+by : x,y\in\mathbb{Z}\} \setminus \{0\} \) (assuming \( a,b \) not both \( 0 \), so \( S \neq \emptyset \)) and let \( m = \min(S \cap \mathbb{Z}_{\gt 0}) \), which exists by well-ordering. Then \( m = d \), and \( S \cup \{0\} = d\mathbb{Z} \).

Divide \( a \) by \( m \) (Step 2): \( a = qm+r \), \( 0\le r\lt m \); since \( m = ax_0+by_0 \) for some \( x_0,y_0 \), \( r = a - qm = a(1-qx_0) + b(-qy_0) \in S\cup\{0\} \), and minimality of \( m \) forces \( r=0 \), so \( m \mid a \); symmetrically \( m \mid b \); so \( m \) is a common divisor, hence \( m \le d \) by definition (ii) of gcd. Conversely \( d \mid a, d\mid b \Rightarrow d \mid (ax+by) \) for every \( x,y \) (linearity lemma of Step 6), so \( d \mid m \) as \( m \in S \), giving \( d \le m \). Hence \( d=m \), and every element of \( S\cup\{0\} \) is, by the division argument just given applied to any \( ax+by \), a multiple of \( d \); conversely \( kd = k(ax+by) = a(kx)+b(ky) \in S \cup\{0\} \) for every \( k\in\mathbb{Z} \). This is the standard "smallest positive combination" argument and is logically independent of the algorithmic construction in Steps 3–9 — it re-proves existence of \( x,y \) non-constructively and adds the sharper description of the whole combination set. C

Result

\[ \exists\, x,y \in \mathbb{Z} : \ \gcd(a,b) = ax + by \]

Reading. The greatest common divisor of two integers, not both zero, is always achievable as a "signed integer combination" of the two — and the Euclidean algorithm's chain of divisions, read backwards, hands you such an \( x \) and \( y \) explicitly.

Scope. Valid for all \( a,b\in\mathbb{Z} \) not both \( 0 \); the coefficients \( x,y \) are never unique (replacing \( (x,y) \) by \( (x+k b/d,\ y-ka/d) \) for any \( k\in\mathbb{Z} \) gives another valid pair); the statement and proof generalise verbatim to any Euclidean domain (e.g. \( F[t] \) for a field \( F \), or the Gaussian integers \( \mathbb{Z}[i] \)) once "division algorithm" and "smaller" are reinterpreted via the relevant Euclidean norm.

Corollaries & converses

Euclid's Lemma. If \( p \) is prime and \( p \mid ab \), then \( p\mid a \) or \( p \mid b \). (If \( p \nmid a \) then \( \gcd(p,a)=1 \), so \( 1 = px+ay \) for some \( x,y \); multiply by \( b \) to get \( b = pbx + aby \), and \( p \) divides both terms on the right since \( p\mid ab \).)
Existence of modular inverses. \( a \) has a multiplicative inverse mod \( n \) iff \( \gcd(a,n)=1 \), and the extended algorithm computes it directly: \( ax+ny=1 \Rightarrow ax\equiv 1 \pmod n \).
\( \mathbb{Z} \) is a Bézout domain / PID. Every ideal \( (a,b) \) of \( \mathbb{Z} \) equals \( (d) \) with \( d=\gcd(a,b) \), by Step 10; iterating shows every finitely generated ideal of \( \mathbb{Z} \) is principal.
Converse fails as a "detection" tool. The existence of some \( x,y \) with \( ax+by=1 \) does prove \( \gcd(a,b)=1 \) (by Step 10's minimality argument any positive value in \( S \) is a multiple of \( d \), so \( d\mid 1 \Rightarrow d=1 \)) — so in this coprimality case the converse genuinely holds and is used constantly. But it is false that every representation \( ax+by=d \) is unique, and it is false that an arbitrary pair \( (x,y) \) with \( ax+by = k \) for some multiple \( k \) of \( d \) tells you \( \gcd(a,b)=k \) — e.g. \( 4\cdot 3 + 6\cdot(-2) = 0 \) says nothing about \( \gcd(4,6) \) beyond \( \gcd(4,6)\mid 0 \), which is vacuous.

Fails without

Drop "not both zero": \( a=b=0 \). Every integer is a common divisor, there is no greatest one, and \( S = \{0\cdot x+0\cdot y\} = \{0\} \) has no positive element, so the minimality argument of Step 10 has nothing to minimise over — the theorem's statement is not merely false here, it is not even meaningful.
Replace \( \mathbb{Z} \) by a ring without a division algorithm: in \( \mathbb{Z}[\sqrt{-5}] \), take \( \alpha = 2,\ \beta = 1+\sqrt{-5} \). One can show \( 1 \) is a common divisor bound in the sense that no non-unit divides both up to the obvious factors, yet the ideal \( (2,\,1+\sqrt{-5}) \) is not principal — there is no single element \( \delta \) with \( (\delta) = (2,1+\sqrt{-5}) \), so there is no candidate "\( d \)" for which one could even ask whether \( d = 2x+(1+\sqrt{-5})y \). The proof breaks at the very first step (Step 2), since \( \mathbb{Z}[\sqrt{-5}] \) admits no division algorithm relative to any norm making it Euclidean.
Drop finiteness of the descent (hypothetical): if one tried to run the same idea in a ring where remainders needn't strictly decrease in a well-ordered value (e.g. formally in \( \mathbb{Q} \) itself, where "remainder" \( 0 \le r \lt n \) can be forced to \( 0 \) trivially but the notion of "common divisor" collapses since every non-zero rational divides every other), termination (Step 4) and the divisor structure both dissolve — gcd is not a meaningful invariant in a field.

Common errors

Running the forward Euclidean algorithm to find \( d \), then guessing \( x,y \) by trial and error instead of systematically back-substituting (Step 8) — this misses the algorithmic content of the theorem and is error-prone for anything beyond tiny examples.
Believing \( x,y \) are unique. They are not; students are often thrown when a textbook and a calculator give "different" correct answers to the same Bézout problem.
Sign errors in back-substitution: forgetting that \( r_{i+1} = r_{i-1} - q_ir_i \) needs to be tracked with the correct sign at each stage, especially when \( a \) or \( b \) is negative and Step 1's reduction hasn't been undone at the end.
Concluding \( \gcd(a,b) = k \) merely because some \( x,y \) were found with \( ax+by=k \); as the Corollaries section notes, this only pins down \( \gcd(a,b) \) as a divisor of \( k \), not as equal to it, unless \( k=1 \) (or minimality is separately verified).
Confusing "\( \gcd(a,b) \) is an integer combination of \( a,b \)" with "every integer combination of \( a,b \) is a multiple of the gcd achieved with small coefficients" — the coefficients \( x,y \) produced by naive search can be far larger than those from the extended algorithm, though both are valid.

Discussion

The Euclidean algorithm is arguably the oldest non-trivial algorithm in continuous use, appearing in Euclid's Elements (Book VII, Propositions 1–2) as a test for commensurability of magnitudes, phrased geometrically rather than arithmetically. Bézout's name attaches to the identity via Étienne Bézout's 18th-century work on resultants of polynomials, though the integer case was known earlier (implicitly to Bachet, and in essence to the algorithm itself) — a reminder that theorem names in number theory often reflect a later, sharper articulation rather than strict priority.

Structurally, the theorem is the concrete, computational face of the abstract fact that \( \mathbb{Z} \) is a principal ideal domain: the set \( \{ax+by\} \) is precisely the ideal \( (a,b) \), and Bézout's identity says this ideal is principal, generated by \( \gcd(a,b) \). Anywhere this ideal-theoretic property holds — Euclidean domains generally, including \( F[t] \) and \( \mathbb{Z}[i] \) — an analogous identity and an analogous algorithm exist, obtained by replacing "size" \( |r| \) with the ring's Euclidean norm.

It is worth being precise about logical dependencies: the existence of \( x,y \) can be proved two genuinely different ways — constructively via the terminating algorithm and back-substitution (Steps 2–9), or non-constructively via well-ordering applied to the set of positive combinations (Step 10). The constructive route is what makes the theorem useful (it hands you an algorithm, not just a proof of existence), while the non-constructive route is what most cleanly explains why the theorem is true at the level of ideal theory. Good exposition keeps both, because they answer different questions: "how do I compute \( x,y \)?" versus "why must such \( x,y \) exist at all?"

Common misconception: that Bézout's identity gives a way to compute \( \gcd(a,b) \) — it does not; the gcd must already be known (or computed via the forward pass of the algorithm) before the identity can be exhibited. The identity certifies a value as the gcd once you already believe it is one (e.g. once you have found \( x,y \) with \( ax+by = g \) and separately checked \( g \mid a, g\mid b \)), but blind search for such \( x, y, g \) without the algorithm's structure is not a gcd-finding method.

Worked examples

Find \( \gcd(252,105) \) and integers \( x,y \) with \( 252x+105y=\gcd(252,105) \).

Apply the algorithm of Step 3 forward. A

\[ 252 = 2\cdot 105 + 42, \qquad 105 = 2\cdot 42 + 21, \qquad 42 = 2\cdot 21 + 0. \]

Repeated division (Step 2/3); last non-zero remainder is \( 21 \). A

By Step 5, \( \gcd(252,105) = 21 \).

Identification of the last non-zero remainder as the gcd. A

Back-substitute (Step 8): \( 21 = 105 - 2\cdot 42 = 105 - 2\,(252 - 2\cdot 105) = 105 - 2\cdot 252 + 4\cdot 105 = 5\cdot 105 - 2\cdot 252. \)

Eliminate \( 42 \) using the first division, then collect coefficients of \( 252 \) and \( 105 \). B

\[ 252\cdot(-2) + 105\cdot(5) = 21 = \gcd(252,105) \]

Reading. \( x=-2,\ y=5 \) is one valid Bézout pair; check: \( -504+525=21 \). Correct.

Solve \( 17x \equiv 1 \pmod{101} \), i.e. find the inverse of \( 17 \) modulo the prime \( 101 \).

By the corollary on modular inverses, this reduces to finding \( x,y \) with \( 17x+101y=1 \), which exists since \( \gcd(17,101)=1 \) (\( 101 \) prime, \( 101\nmid 17 \)). B

\[ 101 = 5\cdot 17 + 16,\quad 17 = 1\cdot 16 + 1,\quad 16 = 16\cdot 1 + 0. \]

Forward pass; last non-zero remainder \( 1 \), confirming \( \gcd(17,101)=1 \). A

\( 1 = 17 - 1\cdot 16 = 17 - 1\,(101 - 5\cdot 17) = 6\cdot 17 - 1\cdot 101. \)

Back-substitution (Step 8), eliminating \( 16 \). B

Reduce mod \( 101 \): \( 17\cdot 6 \equiv 1 \pmod{101} \), so \( 17^{-1} \equiv 6 \pmod{101} \).

Reading the identity \( 6\cdot 17 - 1\cdot 101 = 1 \) modulo \( 101 \) kills the \( -1\cdot 101 \) term. A

\[ 17^{-1} \equiv 6 \pmod{101} \]

Reading. Check: \( 17\times 6 = 102 = 101+1 \equiv 1 \pmod{101}\). This is exactly how modular inverses are computed in practice, e.g. in RSA key generation.

Problems

Compute \( \gcd(840, 252) \) using the Euclidean algorithm, and hence find integers \( x,y \) with \( 840x+252y=\gcd(840,252) \).
Solution
\( 840 = 3\cdot 252 + 84 \); \( 252 = 3\cdot 84 + 0 \). So \( \gcd = 84 \). Back-substitute: \( 84 = 840 - 3\cdot 252 \), so \( x=1, y=-3 \) works directly (only one division was needed). Check: \( 840 - 756 = 84 \). Correct.
Show that if \( \gcd(a,b)=1 \) and \( \gcd(a,c)=1 \), then \( \gcd(a,bc)=1 \).
Solution
By the theorem, choose \( x_1,y_1 \) with \( ax_1+by_1=1 \) and \( x_2,y_2 \) with \( ax_2+cy_2=1 \). Multiply: \( (ax_1+by_1)(ax_2+cy_2)=1 \). Expand: \( a(ax_1x_2+cx_1y_2+bx_2y_1) + bc(y_1y_2) = 1 \). This exhibits \( 1 \) as \( a X + bc\, Y \) with \( X = ax_1x_2+cx_1y_2+bx_2y_1,\ Y=y_1y_2 \), both integers. By the minimality/converse argument (Corollaries), \( \gcd(a,bc) \mid 1 \), so \( \gcd(a,bc)=1 \).
Find all integer solutions \( (x,y) \) to \( 6x+9y=15 \), or show none exist.
Solution
\( \gcd(6,9)=3 \), and \( 3\mid 15 \), so by Step 10 (the combination set is exactly \( 3\mathbb{Z} \), and \( 15\in 3\mathbb{Z} \)) solutions exist. A base solution: \( 6\cdot(-1)+9\cdot 1 = 3 \), scale by \( 5 \): \( 6\cdot(-5)+9\cdot 5=15 \), i.e. \( x_0=-5,y_0=5 \). General solution: \( x=-5+3k,\ y=5-2k \) for \( k\in\mathbb{Z} \) (step sizes \( b/d=3 \), \( a/d=2 \) from Result's uniqueness remark).
Prove that if \( d=\gcd(a,b) \) and \( ax+by=d \), then \( \gcd(x,y) \) need not be \( 1 \) — but show that if additionally \( a=da',\,b=db' \) with \( \gcd(a',b')=1 \) (always possible), the pair \( (x,y) \) can be chosen with \( \gcd(x,y)=1 \). Illustrate with \( a=6,b=4 \).
Solution
\( d=2,\ a'=3,b'=2,\ \gcd(3,2)=1 \), and indeed a Bézout pair for \( 3,2 \) is \( 3(1)+2(-1)=1 \), scaling gives \( 6(1)+4(-1)=2=\gcd(6,4) \), with \( \gcd(x,y)=\gcd(1,-1)=1 \). In general dividing through by \( d \) reduces to the coprime case \( a'x+b'y=1 \), whose Bézout coefficients \( x,y \) automatically satisfy \( \gcd(x,y)=1 \) (any common divisor of \( x,y \) would divide \( a'x+b'y=1 \)). Not every valid pair for the original \( a,b \) has \( \gcd(x,y)=1 \) (e.g. adding a multiple of \( (b/d,-a/d) \) can introduce a common factor into \( x,y \)), but at least one choice always does.
Let \( a,b,n \) be positive integers with \( \gcd(a,n)=1 \). Using Bézout's identity, prove that the map \( t \mapsto at \bmod n \) is a bijection from \( \{0,1,\ldots,n-1\} \) to itself.
Solution
Since \( \gcd(a,n)=1 \), by the theorem there exist \( x,y \) with \( ax+ny=1 \), so \( ax\equiv 1\pmod n \); call \( x \) the inverse \( a^{-1} \bmod n \). The map \( s\mapsto a^{-1}s \bmod n \) is then a two-sided inverse of \( t\mapsto at\bmod n \) on \( \mathbb{Z}/n\mathbb{Z} \): \( a^{-1}(at) \equiv (a^{-1}a)t \equiv t \pmod n \), and symmetrically \( a(a^{-1}s)\equiv s\pmod n \). A map with a two-sided inverse on a finite set is a bijection.