Foros de matemática
21/10/2017, 01:49:05 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Algoritmo extendido de Euclides  (Leído 19996 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 39.873


Ver Perfil
« : 04/11/2009, 03:26:37 pm »

Dados dos números naturales [texx]a,b[/texx], si [texx]d=m.c.d(a,b)[/texx] es su máximo cómun divisor, existen enteros [texx]x,y[/texx] tales que:

[texx]ax+by=d[/texx]          (1)

El algoritmo extendido de Euclides nos da un método para calcular [texx]d,x,y[/texx].

Pasos a seguir:

Spoiler (click para mostrar u ocultar)

Ejemplos:

I) Calcular [texx]d=m.c.d(12,17)[/texx] y [texx]x,y\in Z[/texx] tales que [texx]12x+17y=d[/texx]

Spoiler (click para mostrar u ocultar)

II) Calcular [texx]d=m.c.d(21,15)[/texx] y [texx]x,y\in Z[/texx] tales que [texx]21x+15y=d[/texx]

Spoiler (click para mostrar u ocultar)
En línea
Click
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 160


Ver Perfil
« Respuesta #1 : 31/05/2010, 02:48:52 pm »

En el segundo ejemplo:

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


No debería decir:
"Calcular [texx]d=m.c.d(21,15)[/texx] y [texx]x,y\in Z[/texx] tales que [texx]\color{red}21x+15y=d[/texx]"?
En línea
Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 39.873


Ver Perfil
« Respuesta #2 : 31/05/2010, 05:35:12 pm »

Hola

 Tienes razón. Ya lo corregí.

Saludos.
En línea
prometeo
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 148



Ver Perfil
« Respuesta #3 : 15/03/2012, 01:51:39 pm »

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: [texx]a\textsf{ y } b[/texx]
OUTPUT: [texx](a,b)[/texx] y valores [texx]s,t[/texx] tales que [texx](a,b)=as+bt[/texx]
1.[texx](r_0,r_1,s_0,t_0,s_1,t_1):=(a,b,1,0,0,1)[/texx]
2.[texx]i:=1[/texx]
3.Mientras [texx]r_i\neq{0}[/texx] hacer lo siguiente:
      3.1. Dividir [texx]r_{i-1}[/texx] entre [texx]r_i[/texx] para obtener un cociente [texx]q_i[/texx] y el resto [texx]r_{i+1}[/texx]
      3.2. [texx]s_{i+1}:=s_{i-1} - q_is_i[/texx]
      3.3. [texx]t_{i+1}:=t_{i-1} - q_it_i[/texx]
      3.4. [texx]i:=i+1[/texx]
4.El resultado final es [texx]r_{i-1}=(a,b)[/texx] y [texx]r_{i-1}=as_{i-1}+bt_{i-1}[/texx]
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,
En línea

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)
Hernan_ER
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.452


Ver Perfil
« Respuesta #4 : 19/03/2013, 09:07:48 pm »

¿Qué ocurre si uno de a y b es negativo? ¿Sigue funcionando?
En línea
Carlos Ivorra
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 8.463


Ver Perfil WWW
« Respuesta #5 : 04/04/2013, 04:43:40 pm »

¿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.
En línea
sebasuy
Moderador Global
Pleno*
*

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Uruguay Uruguay

Mensajes: 1.047


Ver Perfil
« Respuesta #6 : 14/11/2013, 01:05:37 pm »

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

Saludos.
En línea

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

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10


Ver Perfil
« Respuesta #7 : 14/10/2017, 02:14:02 pm »

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:

[texx]\displaystyle\prod_{i=1}^k p_i[/texx]

tal que: [texx]p_i \equiv 1 \mod{4}, [/texx]

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

[texx] m^2 + 1 \equiv 0 \mod{n}[/texx] (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:
[texx]\frac{n}{m}[/texx]

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

[texx]a^2 + b^2 = n[/texx]

Ejemplo: Tomando [texx]n = 65= 5 * 13[/texx] 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á:

[texx]k = 2^{(i-1)}[/texx]

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

Por tanto: [texx]65 = 7^2 + 4^2[/texx]

El segundo es inmediato: [texx]m_2 =8 [/texx] ya que [texx]8^2 +1 = 65 * 1[/texx].

Por tanto: [texx]65 = 8^2 + 1^2[/texx]
En línea

"Uno no entiende las matemáticas, más bien, se acostumbra a ellas"
Alan Turing
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!