O algoritmo de Euclides com 1071 e 465 chega ao mdc 3 passando pelos restos 141, 42, 15, 12

Tome restos até que um seja zero; o último resto não nulo é o máximo divisor comum.

Equações e álgebra · Nível: Resultado clássico · Atualizado em 2026-11-10

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.

Este é um site de ferramentas independente de terceiros. Não é afiliado à Casio, à Texas Instruments nem aos seus distribuidores, e não conta com patrocínio ou autorização deles. Os nomes de modelos e produtos são marcas comerciais de seus respectivos titulares e aparecem aqui apenas para identificar os dispositivos.

As sequências de teclas destes manuais foram redigidas a partir dos próprios dados de layout deste site — os mesmos que a calculadora online renderiza — junto com informações de produto disponíveis publicamente. As especificações e as configurações regionais são verificadas no dispositivo físico e no material mais recente do fabricante.