1071 mod 465 é 141. 465 mod 141 é 42. 141 mod 42 é 15, 42 mod 15 é 12, 15 mod 12 é 3, e 12 mod 3 é 0. O último resto não nulo, 3, é o máximo divisor comum, e cada passo é legítimo pela mesma razão: qualquer número que divida ao mesmo tempo a e b também divide a − qb, então o par e o seu resto têm exatamente os mesmos divisores. Aqui não é preciso fatorar nada, e esse é o ponto prático: 3 é a resposta muito antes de alguém saber por que 1071 é 3·357.
O número de passos é o que se deve vigiar. Lamé demonstrou em 1844 que o algoritmo de Euclides sobre um par de inteiros nunca demora mais que umas cinco vezes o número de dígitos decimais do menor, e que os piores casos são números de Fibonacci consecutivos; é por isso que 141, 42, 15, 12, 3 nesta página encolhem rápido: aqui nada é vizinho de Fibonacci. A versão estendida da mesma tabela de restos também devolve coeficientes com 3 = 1071s + 465t, o ingrediente de toda rotina de divisão modular em um sistema de álgebra computacional.
Resposta
3
Como ler
15 mod 12, o último resto não nulo. Os dois primeiros links são os passos iniciais, 1071 mod 465 = 141 e 465 mod 141 = 42.
Fonte
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
Resolva na calculadora
Estes links abrem a calculadora adequada com os números deste problema já escritos. A linha de cima é o que a tela deveria mostrar: confira você mesmo.