Download Algoritmo de Euclides para buscar M

Algoritmo de Euclides para buscar M.C.D.
El algoritmo de Euclides para encontrar el Máximo común divisor entre 2
números se basa en la siguiente idea:
Definición: Si a y b son 2 números naturales, el M.C.D. entre a y b es el mayor
número natural que divide tanto a a como a b .
¿Qué significa que un número natural d divida a a ?
Quiere decir que al hacer la división a  d no hay resto. En otras palabras, que
existe un número c natural tal que a  d  c
Para referirnos al M.C.D. entre a y b usaremos la notación a, b
Por ejemplo el M.C.D. entre 15 y 25 es 15,25  5 . Y 6,9  3 . Etc.
Un modo de encontrar el máximo común divisor entre 2 números naturales es
factorizar a ambos números como producto de números primos y ver los
números primos que aparecen en ambas factorizaciones. El producto de los
números primos que aparecen en ambas factorizaciones a la potencia mínima
en que aparecen entre las 2 factorizaciones será el M.C.D. entre ambos
números. Pero para números grandes puede ser bastante molesto encontrar la
factorización.
Euclides propuso un modo de encontrar el máximo común divisor entre 2
números. El algoritmo de Euclides se basa en lo siguiente:
Si a  b son 2 números enteros y
a  c  b  r resto r (con 0  r  b ) al hacer a  b , entonces vale que: a, b  b, r 
Bueno, no es difícil probar que esto vale ya que a, b por ser el M.C.D. divide
tanto a a como a b . Pero si divide a b también divide a c  b . Pero si divide a 2
números también divide a su suma o a su resta. Entonces a, b divide a
a  cb  r .
Pero entonces llegamos a que a, b divide a ambos b y r por lo tanto
a, b  b, r  que era el mayor número que dividía a ambos b y r .
Con un razonamiento similar se prueba que b, r  divide a b y a c  b  r  a
Entonces b, r  divide tanto a b como a a . Entonces b, r   a, b
Pero entonces no les queda otra que ser el mismo número. O sea:
a, b  b, r 
Entonces, veamos en un ejemplo, como es el algoritmo de Euclides para
encontrar el M.C.D entre 2 números.
Ejercicio. Encontrar usando el Algoritmo de Euclides el M.C.D entre 402 y 518.
518  1  402  116
402  3  116  54
116  2  54  8
54  6  8  6
8  1 6  2
6  3 2  0
El algoritmo termina cuando una división nos da con resto 0. Y el último resto al
que llegamos distinto de 0 será el máximo común divisor. O sea 402,518  2
Veamos otro ejemplo:
Encontrar 60,135
135  2  60  15
60  4  15  0 Acá termina el algoritmo y el último resto distinto de 0 es
15. Entonces
60,135  15
Ejercicios:
Calcular 314,159 y 4144,7696
Resolución enviada por Juan Costa Ponce:
Respuestas: sigue en la página siguiente
a)
(314,159) = 1
314= 1. 159 + 155
159= 1. 155 + 4
155= 38.4 + 3
4= 1.3 + 1
3= 3.1 + 0
b)
(4144,7696)= 592
7696= 1. 4144 + 3552
4144= 1.3552 + 592
3552= 6.592 + 0