Algoritmo de Euclides

Na matemática, o algoritmo de Euclides, é um método eficiente para computar o máximo divisor comum (MDC) de dois inteiros, o maior número que divide ambos sem deixar resto. Recebeu o nome do antigo matemático grego Euclides, que o descreveu pela primeira vez nos seus Elementos (c. 300 a.C.). É um exemplo de um algoritmo, e é um dos algoritmos mais antigos em uso comum. Pode ser usado para reduzir frações à sua forma mais simples e faz parte de muitos outros cálculos na teoria dos números e na criptografia. O algoritmo de Euclides baseia-se no princípio de que o máximo divisor comum de dois números não muda se o número maior for substituído pela sua diferença com o número menor. Por exemplo, 21 é o MDC de 252 e 105 (pois 252 = 21 × 12 e 105 = 21 × 5), e o mesmo número 21 é também o MDC de 105 e 252 − 105 = 147. Como esta substituição reduz o maior dos dois números, a repetição deste processo produz pares de números sucessivamente menores até que os dois números se tornem iguais. Quando isso ocorre, esse número é o MDC dos dois números originais. Ao reverter os passos ou utilizar o algoritmo de Euclides estendido, o MDC pode ser expresso como uma combinação linear dos dois números originais, ou seja, a soma dos dois números, cada um multiplicado por um inteiro (por exemplo, 21 = 5 × 105 + (−2) × 252). O facto de o MDC poder sempre ser expresso desta forma é conhecido como a identidade de Bézout. A versão do algoritmo de Euclides descrita acima — que segue a apresentação original de Euclides — pode exigir muitos passos de subtração para encontrar o MDC quando um dos números dados é muito maior...