<s>[INST] Proof of Bézout's Theorem Gostaria de saber como provar usando divisibilidade o teorema de Bezout
$(a,b)=d\Longrightarrow \exists f,g\in\mathbb{Z^*}$ tal que $af+gb=d$


I'd like to know how to, using divisibility,  prove Bézout's Theorem:
Given integers $a,\ b$, if $(a,b)=d$ then  there exist $f,g\in\mathbb{Z^*}$ such that $af + gb=d$.

 [/INST] First of all, it is only an implication in one sense, in English it is incorrectly given as an equivalence.
I very much like the constructive proof. Suppose without loss of generality $a \ge 0$ and $b > 0$, and write the obvious
\begin{equation*}
  \begin{matrix}
    a &=& a \cdot 1 &+& b \cdot 0\\
    b &=& a \cdot 0 &+& b \cdot 1\\
  \end{matrix}
\end{equation*}
Let us now start Euclid's algorithm: $a = b q_{1} +
r_{1}$, with $0 \le r_{1} < b$. We can extend the previous table to:
\begin{equation*}
  \begin{matrix}
    a &=& a \cdot 1 &+& b \cdot 0\\
    b &=& a \cdot 0 &+& b \cdot 1\\
    r_{1} &=& a \cdot 1 &+& b \cdot (-q_{1})\\
  \end{matrix}
\end{equation*}
Let's continue with Euclidean divisions: $b = r_{1} q_{2} + r_{2}$, with $0 \le r_{2} < r_{1}$. Thus $r_{2} = b
- r_{1} q_{2}$. Let us use the last two lines of the last table to rewrite $r_{2}$ in terms of $a$ and $b$,
\begin{equation*}
  \begin{matrix}
    a &=& a \cdot 1 &+& b \cdot 0\\
    b &=& a \cdot 0 &+& b \cdot 1\\
    r_{1} &=& a \cdot 1 &+& b \cdot (-q_{1})\\
    r_{2} &=& a \cdot u_{2} &+& b \cdot v_{2}\\
  \end{matrix}
\end{equation*}
Here $u_{2} = -q_2$ and $v_{2} = 1 + q_1 q_2$. But the exact values of $u_{2}$ e $v_{2}$ are not important here, what counts is that they can be calculated in terms of the coeffients in the previous two lines of the table. At the end of the algorithm the last non-zero remainder will be the $\gcd$ of $a$ and $b$, and the table will look like
\begin{equation*}
  \begin{matrix}
    a &=& a \cdot 1 &+& b \cdot 0\\
    b &=& a \cdot 0 &+& b \cdot 1\\
    r_{1} &=& a \cdot 1 &+& b \cdot (-q_{1})\\
    r_{2} &=& a \cdot u_{2} &+& b \cdot v_{2}\\
    & &   \dots & & \\
    d &=& a \cdot u  &+& b \cdot v\\
  \end{matrix}
\end{equation*}
We have thus found the required linear combination.
An example: $a =
24$ and $b = 14$.
The Euclidean divisions are
\begin{equation}
  \begin{matrix}
    \mathbf{24} &=& \mathbf{14} \cdot 1 &+& \mathbf{10}\\
    \mathbf{14} &=& \mathbf{10} \cdot 1 &+& \mathbf{4}\\
    \mathbf{10} &=& \mathbf{4} \cdot 2 &+& \mathbf{2}\\
    \mathbf{4} &=& \mathbf{2} \cdot 1 &+& 0\\
  \end{matrix}
\end{equation}
so that the $\gcd$ is (surprise!) $2$. (Remainders are given in bold here.)
Computing as above
\begin{equation}
  \begin{matrix}
    \mathbf{24} &=& \mathbf{24} \cdot 1 &+& \mathbf{14} \cdot 0\\
    \mathbf{14} &=& \mathbf{24} \cdot 0 &+& \mathbf{14} \cdot 1\\
    \mathbf{10} &=& \mathbf{24} \cdot 1 &+& \mathbf{14} \cdot (-1)\\
    \mathbf{4} &=& \mathbf{24} \cdot (-1) &+& \mathbf{14} \cdot 2\\
    \mathbf{2} &=& \mathbf{24} \cdot 3 &+& \mathbf{14} \cdot (-5)\\
  \end{matrix}
\end{equation}
PS Linguistic remark: this is a translation of my notes, which are written in Italian.
</s>