O algoritmo de Euclides acha o máximo divisor comum (MDC) de dois números por divisões sucessivas, sem fatorar. Para 462/1071 bastam três divisões: o MDC é 21 e a fração fica em 22/51. Para obter só o resultado, a calculadora de máximo divisor comum mostra o resultado na hora; este guia explica o método à mão e por que ele sempre termina no MDC.
A ideia cabe numa frase: o MDC de dois números não muda se o maior for trocado pelo resto da divisão dele pelo menor. Repete-se até o resto ser 0, e o último divisor usado é o MDC.
Cada linha satisfaz dividendo = quociente × divisor + resto, com o resto menor que o divisor. À linha seguinte só se leva o divisor e o resto, não o quociente. A multiplicação cruzada da verificação é a mesma que serve para comparar frações, e dividir os dois termos pelo mesmo número é o que distingue simplificar de ampliar, como explicam as frações equivalentes.
Por que o resto basta
Se a = q × b + r, todo número que divide a e b divide também r, porque r = a − q × b. E vice-versa: o que divide b e r divide a. Os pares (a, b) e (b, r) têm, portanto, os mesmos divisores comuns, e o maior deles é o mesmo. Por isso MDC(a, b) = MDC(b, r). Como cada resto é menor que o anterior, a cadeia desce até chegar a 0.
A mesma ideia aparece com quadrados. O retângulo de 1071 por 462 é coberto por dois quadrados de lado 462; na faixa que sobra cabem três de lado 147, e na tira final, sete de lado 21. O menor quadrado que preenche tudo sem falhas mede 21, o MDC.
Exemplo resolvido: simplificar 462/1071
O objetivo é reduzir 462/1071 à fração irredutível, sem nenhum divisor comum à vista.
- Divida o maior pelo menor. 1071 = 2 × 462 + 147.
- Passe ao par divisor e resto. Agora são 462 e 147: 462 = 3 × 147 + 21.
- Repita com o novo par. São 147 e 21: 147 = 7 × 21 + 0. O resto é 0, então a cadeia termina.
- Tome o último divisor. O MDC é 21.
- Divida numerador e denominador por 21. 462 ÷ 21 = 22 e 1071 ÷ 21 = 51.
Resultado: 462/1071 = 22/51.
Verificação: por multiplicação cruzada, 462 × 51 = 23.562 e 1071 × 22 = 23.562, então as duas frações valem o mesmo. Além disso, 22 = 2 × 11 e 51 = 3 × 17 não têm fatores em comum.
Segundo exemplo, com cinco divisões
Para 3600/4284, comece pelo número maior, 4284. A cadeia é:
- 4284 = 1 × 3600 + 684
- 3600 = 5 × 684 + 180
- 684 = 3 × 180 + 144
- 180 = 1 × 144 + 36
- 144 = 4 × 36 + 0
O MDC é 36, e 3600 ÷ 36 = 100 com 4284 ÷ 36 = 119, então a fração fica em 100/119. Começando pelo menor, a primeira divisão dá quociente 0 e apenas troca o par; o resultado é o mesmo, com um passo a mais.
Euclides ou fatores primos
Para um MDC há dois caminhos, e cada um vence num terreno diferente.
| Método | O que se faz | Resultado | Quando convém |
|---|---|---|---|
| Euclides | Divide-se com resto até chegar a 0 | 5 divisões, MDC 36 | Números grandes, ou quando só o MDC interessa |
| Fatores primos | Fatora-se e tomam-se os comuns com o menor expoente | 2² × 3² = 36 | Números pequenos, ou quando o MMC também é necessário |
Com 4284 = 2² × 3² × 7 × 17 e 3600 = 2⁴ × 3² × 5², a fatoração exige encontrar todos os primos, e um fator grande alonga a busca. Euclides nunca os procura. Se além do MDC o MMC também é necessário, a decomposição em fatores primos dá-o diretamente, e o guia sobre a diferença entre MDC e MMC explica quando usar cada um. Os critérios de divisibilidade poupam passos quando o divisor comum é evidente.
Um erro que parece um resultado certo
O deslize mais comum é levar adiante o quociente no lugar do resto, e ele produz um MDC que parece razoável.
Outro deslize parecido é parar num resto pequeno sem esperar o 0: o MDC é o último divisor, não o primeiro resto que parece fácil de manejar. E, para simplificar, é preciso dividir os dois termos pelo MDC, não só um, ou o valor muda.
Quando usar e para onde ir depois
Euclides trabalha com dois inteiros de cada vez e devolve apenas o MDC. Para frações pequenas, como 6/8, reconhecer o 2 a olho é mais rápido. Para praticar com qualquer fração, a ferramenta para simplificar frações aplica o MDC e dá a forma irredutível. Para outras formas de escrever uma fração, o guia de frações contínuas e egípcias usa estas mesmas divisões: os quocientes da cadeia são os termos da fração contínua.