Cálculos Del Máximo Común Divisor
Páginas: 4 (844 palabras)
Publicado: 5 de octubre de 2015
Cálculos del Máximo Común
Divisor
ALGORITMO DE EUCLIDES
Ejemplo: mcd(320,296)
320 = 276 ·1 + 44
276 = 44 ·6 + 12
44
= 12 ·3 +
8
12
=
8
·1 +
4
8
=
4
·2 +
0
Empieza dividiendo dosnúmeros.
Escribiendo el resultado de la forma
a = bq + r
a>b, 0<=r
Ejecutar hasta que el resto sea igual a
cero.
El último resto no-cero es el mcd.
En este caso, (320, 296) = 4.
Ejemplo: mcd(346,592)= 2
592 = 346 ·1 + 246
346 = 246 ·1 + 100
246 = 100 ·2 + 46
100 = 46 ·2 +
8
46
=
8
·5 +
6
8
=
6
·1 +
2
6
=
2
·3 +
0
Ejercicios
• MCD(4864, 3458) = 38
• MCD(54, 240)
= 6
• MCD(674,308)
= 2
ALGORITMO EXTENDIDO DE
EUCLIDES
Algoritmo Extendido de Euclides
• Teorema de Bézout
– Dados dos enteros positivos a y b con d=mcd(a,b),
existen enteros x, y tal que
ax + by = d
– Porejemplo: mcd(324, 148) = 4, retornado
324 · 16 + 148 · (-35) = 4.
– ¿Cómo se encuentran los valores de x, y?
Usando el Algoritmo de Euclides
• Se usa el algoritmo de Euclides para obtener los valores dex, y.
• Pasos:
1. Calcule el algoritmo de euclides
2. Despeje los restos (excepto para el último resto)
324 = 148 ·2 + 28
28
= 324 +(-2)· 148
148 = 28 ·5 +
8
8
= 148 +(-5)· 28
28
=
8
·3 +4
4
= 28 +(-3)· 8
8
=
4
·2 +
0
Paso 3. Sustitución
• Encontrar los valores de X, Y tal que
4 = x · 148 + y · 324.
• En el lenguaje de álgebra lineal, queremos expresar 4
como una “combinaciónlinear” de 148 y 324.
• Note que la última ecuación tiene una combinación
linear de 28 y 8, que no es lo que queremos.
4
= 28 +(-3)· 8
Paso 3. Sustitución
• Entonces que hacemos? Use la ecuaciónprevia para
substituir en la ecuación de “combinación linear”.
• Simplificamos la ecuación, pero sólo de los números
que están fuera en las cajas.
4
= 28 +(-3)· 8
4
= 28 +(-3)· ( 148 +(-5)· 28 )
4= 16 · 28 +(-3)· 148
Paso 3. Sustitución
• Tenemos ahora
4
= 16 · 28 +(-3)· 148
• Que expresa 4 cómo una combinación linear
de 28 y 148.
• Continua sustituyendo, en cada paso con la
ecuación...
Divisor
ALGORITMO DE EUCLIDES
Ejemplo: mcd(320,296)
320 = 276 ·1 + 44
276 = 44 ·6 + 12
44
= 12 ·3 +
8
12
=
8
·1 +
4
8
=
4
·2 +
0
Empieza dividiendo dosnúmeros.
Escribiendo el resultado de la forma
a = bq + r
a>b, 0<=r
Ejecutar hasta que el resto sea igual a
cero.
El último resto no-cero es el mcd.
En este caso, (320, 296) = 4.
Ejemplo: mcd(346,592)= 2
592 = 346 ·1 + 246
346 = 246 ·1 + 100
246 = 100 ·2 + 46
100 = 46 ·2 +
8
46
=
8
·5 +
6
8
=
6
·1 +
2
6
=
2
·3 +
0
Ejercicios
• MCD(4864, 3458) = 38
• MCD(54, 240)
= 6
• MCD(674,308)
= 2
ALGORITMO EXTENDIDO DE
EUCLIDES
Algoritmo Extendido de Euclides
• Teorema de Bézout
– Dados dos enteros positivos a y b con d=mcd(a,b),
existen enteros x, y tal que
ax + by = d
– Porejemplo: mcd(324, 148) = 4, retornado
324 · 16 + 148 · (-35) = 4.
– ¿Cómo se encuentran los valores de x, y?
Usando el Algoritmo de Euclides
• Se usa el algoritmo de Euclides para obtener los valores dex, y.
• Pasos:
1. Calcule el algoritmo de euclides
2. Despeje los restos (excepto para el último resto)
324 = 148 ·2 + 28
28
= 324 +(-2)· 148
148 = 28 ·5 +
8
8
= 148 +(-5)· 28
28
=
8
·3 +4
4
= 28 +(-3)· 8
8
=
4
·2 +
0
Paso 3. Sustitución
• Encontrar los valores de X, Y tal que
4 = x · 148 + y · 324.
• En el lenguaje de álgebra lineal, queremos expresar 4
como una “combinaciónlinear” de 148 y 324.
• Note que la última ecuación tiene una combinación
linear de 28 y 8, que no es lo que queremos.
4
= 28 +(-3)· 8
Paso 3. Sustitución
• Entonces que hacemos? Use la ecuaciónprevia para
substituir en la ecuación de “combinación linear”.
• Simplificamos la ecuación, pero sólo de los números
que están fuera en las cajas.
4
= 28 +(-3)· 8
4
= 28 +(-3)· ( 148 +(-5)· 28 )
4= 16 · 28 +(-3)· 148
Paso 3. Sustitución
• Tenemos ahora
4
= 16 · 28 +(-3)· 148
• Que expresa 4 cómo una combinación linear
de 28 y 148.
• Continua sustituyendo, en cada paso con la
ecuación...
Leer documento completo
Regístrate para leer el documento completo.