Bézout’s Identity

Statement

Let $a,b\in\mathbb{Z}$, not both zero. Then there exist integers $x,y\in\mathbb{Z}$ such that \[ ax + by = \gcd(a,b). \] Moreover, the set of all integer combinations \[ \{ax+by \mid x,y\in\mathbb{Z}\} \] is exactly the set of multiples of $\gcd(a,b)$.

Proof (From the Euclidean Algorithm)

Run the Euclidean algorithm on $a$ and $b$ (assume $a\ge b\ge 0$ for simplicity; signs do not matter for $\gcd$): \[ \begin{aligned} a &= bq_1 + r_1, && 0 \le r_1 < b,\\ b &= r_1q_2 + r_2, && 0 \le r_2 < r_1,\\ r_1 &= r_2q_3 + r_3,\\ &\ \vdots \\ r_{k-2} &= r_{k-1}q_k + r_k,\\ r_{k-1} &= r_kq_{k+1} + 0. \end{aligned} \] The last nonzero remainder $r_k$ satisfies \[ r_k = \gcd(a,b). \]

Now we show that every remainder is an integer linear combination of $a$ and $b$. Define $r_{-1}=b$ and $r_0=a$. Clearly, \[ r_0 = 1\cdot a + 0\cdot b,\qquad r_{-1} = 0\cdot a + 1\cdot b. \] From the algorithm, each step has the form \[ r_i = r_{i-2} - q_i r_{i-1}. \] If \[ r_{i-2} = \alpha a + \beta b \quad\text{and}\quad r_{i-1} = \gamma a + \delta b \qquad(\alpha,\beta,\gamma,\delta\in\mathbb{Z}), \] then \[ r_i = (\alpha - q_i\gamma)a + (\beta - q_i\delta)b, \] which is again an integer combination of $a$ and $b$. By repeating this, the final remainder $r_k$ can be written as \[ r_k = xa + yb \] for some integers $x,y$. Since $r_k=\gcd(a,b)$, we obtain \[ ax+by=\gcd(a,b). \]

Example

Compute $\gcd(56,15)$: \[ 56 = 15\cdot 3 + 11,\quad 15 = 11\cdot 1 + 4,\quad 11 = 4\cdot 2 + 3,\quad 4 = 3\cdot 1 + 1. \] So $\gcd(56,15)=1$: \[ \begin{aligned} 1 &= 4 - 3\\ &= 4 - (11 - 4\cdot 2) = 3\cdot 4 - 11\\ &= 3(15 - 11) - 11 = 3\cdot 15 - 4\cdot 11\\ &= 3\cdot 15 - 4(56 - 15\cdot 3) = 15\cdot 15 - 4\cdot 56. \end{aligned} \] Hence $x=-4$ and $y=15$ work: \[ 56(-4) + 15(15) = 1. \]

Corollary (Linear Diophantine Equations)

The equation \[ ax + by = c \] has an integer solution $(x,y)\in\mathbb{Z}^2$ if and only if $\gcd(a,b)\mid c$. (If $\gcd(a,b)=d$ and $ax_0+by_0=d$, then multiplying by $c/d$ gives a solution.)