Algoritmo de Euclides: MDC e divisões passo a passo

O algoritmo de Euclides calcula o máximo divisor comum, ou MDC, de dois inteiros por divisões sucessivas. A cada etapa, troca-se o par atual pelo divisor e pelo resto. Quando o resto chega a zero, o último divisor não nulo é o resultado. O método dispensa listar todos os divisores ou fatorar os números em primos.

Para aprender de forma verificável, é útil acompanhar três questões: como executar as divisões, por que o resultado permanece o mesmo e por que o processo termina. O exemplo com 252 e 198 será usado também para simplificar uma fração e encontrar uma combinação inteira desses números.

O que o MDC representa

Um inteiro positivo d divide a se existe um inteiro k tal que a = d × k. O MDC de dois números não simultaneamente nulos é o maior inteiro positivo que divide ambos. Para 18 e 24, os divisores positivos comuns são 1, 2, 3 e 6; portanto, MDC(18,24) = 6.

O termo “máximo” se refere ao tamanho do divisor, e não à quantidade de divisores. Quando o MDC vale 1, os números são chamados coprimos ou primos entre si. Eles não precisam ser individualmente primos: 8 e 15 são compostos, mas não compartilham divisor positivo maior que 1.

A entrada do algoritmo aqui é inteira. Um valor escrito como 2,5 não deve ser tratado como se fosse um resto de divisão inteira. Problemas com medidas decimais podem ser convertidos para uma unidade comum exata, quando isso fizer sentido, mas essa transformação precisa preservar o significado dos dados.

Exemplo completo: MDC de 252 e 198

A divisão euclidiana escreve a = q × b + r, com divisor b positivo e resto no intervalo 0 ≤ r < b. O quociente q informa quantas vezes o divisor cabe; o resto r informa o que sobra. A próxima etapa usa b e r, e não a e q.

O processo para na quarta divisão. Como 18 é o último divisor não nulo, MDC(252,198) = 18. Uma conferência imediata dá 252/18 = 14 e 198/18 = 11. Isso mostra que 18 divide ambos; a justificativa de que ele é o maior divisor comum exige o argumento de conservação apresentado a seguir.

Um erro frequente é responder zero por ser o último resto calculado. Zero funciona como condição de parada, não como resultado do MDC neste caso. Outro erro é parar na primeira divisão que produza um resto pequeno. É preciso continuar até que o resto seja exatamente zero, sem arredondamentos.

Por que substituir o par preserva a resposta

Se a = q × b + r, todo divisor comum de a e b também divide r = a − q × b. No sentido inverso, todo divisor comum de b e r divide a = q × b + r. Logo, os pares (a,b) e (b,r) têm exatamente os mesmos divisores comuns e, portanto, o mesmo MDC.

Esse é o invariante: uma propriedade que permanece verdadeira durante as transformações. As notas de Cornell sobre o algoritmo desenvolvem sua definição e demonstração. No exemplo, conservar o MDC conecta o par inicial (252,198) ao par final (18,0).

Todo inteiro positivo divide zero, pois 0 = d × 0. Assim, os divisores comuns de 18 e 0 são precisamente os divisores de 18, e o maior é 18. Como cada transformação conservou os divisores comuns, esse também é o MDC dos números originais.

Conservar uma resposta e terminar são exigências distintas. Um procedimento que repetisse o mesmo par conservaria o MDC, mas nunca encerraria o cálculo. Essa separação é útil no estudo de algoritmos: verificar somente alguns exemplos não demonstra que todo caso permitido termine nem que a saída sempre cumpra a especificação.

Uma descrição executável sem depender de linguagem

A ordem das atribuições importa. Se a for substituído antes de calcular o resto com os valores antigos, o programa pode perder uma entrada necessária. Guardar r temporariamente resolve isso. Uma atribuição simultânea também pode funcionar em linguagens que definem essa operação, mas não deve ser presumida em qualquer pseudocódigo.

A normalização dos sinais evita que diferentes regras de resto para números negativos compliquem esta versão. Por exemplo, MDC(−252,198) = 18. Se uma entrada for zero e a outra não, o resultado é o valor absoluto da entrada não nula. Para (0,0), não há maior divisor positivo; bibliotecas podem definir uma extensão convencional.

A função math.gcd de Python adota gcd(0,0) = 0 e devolve um resultado não negativo. Assim, math.gcd(252,198) retorna 18. Ao comparar uma demonstração matemática com uma biblioteca, separe o domínio originalmente definido das convenções usadas para tornar a função total no software.

Frações, agrupamentos e combinação de Bézout

Para simplificar 252/198, divida numerador e denominador por 18: a fração torna-se 14/11. Ela é irredutível porque os novos números são coprimos. O MDC também resolve um agrupamento hipotético: com 252 peças de um tipo e 198 de outro, o maior número de kits idênticos sem sobras é 18, cada um com 14 e 11 peças.

As mesmas divisões permitem escrever o MDC como combinação inteira dos números de entrada. Comece por 18 = 54 − 36. Da etapa anterior, 36 = 198 − 3 × 54. Substituindo, 18 = 4 × 54 − 198. Como 54 = 252 − 198, chega-se a 18 = 4 × 252 − 5 × 198.

A igualdade final pode ser conferida diretamente: 1.008 − 990 = 18. A versão que calcula também esses coeficientes é o algoritmo de Euclides estendido. O material da Rutgers explica a recuperação dos coeficientes; eles são úteis em equações diofantinas e aritmética modular.

Por exemplo, para 35 e 12, as divisões dão 35 = 2 × 12 + 11 e 12 = 1 × 11 + 1. Assim, 1 = 3 × 12 − 35. Como 3 × 12 deixa resto 1 ao dividir por 35, 3 é um inverso de 12 módulo 35. Esse inverso existe porque o MDC é 1.

Eficiência e escolhas de implementação

Usar o resto evita repetir muitas subtrações. Para um número grande e outro pequeno, subtrair o menor até reduzi-lo pode exigir inúmeras etapas; a divisão resume essas subtrações em uma operação. A análise do número de divisões, porém, não equivale ao custo de processar inteiros com milhares de algarismos.

O custo real depende da representação e do modelo de operações. Essa distinção também orienta a escolha de estruturas de dados. Em outro domínio, o algoritmo de Dijkstra mostra como uma operação central e sua implementação alteram o desempenho, embora resolva um problema diferente do MDC.

É necessário fatorar antes?

Não. A vantagem do método é obter o MDC diretamente por divisões com resto. A fatoração pode servir para conferir exemplos pequenos, mas não é uma etapa obrigatória. O exemplo didático da Emory apresenta justamente uma sequência de restos como caminho direto para o resultado.

E se o primeiro número for menor?

Pode-se trocar a ordem ou permitir a primeira divisão com quociente zero. Para a = 198 e b = 252, o resto é 198; o novo par é (252,198), que segue o exemplo. O MDC é simétrico: trocar os argumentos não muda a resposta, desde que o procedimento trate corretamente suas entradas.