Dados dos números naturales \( a,b \), si \( d=m.c.d(a,b) \) es su máximo cómun divisor, existen enteros \( x,y \) tales que:
\( ax+by=d \) (1)
El algoritmo extendido de Euclides nos da un método para calcular \( d,x,y \).
Pasos a seguir:
Spoiler
1) Tomamos \( r_0=max(a,b) \), \( r_1=min(a,b) \).
2) Hacemos la división entera entre \( r_0 \) y \( r_1 \) de manera que obtenemos:
\( r_0=r_1c_1+r_2 \) donde \( c_1 \) es el cociente y \( 0\leq r_2<r_1 \) es el resto.
3) Si \( r_1\neq 0 \), continuamos.Hacemos la división entera entre \( r_1 \) y \( r_2 \) de manera que obtenemos:
\( r_1=r_2c_2+r_3 \) donde \( c_2 \) es el cociente y \( 0\leq r_3<r_2 \) es el resto.
4) Repetimos el proceso:
\( r_{k-1}=r_kc_k+r_{k+1} \) donde \( c_k \) es el cociente y \( 0\leq r_{k+1}<r_k \) es el resto.
Hasta llegar a un resto \( r_{n+1} \).
5) Entonces \( d=m.c.d(a,b)=r_n \).
6) Para obtener \( x,y \) verificando la condición (1), despejamos en cada ecuación el resto:
\( r_{k+1}=r_{k-1}-r_kc_k \)
y lo vamos sustiyendo en la ecuación anterior empezando por el final:
\( r_n=r_{n-2}-r_{n-1}c_{n-1} \)
\( r_n=r_{n-2}-(r_{n-3}-r_{n-2}c_{n-2})c_{n-1} \)
\( \ldots \)
y así sucesivamente. Al final tendremos \( d \) como combinación lineal entera de \( r_0 \) y \( r_1 \) (de \( a \) y \( b \)).
Ejemplos:
I) Calcular \( d=m.c.d(12,17) \) y \( x,y\in Z \) tales que \( 12x+17y=d \)
Spoiler
Tenemos:
\( 17=12\cdot 1+5 \)
\( 12=5\cdot 2+2 \)
\( 5=2\cdot 2+1 \)
\( 2=2\cdot 1+0 \)
Por tanto \( m.c.d(12,17)=1 \). Ahora vamos incoporando cada ecuación a la última empezando por el final y hacia atrás:
\( 1=5-2\cdot 2 \)
\( 1=5-(12-5\cdot 2)\cdot 2=5\cdot 5-2\cdot 12 \)
\( 1=5\cdot (17-12)-2\cdot 12=5\cdot 17-7\cdot 12 \)
Obtenemos:
\( 5\cdot 17-7\cdot 12=1 \)
II) Calcular \( d=m.c.d(21,15) \) y \( x,y\in Z \) tales que \( 21x+15y=d \)
Spoiler
Tenemos:
\( 21=15\cdot 1+6 \)
\( 15=6\cdot 2+3 \)
\( 6=3\cdot 2+0 \)
Por tanto \( m.c.d(21,15)=3 \). Ahora vamos incoporando cada ecuación a la última empezando por el final y hacia atrás:
\( 3=15-6\cdot 2 \)
\( 3=15-(21-15)\cdot 2=3\cdot 15-2\cdot 21 \)
Obtenemos:
\( 3\cdot 15-2\cdot 21=3 \)
Si, no me explique bien, me referia a un limite superior de esos dos primeros valores calculados, de los valores dados por el algoritmo extendido de euclides. En una ecuacion Ax+By=C, x e y ¿son siempre menores a A y B respectivamente?,¿Depende de C?, ¿Depende de m.c.d?.
En primer lugar para que la ecuación \( Ax+By=C \) tenga solución, \( C \) debe de ser múltiplo del mcd de \( C \).
Por otra parte si \( |A|\neq |B| \) y \( C=mcd(A,B) \) siempre podemos conseguir una solución con \( |x|<|B| \) e \( |y|<|A| \).
Spoiler
Sin pérdida de generalidad suponemos \( C<|B| \).
Basta tener en cuenta que la solución general es de la forma \( (x,y)=(x_0,y_0)+k(B,-A) \). De ahí \( x=x_0+kB \) y podemos escoger \( k \) tal que \( |x|<|B| \). Entonces:
\( |y|=\dfrac{1}{|B|}|C-Ax|\leq \dfrac{1}{|B|})(|C|+|A||x|)\leq \dfrac{1}{B}|A||x|<|A| \)
Saludos.