Estructura lógica de la prueba elemental de la teoría de los números

Question

Estoy tratando de entender la estructura lógica detallada de una prueba mediante el uso de la identidad de bezout.La parte de la teoría de números la entiendo fácilmente, el problema que tengo es con la lógica.

Un ejemplo :

Propuesta - gcd(a,b)= gcd( gcd(a,b) , b) .
Lo entiendo perfectamente por intuición, y también puedo demostrar que todo entero d que divide a y b, debe dividir a gcd(a,b) y a b , también a la inversa, demostrando que tienen los mismos divisores comunes y por tanto el mismo gcd.
Mi problema es entender completamente cada paso de una prueba formal de esa proposición, mediante el uso de la identidad de bezout.
Sé que la identidad bezout nos permite inferir dos afirmaciones :

• Afirmación 1 : Existe x,y en Z s.t ax + by = gcd(a,b) = d .
• Afirmación 2 : Existen xo,yo en Z s.t gcd(a,b).xo + b.yo = gcd( gcd(a,b) , b ) = w

Ahora, ¿cómo debemos proceder para demostrar la proposición, es decir, para demostrar d=w ?

1 - ¿Debemos intentar demostrar que la afirmación 1 es verdadera si y sólo si la afirmación 2 es verdadera? ( supongo que no )

2 - ¿Podría simplemente encontrar algún par xo,yo, es decir xo=1 y yo=0, que haga que w=d ? ¿Probaría esto completamente la proposición?

3 - Si basta con demostrar la proposición completa, ¿es la única opción para demostrar mediante el uso de la identidad de bezout ( demostrando w=d ) ? Porque en afirmaciones más complicadas ( como gcd(a,b) = gcd(a+bx,b) ) , podría no ser capaz de adivinar de inmediato el xo,yo que hace w=d.

Muchas gracias de antemano.

Answer 1

Creo que tu principal dificultad es que sólo has expuesto realmente una parte del resultado de Bezout. La versión completa es:

si $m,n,c$ son enteros, entonces existen enteros $x,y$ tal que $mx+ny=c$ si y sólo si $c$ es un múltiplo de $\gcd(m,n)$ .

Así que para tu pregunta: deja que $d=\gcd(a,b)$ y $w=\gcd(d,b)$ . Entonces existe $x_1,y_1$ tal que $ax_1+by_1=d$ y existe $x_2,y_2$ tal que $dx_2+by_2=w$ . Sustituyendo la primera ecuación en la segunda y reordenando, $$a(x_1x_2)+b(y_1x_2+y_2)=w\ ,$$ y como las dos expresiones entre paréntesis son números enteros, tenemos $\gcd(a,b)\mid w$ Es decir, $d\mid w$ . Por otro lado, la ecuación $$dx+by=d$$ obviamente tiene la solución entera $x=1$ , $y=0$ y así $\gcd(d,b)\mid d$ Es decir, $w\mid d$ . Esto completa la prueba.

Answer 2

Sugerencia $\ $ Al aplicar repetidamente $\,\ (m,n)\,\Bbb Z\, =\, m\,\Bbb Z + n\,\Bbb Z\,\ $ obtenemos

$$\begin{eqnarray} ((a,\,b),\,bc)\,\Bbb Z &\,=\,& (a,\,b)\,\Bbb Z + bc\,\Bbb Z\\ &=& (a\,\Bbb Z+b\,\Bbb Z)+bc\,\Bbb Z\\ &=& a\,\Bbb Z+(b\,\Bbb Z\,+\,bc\,\Bbb Z)\\ &=& a\,\Bbb Z +\, b\,\Bbb Z\,\ {\rm by}\,\ bc\,\Bbb Z\subseteq b\,\Bbb Z\\ &=& (a,\,b)\,\Bbb Z\end{eqnarray}\quad\ \ $$

Su pregunta es el caso especial $\ c = 1.$

Answer 3

La técnica que utilizo para demostrar afirmaciones como esa es tomar $d=\gcd (a,b)$ y demostrando que $d$ divide $\gcd(a,b)$ (lo cual es obvio) y que $d$ divide $b$ (lo cual es bastante obvio, además).

Por el contrario, toma $d'=\gcd(\gcd(a,b),b)$ . Obsérvese que ya hemos demostrado que $d$ divide $d'$ desde $d$ es un divisor común de $\gcd(a,b)$ y $b$ . Usted debe demostrar que $d'$ divide $a$ y $b$ . Pero esto también es obvio, ya que $d'$ divide $\gcd(a,b)$ . Por lo tanto, $d'$ divide $d$ y $d=d'$ .

En encontrar esta técnica es mucho más fácil que enredar con la identidad de Bezout.