Bezout’s Identity

Math NT

Statement

Let $x\in \mathbb{Z}$, $y\in \mathbb{Z}$, $x\ne 0$, $y\ne 0$, and $g=\gcd (x,y)$. Bezout’s Identity states that $\alpha \in \mathbb{Z}$ and $\beta \in \mathbb{Z}$ exists when:

$$\alpha x+\beta y=g$$

Furthermore, $g$ is the least positive integer able to be expressed in this form.

Proof

First Statement

Let $x=g{x}_1$ and $y=g{y}_1$, and notice $\gcd (x_1,y_1)=1$ and $\mathrm{lcm}(x_1,y_1)=x_1{y}_1$.

Since this is true, the smallest integer $\alpha$ for $\alpha x_1\equiv 0\mathrm{mod}y$ is $a=y_1$.

For all integers $0\le a,b<y_1$, $a{x}_1\not\equiv b{x}_1\mathrm{mod}y$. (If not, we get $|b-a|>y_1$, which is contradictory). Thus, by pigeonhole principle, there exists $\alpha$ such that $\alpha x_1\equiv 1\mathrm{mod}{y}_1$.

Therefore, there is an $\alpha$ such that $a{x}_1-1\equiv 0\mathrm{mod}{y}_1$, and by extension, there exists an integer $\beta$ such that:

$$\begin{gathered} \alpha x_1-1=-\beta y_1 \\ \alpha x_1+\beta y_1=1 \end{gathered}$$

By multiplying by $g$:

$$\alpha x+\beta y=g$$

Second Statement

To prove $g$ is minimum, let’s consider another positive integer $g\prime$:

$$\alpha \prime x+\beta \prime y=g\prime$$

Since all values are a multiple of $g$:

$$\begin{gathered} 0\equiv \alpha \prime x+\beta \prime x\mathrm{mod}g \\ 0\equiv g\prime \mathrm{mod}g \end{gathered}$$

Since $g$ and $g\prime$ are positive integers, $g\prime \ge g$.