Diferencia entre revisiones de «Algoritmo de Euclides»
Contenido eliminado Contenido añadido
Sin resumen de edición |
|||
Línea 3:
==Proposición==
Sean '''a,b''' enteros no nulos. Entonces mcd(a,b) = mcd(b,r) donde '''r''' es el único 0 < '''r''' < '''b''' tal que existe un entero q con '''''a= bq + r''''' (esto es, que r es el resto de la división de a por b)
Esta proposición nos indica que es igual de válido calcular el mcd(a,b) que el mcd(b,r), con la ventaja de que '''r''' es un entero de menor tamaño que el original a. Esto es aprovechado por el algoritmo de Euclides para el cálculo del máximo común divisor de dos números enteros.
| |||