Algoritmo de Euclides

12/07/2012 14.421 Palabras

Algoritmo de Euclides tradicional Al dividir a {\displaystyle a} entre b {\displaystyle b} (números enteros), se obtiene un cociente q {\displaystyle q} y un residuo r {\displaystyle r} . Es posible demostrar que el máximo común divisor de a {\displaystyle a} y b {\displaystyle b} es el mismo que el de b {\displaystyle b} y r {\displaystyle r} (Sea c el máximo común divisor de a {\displaystyle a} y b {\displaystyle b} ,.Como a=bq+r y c divide a a {\displaystyle a} y a b {\displaystyle b} 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 a {\displaystyle a} y b {\displaystyle b} , 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 a {\displaystyle a} y 0 {\displaystyle 0} es precisamente a {\displaystyle a} . Para fines prácticos, la notación m c d ( a , b ) {\displaystyle \mathrm {mcd} (a,b)} significa máximo común divisor de a {\displaystyle a} y b {\displaystyle b} .

This website uses its own and third-party cookies in order to obtain statistical information based on the navigation data of our visitors. If you continue browsing, the acceptance of its use will be assumed, and in case of not accepting its installation you should visit the information section, where we explain how to remove or deny them.
OK | More info