Calculadora de algoritmo de Euclides

a = q * b + r, logo mdc(a, b) = mdc(b, r); repita até r = 0, e então b é a resposta

a = q * b + r

Uma rodada do algoritmo, escrita como equação. a é o maior dos dois números desta rodada, b o menor, q é quantas vezes inteiras b cabe em a, e r é o que sobra. É a mesma notação dos passos impressos na página, onde os números saem sem separador de milhar: 1.071 = 2 * 462 + 147 é uma rodada

a, b

Os dois números comparados. Eles trocam de identidade a cada rodada — o b de uma rodada vira o a da seguinte, e o r vira o novo b. É essa troca que explica por que os campos de entrada não se chamam dividendo e divisor: na primeira rodada 1.071 é o dividendo, na segunda é 462, e um rótulo certo para uma rodada fica errado nas outras

q

O quociente, quantas vezes inteiras b cabe em a. Ele é sempre pelo menos 1, porque o par é posto em ordem decrescente antes de o laço começar — e é também por isso que você nunca verá q = 0 aqui. A única rodada em que q não chama atenção é a última, em que o resto é zero e o quociente é exato

r

O resto, sempre menor que b e nunca negativo. A regra de parada do algoritmo é r = 0, impressa como a última rodada em vez de omitida: 147 = 7 * 21 + 0 é a linha que diz que a busca acabou e que 21 é a resposta

mdc(a, b)

O máximo divisor comum: o maior número inteiro que divide a e b sem deixar resto. A resposta é o b da rodada final, tirado direto do laço em vez de recalculado. Para 1.071 e 462 é 21, e é por isso que 1.071 = 21 × 51 e 462 = 21 × 22, e nenhum número maior divide os dois

610 = 1 * 377 + 233

A rodada de abertura do pior caso: números de Fibonacci consecutivos. Todo quociente aqui é 1 e os números quase não encolhem, e é isso que faz esse par levar treze rodadas. O teorema de Lamé diz que nenhum par desse tamanho consegue levar mais

Reduzir uma fração é o uso do dia a dia. Para escrever a fração formada por 462 e 1.071 na forma irredutível você precisa do máximo divisor comum dos dois, e esta página entrega esse número junto com a prova — 21, e as três rodadas que o produziram. Dividir o de cima e o de baixo por 21 dá 22/51, e os passos impressos são o que permite conferir a simplificação em vez de confiar nela. A mesma necessidade aparece sempre que uma razão precisa ser simplificada: relações de engrenagens, proporções de tela, desenhos em escala e quaisquer duas medidas que você queira expressar como proporção, e não como um par de números. O segundo uso é na programação e nas aulas, onde o algoritmo é ensinado como o primeiro interessante: ele termina, é rápido e está correto por uma razão que se vê em uma única equação. Ele é também a maneira padrão de calcular um inverso modular — a versão estendida carrega dois números extras pelas mesmas rodadas —, que é o passo dentro da geração de chaves RSA. Um terceiro uso é uma checagem rápida na fatoração. Descobrir que 1.071 é 3 × 357 e que 462 é 2 × 3 × 7 × 11 dá trabalho; descobrir que o máximo divisor comum deles é 21 são três divisões, então rodar esta página primeiro diz se a simplificação vai ser fácil antes de você começar. Quando você quer só a resposta e não o processo, a Calculadora de MDC faz a mesma pergunta de forma mais curta e aceita mais de dois números de uma vez; a Calculadora de MMC usa o fator para chegar ao mínimo múltiplo comum, já que mmc = (a / mdc) * b; e a Calculadora de resto cobre o que um único resto significa quando os números podem ser negativos, algo com que esta página nunca precisa lidar.

1. O par clássico dos livros: 1.071 e 462

   1. Quantas vezes 462 cabe em 1.071? Duas, e 2 × 462 = 924, deixando 1.071 − 924 = 147
   2. Agora o par é 462 e 147: 147 cabe em 462 três vezes, 3 × 147 = 441, deixando 21
   3. Agora o par é 147 e 21: 21 cabe em 147 exatamente sete vezes, deixando 0
   4. O resto é zero, então o algoritmo para e a resposta é 21

   A entrada padrão, e o exemplo com que este algoritmo costuma ser apresentado. Vale fazer duas conferências sobre o resultado. Divida os dois números por 21 e você chega a 51 e 22, que não têm fator em comum, e é isso que faz de 21 o máximo, e não apenas um divisor comum. E repare que nada aqui envolveu fatorar: para achar os fatores de 1.071 por divisão por tentativa você iria até 32, enquanto o algoritmo só dividiu um número por outro que já tinha em mãos. Três rodadas, cada uma mais barata que a anterior.

2. Uma rodada basta: 12 e 60

   1. Ponha o par em ordem decrescente: 60 primeiro, 12 depois
   2. 60 = 5 × 12 + 0, então 12 divide 60 exatamente
   3. O resto é zero logo de saída, então o algoritmo para depois de uma rodada
   4. A resposta é 12 — o menor dos dois, porque ele divide o maior

   A rodada não trivial mais curta possível, e o caso que mostra por que a rodada final é impressa em vez de pulada. A linha 60 = 5 * 12 + 0 é a resposta inteira: ela diz que o resto chegou a zero, que é a única maneira de este algoritmo parar. Tire essa linha e os passos ficariam vazios, e o leitor não teria como distinguir uma resposta de uma rodada de uma página que não rodou. Sempre que um número divide o outro exatamente, o máximo divisor comum é simplesmente o menor deles.

3. Números coprimos: 9 e 20

   1. 20 = 2 × 9 + 2, então o par vira 9 e 2
   2. 9 = 4 × 2 + 1, então o par vira 2 e 1
   3. 2 = 2 × 1 + 0, então o algoritmo para
   4. A resposta é 1, o que significa que 9 e 20 não têm nenhum fator acima de 1 em comum

   Um máximo divisor comum igual a 1 é uma resposta de verdade, não uma falha, e tem nome: os números são coprimos. É também o sinal de que a fração 9/20 já está na forma irredutível, então não há simplificação disponível. Repare que as rodadas não encolheram de imediato — o algoritmo desceu até 1 em três passos, porque nenhum dos números dividiu o outro exatamente. Pares coprimos são o caso comum conforme os números crescem: a chance de dois números sorteados ao acaso terem um fator em comum cai rápido, e é exatamente isso que torna o método útil para montar um inverso modular em criptografia.

Os dois números precisam ser inteiros, e os dois precisam estar entre 1 e 1.000.000. O zero é recusado em vez de tratado como caso especial. O máximo divisor comum de a e 0 é a, que é uma resposta perfeitamente boa, mas esta página não consegue mostrá-la: a primeira rodada seria a = q * 0 + r, e esse q não existe. Em vez de imprimir um processo com um buraco, a página recusa a entrada. Números negativos são recusados pelo mesmo motivo — os passos, como são impressos, pressupõem que os dois números sejam pelo menos 1, e um operando negativo exigiria uma regra sobre o que o quociente e o resto significam que esta página não enuncia em lugar nenhum. O teto de 1.000.000 não tem a ver com o algoritmo, que rodaria tranquilamente em números bem maiores; ele existe para que toda subtração, multiplicação e resto no caminho seja exato na aritmética comum de dupla precisão, e para que os passos impressos não cheguem a um comprimento que deixe de ser legível. Dois números até bem pequenos podem produzir muitas rodadas — 610 e 377 levam treze —, mas na prática a contagem fica limitada pelo teto, e a tabela de referência tem uma coluna de rodadas justamente para você vê-la variar. Os passos são impressos como equações — a = q * b + r, separadas por pontos e vírgulas — e não como divisão longa, então quem procura o chaveamento familiar da conta armada não vai encontrá-lo aqui. As entradas são intercambiáveis: a página as ordena de forma decrescente antes de começar, então não dá para usar esta página para ver como seria 3 = 0 * 5 + 3, porque essa rodada nunca é produzida. Os passos são texto puro: os números dentro deles saem como uma sequência corrida de algarismos, sem nenhum separador de milhar, enquanto o MDC é impresso como número e segue a grafia numérica do idioma — as duas coisas ficam no mesmo painel e usam grafias diferentes. Se os seus números podem ser negativos, ou se você quer a convenção do resto explicitada, a Calculadora de resto é a página para essa pergunta.

O que é o máximo divisor comum, em uma frase?

O maior número inteiro que divide os dois números exatamente, sem deixar resto. Para 1.071 e 462 é 21: 1.071 = 21 × 51 e 462 = 21 × 22, e 51 e 22 não têm fator em comum, e é isso que faz de 21 o máximo. Repare que 3 e 7 também dividem os dois números — são divisores comuns, só não são o maior. A saída principal da página é sempre esse número, e os passos abaixo dele são a prova.

Por que o último passo sempre termina em + 0?

Porque um resto igual a zero é a única coisa que para o algoritmo. O laço troca o par por um par menor — o segundo número e o resto —, e os números caem a cada rodada, então eles têm de chegar a zero em algum momento. 147 = 7 * 21 + 0 é a rodada em que isso acontece, e o máximo divisor comum é o divisor dessa rodada, 21. A página a imprime em vez de escondê-la porque uma lista de passos que parasse no último resto diferente de zero deixaria o leitor concluir sozinho que a busca tinha acabado.

A ordem em que digito os dois números importa?

Não. A página os põe em ordem decrescente antes da primeira rodada, então 462 e 1.071 produzem exatamente as mesmas três linhas que 1.071 e 462. Isso é uma escolha, e não uma propriedade do algoritmo — a regra mdc(a, b) = mdc(b, a) garante que qualquer ordem dá a resposta certa —, mas sem a ordenação a primeira linha seria 3 = 0 * 5 + 3 no par 3 e 5, que é uma divisão legal, mas passa a impressão de que dividir um número pequeno por um maior faz parte do método. É também por isso que os campos de entrada se chamam primeiro número e segundo número, e não dividendo e divisor: esses dois papéis trocam a cada rodada.

O que significa uma resposta igual a 1?

Que os dois números não compartilham nenhum fator acima de 1, o que é uma resposta completa e não uma falha. Esses números são chamados de coprimos, e o par 9 e 20 desta página é um exemplo. Isso também diz algo prático: a fração 9/20 já está na forma irredutível, então não há simplificação disponível. Conforme os números crescem, os pares coprimos viram o caso comum, e é por isso que o método importa em criptografia — montar uma chave RSA significa achar números que não compartilhem fator com um número dado.

Números maiores sempre levam mais rodadas?

Não, e a tabela de referência está ali para tornar isso concreto. 1.000.000 e 999.998 terminam em duas rodadas, enquanto 610 e 377 — três dígitos cada um — levam treze. O que força muitas rodadas não é o tamanho, e sim a lentidão com que os números encolhem, e os pares que encolhem mais devagar são os números de Fibonacci consecutivos, em que todo resto fica próximo do divisor. Esse resultado é o teorema de Lamé, e ele impõe um teto à contagem de rodadas que cresce apenas com o número de dígitos, e é por isso que o algoritmo é considerado rápido.

Qual é a diferença entre isto e simplesmente fatorar os dois números?

Fatorar dá muito mais trabalho, e é um trabalho que esta página nunca faz. Para fatorar 1.071 por divisão por tentativa você testaria divisores até a raiz quadrada dele, cerca de 32; o algoritmo, em vez disso, divide um número por outro que já tem em mãos e termina em três rodadas. Em números pequenos como esses a diferença é invisível, mas a fatoração fica dramaticamente mais difícil conforme os números crescem, enquanto o algoritmo de Euclides quase não sente. É essa distância a razão inteira de ele ainda ser ensinado, e é também por isso que a resposta acima sai do próprio laço, e não de uma segunda conta — rodar as duas arriscaria que os passos impressos discordassem do número impresso acima deles.

• Euclidean Algorithm — the recurrence gcd(a, b) = gcd(b, a mod b), the proof that it terminates, and the connection to continued fractions — Wolfram MathWorld (United States)
• Greatest Common Divisor — what the greatest common factor is, and why gcd(a, 0) = a is the base case the algorithm stops on — Wolfram MathWorld (United States)
• Lamé's Theorem — the result that the pair taking the most rounds for its size is always a pair of consecutive Fibonacci numbers — Wolfram MathWorld (United States)