1071 mod 465 es 141. 465 mod 141 es 42. 141 mod 42 es 15, 42 mod 15 es 12, 15 mod 12 es 3, y 12 mod 3 es 0. El último resto no nulo, 3, es el máximo común divisor, y cada paso es legítimo por la misma razón: cualquier número que divida a la vez a a y a b también divide a − qb, así que el par y su resto tienen exactamente los mismos divisores. Aquí no hace falta factorizar nada, y ese es el punto práctico: 3 es la respuesta mucho antes de que nadie sepa por qué 1071 es 3·357.
El número de pasos es lo que hay que vigilar. Lamé demostró en 1844 que el algoritmo de Euclides sobre un par de enteros nunca tarda más de unas cinco veces el número de dígitos decimales del menor, y que los peores casos son números de Fibonacci consecutivos; por eso 141, 42, 15, 12, 3 en esta página se encogen rápido: aquí nada es vecino de Fibonacci. La versión extendida de la misma tabla de restos también devuelve coeficientes con 3 = 1071s + 465t, el ingrediente de toda rutina de división modular en un sistema de álgebra computacional.
Respuesta
3
Cómo leerla
15 mod 12, el último resto no nulo. Los dos primeros enlaces son los pasos iniciales, 1071 mod 465 = 141 y 465 mod 141 = 42.
Fuente
Euclid, Elements VII.1-2 describes antanairesis — repeatedly subtracting the lesser from the greater until a common measure is reached; the remainder form used here is the same procedure written with division, and 1071 = 3²·7·17 against 465 = 3·5·31 confirms the answer the remainders give
Resuélvelo en la calculadora
Estos enlaces abren la calculadora adecuada con los números de este problema ya escritos. La línea de arriba es lo que debería mostrar la pantalla: compruébalo tú mismo.