Algoritmo de Euclides

Algoritmo de Euclides tradicional

Al dividir entre (números enteros), se obtiene un cociente y un residuo . Es posible demostrar que el máximo común divisor de y es el mismo que el de y (Sea c el máximo común divisor de y ,.Como a=bq+r y c divide a y a divide también a r.Si existiera otro número mayor que c que divide a b y a r, también dividiría a a , por lo que c no sería el mcd de y , lo que contradice la hipótesis). Éste es el fundamento principal del algoritmo. También es importante tener en cuenta que el máximo común divisor de cualquier número y es precisamente . Para fines prácticos, la notación significa máximo común divisor de y .

Este sitio web utiliza cookies, propias y de terceros con la finalidad de obtener información estadística en base a los datos de navegación. Si continúa navegando, se entiende que acepta su uso y en caso de no aceptar su instalación deberá visitar el apartado de información, donde le explicamos la forma de eliminarlas o rechazarlas.
Aceptar | Más información