Scribd
Cargar
222 vistas1 página

Algoritmo de Euclides: Guía Práctica

El algoritmo de Euclides puede utilizarse para encontrar el máximo común divisor (MCD) de dos números enteros de forma eficiente. El algoritmo involucra dividir repetidamente el divisor entre el residuo hasta obtener un residuo de cero, donde el último residuo no cero es el MCD de los números originales. Este proceso es finito ya que la secuencia de números no puede contener más de b términos, siendo b el número mayor original.

Cargado por

Ovigarto
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOC, PDF, TXT o lee en línea desde Scribd
222 vistas1 página

Algoritmo de Euclides: Guía Práctica

El algoritmo de Euclides puede utilizarse para encontrar el máximo común divisor (MCD) de dos números enteros de forma eficiente. El algoritmo involucra dividir repetidamente el divisor entre el residuo hasta obtener un residuo de cero, donde el último residuo no cero es el MCD de los números originales. Este proceso es finito ya que la secuencia de números no puede contener más de b términos, siendo b el número mayor original.

Cargado por

Ovigarto
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOC, PDF, TXT o lee en línea desde Scribd

Algoritmo de Euclides.

El máximo común divisor de dos enteros puede obtenerse escogiendo el mayor de todos los divisores comunes. Hay
un proceso más eficiente que utiliza repetidamente el algoritmo de la división. Este método se llama algoritmo de
Euclides.

El algoritmo de Euclides se describe de la forma siguiente: Dados dos enteros a y b cuyo máximo común divisor se
desea hallar, y asumiendo que a b > 0, (El método funciona también si a y b son negativos). Basta trabajar con los
valores absolutos de estos números, debido a que M.C.D (|a|, |b|) =M.C.D (a,b) se siguen los siguientes pasos:
a) Se usa el algoritmo de la división para obtener a = q 1b + r2 con
0 £ r1 < b. Si r1 = 0, entonces bïa y M.C.D.(a, b) = b.
b) Si r1 ¹ 0 se divide b por r1 y se producen enteros q2y r2 que satisfacen b =q2 r1 + r2 con 0 £ r2 < r1. Si r2 = 0 el
proceso termina y M.C.D.(a, b) = r1.
c) Si r2 ¹ 0 se procede a dividir r2 por r1 obteniendo r1 = q3 r2 + r3 con 0 £ r3 < r2.
d) Este proceso continua hasta que algún residuo cero aparece. Esto ocurre porque en la secuencia b > r1 > r2 > .....
³ 0 no puede haber más de b enteros. Es decir, el proceso es finito.
e) En estas circunstancias, el máximo común divisor de a y b no es más que el último residuo no cero del proceso
anterior.
Esto lo garantiza la aplicación reiterada del siguiente teorema.
8.7.1 Teorema.Sí a y b son enteros positivos con a ³ b y si a = qb + r entonces M.C.D.(a, b) = M.C.D.( b, r ).

Demostración
Sea d= M.C.D.(a, b). Luego dïa y dïb. De donde dï(a-qb) por teorema 2.2.3 y 2.2.4. Como a - qb = r, se tiene que
dïr. Luego d es divisor común de b y r.
Por otra parte, sea c un divisor común de b y r, luego cï(qb + r) por teorema 2.2.2 y 2.2.3. Como qb + r = a, entonces
cïa. De lo anterior tenemos que c es un divisor común de a y b.
Como d = M.C.D.(a, b) se tiene que c £ d. Luego d = M.C.D.(b, r).
Ejemplo 30.
Halle M.C.D.(12.378, 3.054).
12.378 = 4´3.054 + 162
3.054 = 18´162 + 138
162 = 1´138 + 24
138 = 5´24 + 18
24 = 1´18 + 6
18 = 3´6 + 0
Luego M.C.D.(12.378, 3.054) = 6 que es el último residuo no cero.

Ejemplo 31.
Como M.C.D.(12.378, 3.054) = 6 podemos utilizar el ejercicio anterior para encontrar enteros x y y que cumplan la
condición: 6 = 12.378x + 3.054y.
6 = 24 - 18
= 24 - (138 - 5´24)
= 6´24 - 138
= 6´(162 - 138) - 138
= 6´162 - 7´138
= 6´162 - 7´(3.054 - 18´162)
= 132´162 - 7´3.054
= 132´(12.378 - 4´3.054) - 7´3.054
= 132´12.378 + (-535) ´3.054
Luego x= 132; y = -535

También podría gustarte