Algoritmo de Euclides (MDC)

É um método antigo e eficiente para encontrar o máximo divisor comum (MDC) de dois números usando divisões sucessivas. Em vez de listar todos os divisores ou fatorar em primos, dividimos o maior pelo menor, depois o divisor pelo resto, e repetimos até o resto ser zero. O último divisor usado é o MDC.

Dividimos 48 por 18 e obtemos resto 12. Depois dividimos 18 por 12 e obtemos resto 6. Em seguida dividimos 12 por 6 e o resto dá zero. Como o resto chegou a zero, o último divisor, que foi 6, é o MDC de 48 e 18. A calculadora mostra a tabela completa dessas divisões.

Porque, a cada divisão, todo divisor comum dos dois números também divide o resto. Assim, o conjunto de divisores comuns não muda ao longo das etapas. Quando o resto chega a zero, o divisor daquela última conta divide exatamente o número anterior, e ele é o maior valor que divide os dois números originais.

A fatoração em primos decompõe cada número e multiplica os fatores comuns; é intuitiva, mas fica lenta com números grandes. O algoritmo de Euclides só usa divisões e é muito mais rápido, especialmente para números grandes, porque cada passo reduz bastante o tamanho dos valores. Os dois métodos chegam ao mesmo MDC.

Sim. Depois de achar o MDC, ela calcula o mínimo múltiplo comum pela relação a vezes b igual a MDC vezes MMC. Ou seja, o MMC é o produto dos dois números dividido pelo MDC. Para 48 e 18, o MMC é 48 vezes 18 dividido por 6, que dá 144.

Significa que os dois números são primos entre si, ou coprimos: não têm nenhum divisor comum maior que 1. Por exemplo, 8 e 15 têm MDC 1, mesmo nenhum deles sendo primo isoladamente. Números coprimos aparecem muito ao simplificar frações, pois uma fração irredutível tem numerador e denominador coprimos.