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$.
On
Definition: We say $d=\gcd(a,b)$ is the greatest common divisor of $a$ and $b$ if and only if the following holds:
1- $d>0$
2- $d \mid a$ and $d \mid b$
3- If $e \mid a$ and $e \mid b$ then $d \mid e$
Now we prove the existence of $\gcd(a,b)$ which is called the Bézout's theorem:
Proof: We claim that $\gcd(a,b)=\min\{ ax+by>0: x,y,z \in \mathbb{Z} \}$, let us call it $d$:
It's clear that that $S=\{ ax+by>0: x,y,z \in \mathbb{Z} \} \neq \emptyset$. Because either $a.1+b.0$ or $a.(-1)+b.0$ is positive and hence is in $S$. Therefore, $S$ is a non-empty subset of natural numbers and by using the well-ordering principle $S$ has a least positive element. set $d=\min(S)$. We claim that $d$ satisfies all of the properties of $\gcd(a,b)$:
1) $d>0$ is trivial by the definition of $S$.
2) We claim that $d \mid a$, the same technique could be used to prove that $d \mid b$.
Using Euclid's division algorithm(theorem) we know that $\exists q,r \in \mathbb{Z}$ such that $a=qd+r$ where $0 \leq r < d$
But $d \in S$ therefore $\exists x_0,y_0 \in \mathbb{Z}$ such that $d=a.x_0 + b.y_0$. Therefore $a =q(a.x_0 + b.y_0) + r \implies 0 \leq r = (1-qx_0)a + (-qy_0)b \in S$. If $r>0$ then because $r<d$ by Euclid's division algorithm that contradicts that $d = \min(S)$. Thefore $r=0$ and $a=qd$ which means $d \mid a$. You can similarly show $d \mid b$.
3) if $e \mid a$ and $e \mid b$ then $e \mid a.x_0+b.y_0$, i.e. $e \mid d$
This is obvious because $e \mid a \implies \exists q \in \mathbb{Z}: eq=a$ and $e \mid b \implies \exists q' \in \mathbb{Z}: eq'=b$
Now $eqx_0 + eq'y_0 = ax_0 + by_0 \implies \exists Q=(qx_0+q'y_0)\in \mathbb{Z}: eQ=ax_0+by_0 =d$
This proves that $d= \min\{ ax+by>0: x,y,z \in \mathbb{Z} \}$ satisfies all properties of $\gcd(a,b)$ and since $\gcd(a,b)$ is unique it must be equal to $\gcd(a,b)$.
To show that $\gcd(a,b)$ is unique you can use the third property twice. So, if you assume that $\gcd(a,b)$ is not unique and $d$ and $d'$ satisfy the definition of $\gcd$ then you must have $d \mid d'$ and $d' \mid d$ by using the third property of $\gcd$ twice. That implies $|d| = |d'|$ but since $\gcd$ is defined to be positive that means $d=d'$.
I guess now you'll need someone to translate all this into Spanish for you. Also, instead of $x_0$ or $y_0$ you can write $f$ and $g$. That doesn't really matter as far as we have demonstrated the existence of two such integers satisfying what you want.
On
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 2 &+& 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.
This is the canonical proof I know.
Consider the set $$ S'=\{ax+by:\ x,y\in\mathbb Z\}. $$ It is easy to check that $S'\cap\mathbb N\ne\emptyset$ (because $a,-a,b,-b\in S'$). Let $S=S'\cap\mathbb N$.
As $S$ is a nonempty set of natural numbers, it has a minimum element $d'=af+bg$ for certain $f,g\in\mathbb Z$.
We note first that $d'$ divides both $a$ and $b$. Indeed, use the Division Algorithm to write $a=qd'+r$, with $0\leq r<d'$. If $r>0$, then $r=a-qd'=a-q(af+bg)=a(1-qf)+b(-g)\in S$, contradicting the minimality of $d'$. So $r=0$. A similar argument shows that $d'$ divides $b$.
Finally, let $c$ be any divisor of $a$ and $b$. Then $a=uc$, $b=vc$ for some $v,c\in\mathbb Z$. So $$ d'=af+bg=ucf+vcg=(uf+vg)c, $$ so $c$ divides $d'$. Thus $d'$ is the greatest common divisor.