[Luis Fuentes]

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 \)).

[cerrar]

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 \)

[cerrar]

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 \)

[cerrar]

[Click]

En el segundo ejemplo:

II) Calcular \( d=m.c.d(21,15) \) y \( x,y\in Z \) tales que \( 20x+50y=d \)

No debería decir:
"Calcular \( d=m.c.d(21,15) \) y \( x,y\in Z \) tales que \( \color{red}21x+15y=d \)"?

[Luis Fuentes]

Hola

 Tienes razón. Ya lo corregí.

Saludos.

[prometeo]

Hola,
Saludos a todos los foreros, en un libro encontré lo siguiente:
Algoritmo extendido de Euclides implementado en una computadora.
El programa es el siguiente.
INPUT: \( a\textsf{ y } b \)
OUTPUT: \( (a,b) \) y valores \( s,t \) tales que \( (a,b)=as+bt \)
1.\( (r_0,r_1,s_0,t_0,s_1,t_1):=(a,b,1,0,0,1) \)
2.\( i:=1 \)
3.Mientras \( r_i\neq{0} \) hacer lo siguiente:
      3.1. Dividir \( r_{i-1} \) entre \( r_i \) para obtener un cociente \( q_i \) y el resto \( r_{i+1} \)
      3.2. \( s_{i+1}:=s_{i-1} - q_is_i \)
      3.3. \( t_{i+1}:=t_{i-1} - q_it_i \)
      3.4. \( i:=i+1 \)
4.El resultado final es \( r_{i-1}=(a,b) \) y \( r_{i-1}=as_{i-1}+bt_{i-1} \)
Este sería el programa informático para el algoritmo extendido de Euclides. Tan solo queda escoger el lenguaje de programación, lenguaje C u otro.
Un saludo,

[Hernan_ER]

¿Qué ocurre si uno de a y b es negativo? ¿Sigue funcionando?

[Carlos Ivorra]

¿Qué ocurre si uno de a y b es negativo? ¿Sigue funcionando?

mcd(a,b)=mcd(-a,b)

Puedes suponer que a y son positivos sin pérdida de generalidad.

[sebasuy]

Lo más sencillo es aplicar el Método de Blankinship.

Saludos.

[Sirius]

Una curiosidad más sobre el Algoritmo de Euclides: nos resuelve qué dos cuadrados suman un entero impar n.

1) Suponemos que n es de la forma:

\( \displaystyle\prod_{i=1}^k p_i \)

tal que: \( p_i \equiv 1 \mod{4},  \)

2) Entonces, tomando un entero m del sistema reducido de restos módulo n, tal que:

\(  m^2 + 1 \equiv 0 \mod{n} \) (Condición necesaria, sólo funciona si m verifica ésto).

Podemos aplicar el Algoritmo de Euclides como si fuerámos a hacer un desarrollo en fracción continua de:
\( \frac{n}{m} \)

3) Usando las propiedades de los convergentes se demuestra fácil que, eventualmente, se obtienen siempre dos restos consecutivos  (a,b) tales que:

\( a^2 + b^2 = n \)

Ejemplo: Tomando \( n = 65= 5 * 13 \) sabemos que tiene 2 desarrollos diferentes como suma de dos cuadrados, pues si i es el número de factores diferentes de n, entonces el número k de desarrollos diferentes como suma de dos cuadrados será:

\( k = 2^{(i-1)} \)

El primero se obtiene usando \( m_1 = 18 \) ya que \( 18^2 +1 = 65 * 5 \). Si usamos \( m_1 = 47 = 65 - 18 \) se obtiene el mismo desarrollo. Restando los dos anteriores hasta el menor resto se obtiene cada nueva línea.
\( 65 \)
\( 18 \)
\( 11 \)
\( 7 \)
este es el primer resto tal que \( 7^2 < 65 \)
\( 4 \)

Por tanto: \( 65 = 7^2 + 4^2 \)

El segundo es inmediato: \( m_2 =8  \) ya que \( 8^2 +1 = 65 * 1 \).

Por tanto: \( 65 = 8^2 + 1^2 \)

[Quarkbite]

¿Se sabe si existe un limite superiror para \( d,x,y \) en la resolución del algoritmo?, es decir, para el ejemplo anterior, Calcular \( d=m.c.d(12,17) \) y \( x,y\in \Bbb Z \) tales que \( 12x+17y=d \), en funcion de \( 12 \) y \( 17 \) ¿se puede calcular un valor límite superior para \( d,x,y \)?

[Luis Fuentes]

Hola

¿Se sabe si existe un limite superiror para \( d,x,y \) en la resolución del algoritmo?, es decir, para el ejemplo anterior, Calcular \( d=m.c.d(12,17) \) y \( x,y\in \Bbb Z \) tales que \( 12x+17y=d \), en funcion de \( 12 \) y \( 17 \) ¿se puede calcular un valor límite superior para \( d,x,y \)?

No entiendo bien la pregunta. Tal como lo has planteado el valor de d está determinado: \( d=mcd(12,17) \). En cuanto a los valores de \( x,y \) hay infinitos pares que cumplen la ecuación:

\( (x,y)=(5,-7)+k(-17,12) \)

Entonces cualquiera de las dos variables (aunque no ambas al tiempo) pueden tomar valores tan altos como queramos.

Saludos.