Algoritmo de Euclides: como calcular o MDC passo a passo

O algoritmo de Euclides é uma das ideias mais bonitas e úteis de toda a matemática elementar. Com apenas algumas divisões, ele encontra o máximo divisor comum de dois números, mesmo quando eles são grandes e difíceis de fatorar. Foi descrito por Euclides na obra Os Elementos, escrita por volta de 300 antes de Cristo, e continua exatamente igual hoje, ensinado na escola e usado dentro de computadores e de sistemas de criptografia. Neste guia, escrito como uma aula completa, vamos entender o que é o máximo divisor comum, como o algoritmo funciona passo a passo, por que ele dá certo, como derivar o mínimo múltiplo comum a partir dele e onde tudo isso aparece na prática. O conteúdo serve tanto para quem está no ensino fundamental quanto para quem retoma os estudos na educação de jovens e adultos e para quem se prepara para o ENEM e para concursos. Para conferir cada conta enquanto lê, use a calculadora do algoritmo de Euclides.

O que é o máximo divisor comum

Antes de falar do algoritmo, vale relembrar o que estamos procurando. Um divisor de um número é qualquer valor que cabe nele um número inteiro de vezes, sem deixar resto. Por exemplo, os divisores de 12 são 1, 2, 3, 4, 6 e 12, e os divisores de 18 são 1, 2, 3, 6, 9 e 18. Quando olhamos os divisores que aparecem nas duas listas, encontramos 1, 2, 3 e 6: esses são os divisores comuns de 12 e 18. O maior deles, o 6, é o máximo divisor comum, que abreviamos como MDC.

O MDC responde a uma pergunta muito concreta: qual é o maior tamanho de parte igual em que conseguimos dividir duas quantidades ao mesmo tempo. Se temos 12 balas de um tipo e 18 de outro e queremos montar sacolas iguais usando as duas, sem sobrar nada, o maior número de sacolas possível é o MDC, 6, com 2 balas de um tipo e 3 de outro em cada sacola. Achar os divisores um a um funciona para números pequenos, mas fica trabalhoso quando os números crescem. É aí que o algoritmo de Euclides brilha. Para listar todos os divisores de um número, você pode usar a calculadora de fatores de um número.

A ideia central do algoritmo

O algoritmo de Euclides parte de uma observação simples e poderosa sobre a divisão. Quando dividimos um número maior por um menor, obtemos um quociente e um resto, e esse resto é sempre menor que o divisor. A sacada de Euclides foi perceber que o conjunto de divisores comuns dos dois números de partida é exatamente o mesmo conjunto de divisores comuns do menor número com o resto. Em outras palavras, podemos trocar o problema original por um problema menor, com números mais simples, sem mudar a resposta.

Como cada passo deixa os números menores, em algum momento chegamos a um resto igual a zero. A partir daí não dá para continuar dividindo, e o último divisor que usamos é o máximo divisor comum. Toda a engenhosidade do método está em repetir essa troca por um problema menor até a resposta aparecer sozinha. Por isso ele é tão rápido: a cada divisão, o tamanho dos números cai bastante, e poucas etapas bastam mesmo para valores grandes.

Passo a passo por divisões sucessivas

Vamos calcular o MDC de 48 e 18, acompanhando cada divisão. Começamos dividindo o maior pelo menor. A primeira conta é 48 dividido por 18: cabe 2 vezes, pois 2 vezes 18 é 36, e sobra 12. Guardamos esse resto. Para a próxima etapa, o divisor da conta anterior, 18, passa a ser o dividendo, e o resto, 12, passa a ser o divisor.

A segunda conta é 18 dividido por 12: cabe 1 vez, pois 1 vez 12 é 12, e sobra 6. De novo, o divisor 12 vira o próximo dividendo e o resto 6 vira o próximo divisor. A terceira conta é 12 dividido por 6: cabe 2 vezes exatas, pois 2 vezes 6 é 12, e o resto é 0. Como o resto chegou a zero, paramos. O último divisor que usamos foi 6, então o MDC de 48 e 18 é 6. Repare como cada linha reaproveita os números da linha anterior, formando uma cadeia de divisões. A calculadora mostra essa tabela completa, com dividendo, divisor, quociente e resto em cada etapa.

Vale fixar a regra de transição entre as linhas, que é o coração do método: o divisor de uma conta vira o dividendo da conta seguinte, e o resto vira o novo divisor. Repetimos isso até o resto dar zero. Escrever as contas uma embaixo da outra, em forma de tabela, ajuda a não se perder e deixa claro o caminho até a resposta.

Por que o método funciona

Pode parecer mágica que trocar os números por outros menores não mude o MDC, mas há uma razão clara. Suponha que um número d divida tanto 48 quanto 18. Como 48 é igual a 2 vezes 18 mais 12, podemos isolar o 12: ele é igual a 48 menos 2 vezes 18. Se d divide 48 e divide 18, então d divide qualquer combinação desses dois, inclusive 48 menos 2 vezes 18, ou seja, d divide 12. Isso mostra que todo divisor comum de 48 e 18 também divide o resto 12.

O caminho de volta também vale. Se um número divide 18 e divide 12, então ele divide 2 vezes 18 mais 12, que é justamente 48. Logo, os divisores comuns de 18 e 12 são exatamente os mesmos divisores comuns de 48 e 18. Como o par de números mudou, mas o conjunto de divisores comuns ficou igual, o maior deles, o MDC, também é o mesmo. Esse argumento se repete em cada etapa do algoritmo, garantindo que, do começo ao fim, estamos sempre procurando o mesmo MDC, só que com números cada vez menores até a resposta se revelar.

Um exemplo com números maiores

Para ver a eficiência do método, vamos calcular o MDC de 1071 e 462, um exemplo clássico. A primeira conta é 1071 dividido por 462: cabe 2 vezes, pois 2 vezes 462 é 924, e sobra 147. A segunda conta é 462 dividido por 147: cabe 3 vezes, pois 3 vezes 147 é 441, e sobra 21. A terceira conta é 147 dividido por 21: cabe 7 vezes exatas, pois 7 vezes 21 é 147, e o resto é 0. Paramos aqui. O último divisor foi 21, então o MDC de 1071 e 462 é 21.

Repare que precisamos de apenas três divisões para resolver um problema com números na casa dos milhares. Tentar listar todos os divisores de 1071 e de 462, ou fatorar os dois em primos, daria muito mais trabalho. Essa rapidez é a grande vantagem do algoritmo de Euclides e o motivo de ele continuar sendo usado dentro de programas de computador, onde precisa rodar milhões de vezes com eficiência.

A versão por subtrações sucessivas

Existe uma forma ainda mais antiga do algoritmo, que usa subtrações no lugar de divisões. A ideia é a mesma: enquanto os dois números forem diferentes, subtraímos o menor do maior e ficamos com o resultado no lugar do maior. Repetimos isso até os dois números ficarem iguais, e esse valor comum é o MDC.

Vejamos 48 e 18 por subtração. Como 48 é maior, fazemos 48 menos 18, que dá 30, e ficamos com 30 e 18. Agora 30 menos 18 dá 12, e ficamos com 18 e 12. Depois 18 menos 12 dá 6, e ficamos com 12 e 6. Em seguida 12 menos 6 dá 6, e ficamos com 6 e 6. Os dois números ficaram iguais a 6, então o MDC é 6, o mesmo resultado de antes. A versão por subtração ajuda a entender a intuição do método, mas a versão por divisão é mais rápida, porque uma única divisão resolve de uma vez várias subtrações iguais. Subtrair 18 de 48 duas vezes, por exemplo, é o mesmo que dividir 48 por 18 e olhar o resto.

Quando o resto chega a zero

Um detalhe importante é interpretar corretamente o momento da parada. O algoritmo termina quando uma divisão dá resto zero, e o MDC é o divisor dessa última conta, não o resto. O resto zero é apenas o sinal de que aquele divisor cabe um número exato de vezes no dividendo, ou seja, divide os dois números daquela etapa, e por isso divide também os números originais.

Há um caso particular que confunde no começo: quando um número já divide o outro. Por exemplo, o MDC de 100 e 25. A primeira conta é 100 dividido por 25, que cabe 4 vezes exatas e dá resto 0 logo na primeira divisão. Como o resto já é zero, o MDC é o divisor 25. Isso faz sentido, pois 25 divide tanto 25 quanto 100, e nenhum número maior que 25 divide o 25. Sempre que um número for múltiplo do outro, o MDC é o menor dos dois.

Números primos entre si

Quando o algoritmo termina com MDC igual a 1, dizemos que os dois números são primos entre si, ou coprimos. Isso significa que eles não compartilham nenhum divisor maior que 1, mesmo que nenhum dos dois seja um número primo isoladamente. Um bom exemplo é 8 e 15: o MDC é 1, embora 8 seja 2 vezes 4 e 15 seja 3 vezes 5, porque eles não têm fatores em comum.

Reconhecer números primos entre si é muito útil ao trabalhar com frações. Uma fração está na sua forma irredutível exatamente quando o numerador e o denominador são primos entre si, ou seja, quando o MDC entre eles é 1 e não há mais nada para simplificar. Por isso o algoritmo de Euclides é a ferramenta certa para simplificar frações com segurança: basta dividir o numerador e o denominador pelo MDC para chegar à forma irredutível. A calculadora de simplificação de frações usa exatamente essa ideia.

A relação entre MDC e MMC

O algoritmo de Euclides resolve o MDC, mas, com um passo a mais, ele também entrega o mínimo múltiplo comum, o MMC. Para dois números, vale uma relação simples e elegante: o produto dos dois números é igual ao produto do MDC pelo MMC. Em símbolos, a vezes b é igual a MDC vezes MMC. Isso permite achar o MMC sem nenhum esforço extra: depois de calcular o MDC, basta multiplicar os dois números e dividir pelo MDC.

Para 48 e 18, já sabemos que o MDC é 6. Então o MMC é 48 vezes 18 dividido por 6. O produto 48 vezes 18 é 864, e dividido por 6 dá 144. Logo, o MMC de 48 e 18 é 144. Para evitar números muito grandes, é prático dividir antes de multiplicar: 48 dividido por 6 dá 8, e 8 vezes 18 dá 144, o mesmo resultado. Se você quiser comparar com o método tradicional por fatoração, a calculadora de MMC e MDC mostra os dois caminhos lado a lado.

Comparando com a fatoração em primos

Na escola, é comum aprender a calcular o MDC fatorando cada número em primos e multiplicando os fatores comuns com o menor expoente. Esse método é intuitivo e ajuda a entender a estrutura dos números, mas tem uma fraqueza: fatorar números grandes é difícil e demorado, porque pode ser complicado descobrir os fatores primos. O algoritmo de Euclides não precisa fatorar nada; ele só divide, e por isso é muito mais rápido para números grandes.

Os dois métodos sempre chegam ao mesmo MDC, então a escolha depende do contexto. Para números pequenos e para entender o porquê do resultado, a fatoração é ótima. Para números grandes, para cálculos rápidos e para programar um computador, o algoritmo de Euclides é a melhor opção. Saber os dois caminhos dá flexibilidade e ajuda a conferir um resultado pelo outro. Para fatorar um número e ver seus divisores, a calculadora de fatores é um bom apoio.

Aplicações no dia a dia e na tecnologia

O máximo divisor comum, e o algoritmo que o calcula, aparecem em situações bem práticas. Ao repartir duas quantidades em grupos iguais do maior tamanho possível, o número de grupos é o MDC. Ao planejar o corte de ladrilhos quadrados para cobrir um piso retangular sem sobras nem cortes, o maior lado possível do ladrilho é o MDC das medidas do piso. Em receitas e misturas, o MDC ajuda a reduzir proporções à forma mais simples.

Na tecnologia, o algoritmo de Euclides é ainda mais presente, embora invisível. Ele é usado dentro de programas para trabalhar com frações exatas, para reduzir razões e, numa versão estendida, para resolver equações e encontrar inversos em criptografia. Sistemas de segurança que protegem senhas, mensagens e transações bancárias dependem de propriedades de números primos entre si, e o algoritmo de Euclides é a ferramenta que verifica e calcula esses valores com rapidez. Uma ideia de mais de dois mil anos continua, portanto, no centro da matemática que faz a internet funcionar com segurança.

Mais exemplos resolvidos

Praticar com vários pares de números é a melhor forma de fixar o método. Vamos resolver o MDC de 252 e 198. A primeira conta é 252 dividido por 198: cabe 1 vez, pois 1 vez 198 é 198, e sobra 54. A segunda conta é 198 dividido por 54: cabe 3 vezes, pois 3 vezes 54 é 162, e sobra 36. A terceira conta é 54 dividido por 36: cabe 1 vez, pois 1 vez 36 é 36, e sobra 18. A quarta conta é 36 dividido por 18: cabe 2 vezes exatas, e o resto é 0. O último divisor foi 18, então o MDC de 252 e 198 é 18. Em quatro divisões resolvemos um problema que daria muito trabalho por listagem de divisores.

Agora um caso de números primos entre si, para ver o algoritmo terminar em 1. Vamos calcular o MDC de 35 e 24. A primeira conta é 35 dividido por 24: cabe 1 vez, sobra 11. A segunda é 24 dividido por 11: cabe 2 vezes, pois 2 vezes 11 é 22, e sobra 2. A terceira é 11 dividido por 2: cabe 5 vezes, pois 5 vezes 2 é 10, e sobra 1. A quarta é 2 dividido por 1: cabe 2 vezes exatas, e o resto é 0. O último divisor foi 1, então o MDC de 35 e 24 é 1, e os dois números são primos entre si. Isso confirma que a fração trinta e cinco sobre vinte e quatro já está na forma irredutível, pois não há divisor comum maior que 1 para simplificar.

Vale ainda um exemplo em que um número é múltiplo do outro, para fixar o caso de parada imediata. O MDC de 60 e 15: a primeira conta é 60 dividido por 15, que cabe 4 vezes exatas e dá resto 0 logo de cara. Como o resto já é zero, o MDC é o divisor 15. Esse padrão se repete sempre que o menor número divide o maior: o MDC é o próprio menor. Reconhecer esse atalho economiza tempo em provas e evita contas desnecessárias.

O algoritmo de Euclides estendido

Existe uma versão mais completa do método, chamada algoritmo de Euclides estendido, que faz mais do que achar o MDC. Além de calcular o máximo divisor comum, ela encontra dois números inteiros que, multiplicados pelos valores originais e somados, dão exatamente o MDC. Essa igualdade é conhecida como identidade de Bézout, e ela diz que, para quaisquer dois números, sempre existe uma combinação desse tipo que resulta no MDC deles.

Para entender a ideia sem entrar em contas pesadas, pense no exemplo de 48 e 18, cujo MDC é 6. O algoritmo estendido encontra dois inteiros, um para o 48 e outro para o 18, tais que a soma dos produtos dá 6. No caso, vale a combinação que usa o 48 uma vez positivo e o 18 com o fator adequado para chegar ao 6. O ponto importante não é decorar os coeficientes, e sim saber que eles sempre existem e que o algoritmo os calcula refazendo as divisões de trás para frente. Essa identidade é a base de aplicações avançadas, como encontrar o inverso de um número em aritmética modular, que é justamente o que sustenta vários sistemas de criptografia modernos. Para o estudo no nível escolar, basta guardar que o algoritmo de Euclides, na sua forma estendida, conecta o MDC a uma combinação dos dois números, abrindo a porta para a matemática usada em segurança digital.

Erros comuns ao usar o algoritmo

O primeiro engano frequente é confundir o que é a resposta no momento da parada. Quando o resto dá zero, o MDC é o divisor daquela conta, e não o resto, que é zero, nem o quociente. Vale repetir para si mesmo: o MDC é o último divisor usado, o último resto diferente de zero da sequência.

O segundo erro é trocar a regra de transição entre as linhas. O correto é o divisor virar o próximo dividendo e o resto virar o próximo divisor. Quem inverte isso acaba repetindo a conta ou se perdendo. O terceiro deslize é misturar o algoritmo do MDC com o do MMC; lembre que o algoritmo de Euclides calcula o MDC, e o MMC vem depois, pela relação com o produto dos números. Por fim, atenção a parar cedo demais: só encerramos quando o resto é exatamente zero, e não quando ele apenas fica pequeno. Conferir o resultado na calculadora ajuda a pegar esses erros enquanto se aprende.

Como praticar com segurança

A melhor forma de dominar o algoritmo de Euclides é resolver vários exemplos à mão e conferir cada um. Comece com pares pequenos, como 24 e 36, ou 35 e 14, e escreva a tabela de divisões linha por linha, anotando dividendo, divisor, quociente e resto. Depois passe para números maiores, como 252 e 198, para sentir como o método continua simples mesmo quando as contas crescem. Sempre que terminar, verifique se o MDC encontrado realmente divide os dois números originais.

Conforme você ganha confiança, experimente também derivar o MMC pela relação com o produto e identificar quando os números são primos entre si. Praticar as duas saídas do mesmo cálculo, o MDC e o MMC, fixa a relação entre eles e prepara o terreno para problemas de frações, razões e repartições. A calculadora do algoritmo de Euclides mostra a tabela completa de cada exercício, então você pode resolver primeiro no papel e usar a ferramenta só para conferir, que é a forma mais eficiente de aprender de verdade.

Um pouco de história

O algoritmo aparece no livro VII da obra Os Elementos, de Euclides de Alexandria, escrita por volta de 300 antes de Cristo. Na época, os gregos pensavam os números de forma geométrica, como comprimentos de segmentos, e o método era descrito em termos de medir um segmento com outro repetidamente. A versão original usava subtrações sucessivas, exatamente a ideia de tirar o menor comprimento do maior até sobrar uma medida que coubesse em ambos um número exato de vezes. Essa medida comum corresponde ao que hoje chamamos de máximo divisor comum.

O mais impressionante é a longevidade da ideia. Mais de dois mil anos depois, o algoritmo continua exatamente o mesmo, sem precisar de nenhuma correção, e é estudado em livros de teoria dos números e de ciência da computação no mundo inteiro. Poucas receitas matemáticas atravessaram tanto tempo intactas e ainda úteis. Quando você resolve um exercício de MDC por divisões sucessivas, está repetindo um raciocínio que já era conhecido na Grécia antiga, um pequeno elo com a história da matemática.

Por que ele é tão rápido

Uma pergunta natural é quantas divisões o algoritmo precisa no pior caso. A resposta envolve um fato curioso: as situações que mais exigem etapas são aquelas formadas por números vizinhos da sequência de Fibonacci, em que cada termo é a soma dos dois anteriores. Mesmo nesses casos, o número de divisões cresce de forma muito lenta em relação ao tamanho dos números, o que torna o método extremamente eficiente. Na prática, para números com muitos dígitos, bastam algumas dezenas de divisões, enquanto a fatoração poderia exigir um esforço gigantesco.

Essa eficiência explica por que o algoritmo é tão valorizado em computação. Operações com frações exatas, simplificação de razões e rotinas de criptografia chamam o cálculo do MDC repetidamente, às vezes milhões de vezes por segundo. Um método lento ali deixaria sistemas inteiros pesados. O algoritmo de Euclides resolve cada chamada com pouquíssimas contas, o que o tornou uma peça silenciosa, porém essencial, da tecnologia que usamos todos os dias. É um belo exemplo de como uma ideia simples e bem pensada pode ser, ao mesmo tempo, elegante e profundamente prática.

Resumo

O algoritmo de Euclides encontra o máximo divisor comum de dois números por divisões sucessivas: dividimos o maior pelo menor, depois o divisor pelo resto, e repetimos até o resto ser zero, quando o último divisor usado é o MDC. Ele funciona porque cada divisão preserva o conjunto de divisores comuns, troca o problema por um menor e termina sozinho. A partir do MDC, o MMC sai pela relação com o produto dos números, e o valor 1 indica números primos entre si. Mais rápido que a fatoração para números grandes, simples de fazer à mão e presente da escola à criptografia, ele é um ótimo exemplo de como uma ideia matemática elegante atravessa milênios sem perder a utilidade e ainda surpreende pela simplicidade. Pratique com a calculadora do algoritmo de Euclides e confira seus resultados a cada passo.