Autor Tema: Algoritmo extendido de Euclides

0 Usuarios y 1 Visitante están viendo este tema.

04 Noviembre, 2009, 07:26 pm
Leído 27569 veces

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
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]

31 Mayo, 2010, 07:48 pm
Respuesta #1

Click

  • Novato
  • Mensajes: 160
  • Karma: +0/-0
  • Sexo: Masculino
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 \)"?

31 Mayo, 2010, 10:35 pm
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

 Tienes razón. Ya lo corregí.

Saludos.

15 Marzo, 2012, 05:51 pm
Respuesta #3

prometeo

  • Novato
  • Mensajes: 150
  • Karma: +0/-0
  • Sexo: Masculino
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,
Las proposiciones matemáticas, en cuanto tienen que ver con la realidad, no son ciertas; y en cuanto que son ciertas, no tienen nada que ver con la realidad.
Albert Einstein (1879-1955)

20 Marzo, 2013, 01:07 am
Respuesta #4

Hernan_ER

  • Héroe
  • Mensajes: 1,452
  • Karma: +0/-0
  • Sexo: Masculino
¿Qué ocurre si uno de a y b es negativo? ¿Sigue funcionando?

04 Abril, 2013, 09:43 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,097
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿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.

14 Noviembre, 2013, 05:05 pm
Respuesta #6

sebasuy

  • Lathi
  • Mensajes: 1,047
  • Karma: +0/-0
  • Sexo: Masculino
Lo más sencillo es aplicar el Método de Blankinship.

Saludos.
Life is good for only two things, discovering mathematics and teaching mathematics.
Poisson, Siméo

14 Octubre, 2017, 07:14 pm
Respuesta #7

Sirius

  • Nuevo Usuario
  • Mensajes: 13
  • Karma: +0/-0
  • Sexo: Masculino
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 \)
"Uno no entiende las matemáticas, más bien, se acostumbra a ellas"
Alan Turing

11 Octubre, 2020, 09:39 pm
Respuesta #8

Quarkbite

  • Nuevo Usuario
  • Mensajes: 4
  • País: es
  • Karma: +0/-0
¿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 \)?

11 Octubre, 2020, 09:49 pm
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
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.

12 Octubre, 2020, 09:29 pm
Respuesta #10

Quarkbite

  • Nuevo Usuario
  • Mensajes: 4
  • País: es
  • Karma: +0/-0
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?.

13 Octubre, 2020, 11:48 am
Respuesta #11

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

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| \)
[cerrar]

Saludos.