UNIVERSIDAD NACIONAL DE SAN MARTIN
ESCUELA DE POSGRADO
ALGORITMO DE
EUCLIDES
ASIGNATURA:
ANALISIS DE ALGORITMOS
DOCENTE:
ING. MG. HEBER GOMEZ
HURTADO
ESTUDIANTE:
2023 - I GINO MARCELO MESTANZA
BARDALES
TABLA DE CONTENIDO
INTRODUCCION......................................................................................................................................... 3
ALGORITMO DE EUCLIDES: ....................................................................................................................... 4
PASOS DEL ALGORITMO DE EUCLIDES ..................................................................................................... 5
ALGORITMO DE EUCLIDES EN UN LENGUAJE DE PROGRAMACION ......................................................... 7
TABLA DE FIGURAS
Figura 1 Método 1. .......................................................................................................... 5
Figura 2 Método 2. .......................................................................................................... 6
INTRODUCCION
En el presente informe estudiaremos los conceptos de máximo común divisor. Ahora nos
enfocaremos en un aspecto un poco más práctico sobre el máximo común divisor que
dejamos pendiente: ¿cómo lo calculamos? Para ello hablaremos de un procedimiento
conocido como el algoritmo de Euclides, el cual afirma que afirma que podemos aplicar
iteradas veces el algoritmo de la división en ciertos números específicos, comenzando
con dos enteros a y b para encontrar su máximo común divisor de dos enteros
positivos a y b.
Lo primero que haremos es explicar el procedimiento mediante el cual podemos
encontrar el máximo común divisor de dos números aplicando repetidamente el algoritmo
de la división. En la siguiente sección daremos la demostración de por qué funciona este
procedimiento. Hacia el final de la entrada también veremos que este mismo
procedimiento nos permite también escribir al máximo común divisor de dos
enteros a y b como combinación lineal de ellos.
ALGORITMO DE EUCLIDES:
El algoritmo de Euclides es un método antiguo y eficiente para calcular el máximo común
divisor (MCD). Fue originalmente descrito por Euclides en su obra Elementos.
El algoritmo de Euclides extendido es una ligera modificación que permite además
expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene
aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la
computación, entre otras.
Con unas ligeras modificaciones suele ser utilizado en computadoras electrónicas debido
a su gran eficiencia.
Euclides fue un matemático griego que recopiló varios datos en una obra llamada
Elementos. Esta obra es considerada como uno de los pillares de las matemáticas, y
Euclides el "padre de la geometría".
En Elementos, Euclides explica que el máximo común divisor de dos números se puede
encontrar dividiendo el número mayor por el número menor. Si la división es exacta, el
m.c.d. es el número menor.
Si la división no es exacta, entonces se toma el residuo, y se divide tantas veces como
haga falta para llegar a una división sin residuo. El m.c.d. es el último número por cuál
se puede dividir.
¿QUÉ ES EL MÁXIMO COMÚN DIVISOR (MCD)?
En matemáticas, denominamos máximo común divisor o MCD al mayor número que
divide exactamente a dos o más números a la vez. Como hablamos del mayor número
solo tendremos en cuenta los divisores positivos. Podemos decir que en “A” y “B”, es el
número mayor que los divide a los dos, tanto al número A como al número B.
En un ejemplo sobre el máximo común divisor de 18 y 24 es 6, porque 6 es el mayor de
los divisores comunes de 18 y 24 y lo escribimos MCD (18,24) = 6
PASOS DEL ALGORITMO DE EUCLIDES
1. Se divide el número mayor entre el menor.
2. Si la división es exacta, el divisor es el m.c.d.
3. Si la división no es exacta, dividimos el divisor entre el resto obtenido y
continuamos de esta forma hasta obtener una división exacta. El m.c.d. es el
último divisor.
¿CÓMO SE APLICA EL ALGORITMO DE EUCLIDES?
Para llevar adelante este cálculo se pueden aplicar 2 métodos. El primero consiste en
buscar todos los divisores de un número. Por otro lado, el segundo, en descomponer en
factores. Veamos cómo aplicar cada uno.
MÉTODO 1:
Vamos a calcular el Máximo común divisor de 6 y 9.
1. Escribimos todos los divisores de cada número (de 6 y de 9).
2. Señalar todos los divisores comunes.
3. Elegimos el divisor común mayor.
Figura 1Método 1
MÉTODO 2:
Vamos a calcular el Máximo común divisor de 16 y 21.
1. Factorizamos los números (16 y 21).
2. Escribimos en factores cada uno de los números, el 16 y el 21.
3. Ver cuáles son los factores comunes. En este caso, como ves, los números 16
y 21 no tienen factores comunes. Cuando no hay factores comunes entre los
números el máximo común divisor es 1.
Figura 2Método 2
ALGORITMO DE EUCLIDES EN UN LENGUAJE DE
PROGRAMACION
