Bézout's Identity

In this post, we will prove Bézout’s Identity.

Let \(a\) and \(b\) two integers, there exist integers \(s\) and \(t\) such that

\[\gcd(a,b)=s\cdot a + t\cdot b\]

Proof:

For \(a=0\) and \(b\neq 0\) the greatest common divisor is \(b\). The equation above gives us \(b\) as result for an arbitrary \(s\) and \(t=1\). Therefore, the equation is correct if \(a\) is equal to zero. We can argue in the same way for \(b=0\) and \(a\neq 0\).

If \(a\neq 0\):

Let \(d\) be the smallest positive integer not equal to zero such that

\[d = s\cdot a + t\cdot b\]

Since \(\gcd(a, b)\) divides \(a\) and \(b\), it also divides \(sa + tb\).

\[sa + tb = \gcd(a,b) \left( \frac{sa}{\gcd(a,b)} + \frac{tb}{\gcd(a,b)}\right)\]

Therefore, \(\gcd(a,b)\) also divides \(d\).

We now show, that \(d\) divides both \(a\) and \(b\). We will demonstrate this only for \(a\), as the argument for \(b\) follows in the same way.

With Euclidean division (division with remainder) we can express \(a\) also as a multiple of \(d\)

\[a = qd + r\]

with \(0 \leq r < d\).

If \(d\) divides \(a\), \(a\) is a multiple of \(d\) and \(r\) must be zero.

If follows

\[\begin{align} r & = a - qd \\[1.5em] & = a - q(sa + tb) \\[1.5em] & = a(1-qs)-btq \end{align}\]

We see that \(r\) can be expressed in the form \(ax+by\).

Since \(d\) is the smallest positive integer for \(ax+by\) not equal to zero and because \(r<d\), \(r\) must be equal to zero. Due to \(a=qd\), \(a\) must be a multiple of \(d\).

Since \(d\) divides \(a\) and \(b\), we know that \(d\) is a common divisor of \(a\) and \(b\), but not necessarily the greatest common divisor.

\[d \leq \gcd(a, b)\]

On the other hand, since \(\gcd(a,b)\) also divides \(d\) and because the \(\gcd(a,b)\) cannot divide a number that is smaller than itself but greater than zero, we can conclude that \(d=\gcd(a,b)\).

This proofs that we can write the \(\gcd(a,b)\) as a linear combination of \(a\) and \(b\).

\[\gcd(a,b) = d = sa + tb\]