thumb|300px|Animação do algoritmo de Euclides para os inteiros 252 e 105. As barras representam múltiplos de 21, o máximo divisor comum (MDC). Em cada passo, o número menor é subtraído ao maior, até um número ser reduzido a zero. O número restante é o MDC.

Na matemática, o algoritmo de Euclides,Alguns livros didáticos amplamente utilizados, como Topics in Algebra de I. N. Herstein e Algebra de Serge Lang, usam o termo "algoritmo de Euclides" para se referir à divisão euclidiana. é 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 (). É 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, é o MDC de e (pois e ), e o mesmo número é também o MDC de e . 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, ). 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 do que o outro. Uma versão mais eficiente do algoritmo atalha estes passos, substituindo o maior dos dois números pelo seu resto quando dividido pelo menor dos dois (com esta versão, o algoritmo para ao chegar a um resto zero). Com esta melhoria, o algoritmo nunca requer mais passos do que cinco vezes o número de dígitos (na base 10) do menor inteiro. Isto foi provado por Gabriel Lamé em 1844 (Teorema de Lamé), e marca o início da teoria da complexidade computacional. Métodos adicionais para melhorar a eficiência do algoritmo foram desenvolvidos no século XX.

O algoritmo de Euclides tem muitas aplicações teóricas e práticas. É usado para reduzir frações à sua forma mais simples e para realizar a divisão na aritmética modular. As computações que utilizam este algoritmo fazem parte dos protocolos criptográficos que são usados para proteger as comunicações na internet, e em métodos para quebrar estes criptossistemas através da fatoração de grandes números compostos. O algoritmo de Euclides pode ser usado para resolver equações diofantinas, tais como encontrar números que satisfazem múltiplas congruências de acordo com o teorema chinês do resto, para construir frações contínuas, e para encontrar aproximações racionais precisas para números reais. Por fim, pode ser usado como uma ferramenta básica para provar teoremas na teoria dos números, tais como o teorema dos quatro quadrados de Lagrange e a unicidade das fatorações em primos.

O algoritmo original foi descrito apenas para números naturais e comprimentos geométricos (números reais), mas o algoritmo foi generalizado no século XIX para outros tipos de números, tais como os inteiros gaussianos e polinômios de uma variável. Isto levou a noções modernas em álgebra abstrata, tais como os domínios euclidianos.

Contexto: máximo divisor comum

O algoritmo de Euclides calcula o máximo divisor comum (MDC) de dois números naturais e . O máximo divisor comum é o maior número natural que divide tanto quanto sem deixar resto. Sinônimos para MDC incluem maior fator comum, maior divisor comum e maior medida comum. O máximo divisor comum é frequentemente escrito como ou, de forma mais simples, como , embora a última notação seja ambígua, sendo também usada para conceitos como um ideal no anel de inteiros, que está intimamente relacionado ao MDC.

Se , então diz-se que e são coprimos (ou primos entre si). Esta propriedade não implica que ou sejam eles próprios números primos. Por exemplo, e fatoram-se como e , de modo que não são primos, mas os seus fatores primos são diferentes, logo e são coprimos, sem outros fatores comuns além de .

thumb|upright|alt="Retângulo alto e estreito dividido em uma grade de quadrados. O retângulo tem dois quadrados de largura e cinco quadrados de altura."|Um retângulo 24×60 é coberto com dez ladrilhos quadrados 12×12, onde 12 é o MDC de 24 e 60. De modo mais geral, um retângulo pode ser coberto com ladrilhos quadrados de lado apenas se for um divisor comum de e .

Seja . Como e são ambos múltiplos de , eles podem ser escritos como e , e não existe um número maior para o qual isso seja verdade. Os números naturais e devem ser coprimos, uma vez que qualquer fator comum poderia ser fatorado de e para tornar maior. Assim, qualquer outro número que divida tanto quanto também deve dividir . O máximo divisor comum de e é o único divisor comum (positivo) de e que é divisível por qualquer outro divisor comum .

O máximo divisor comum pode ser visualizado da seguinte forma. Considere uma área retangular de por , e qualquer divisor comum que divida tanto quanto exatamente. Os lados do retângulo podem ser divididos em segmentos de comprimento , o que divide o retângulo em uma grade de quadrados de lado . O MDC é o maior valor de para o qual isto é possível. Para ilustração, uma área retangular pode ser dividida numa grade de: quadrados , quadrados , quadrados , quadrados , quadrados ou quadrados . Portanto, é o MDC de e . Uma área retangular pode ser dividida em uma grade de quadrados , com dois quadrados ao longo de uma borda () e cinco quadrados ao longo da outra ().

O máximo divisor comum de dois números e é o produto dos fatores primos partilhados pelos dois números, onde cada fator primo pode ser repetido tantas vezes quantas divida tanto quanto . Por exemplo, uma vez que pode ser fatorado em , e pode ser fatorado em , o MDC de e é igual a , o produto dos seus fatores primos partilhados (com o 3 repetido, uma vez que divide ambos). Se dois números não possuem fatores primos em comum, o seu MDC é (obtido aqui como uma instância do produto vazio); em outras palavras, eles são coprimos. Uma vantagem fundamental do algoritmo de Euclides é que ele pode encontrar o MDC de forma eficiente sem a necessidade de calcular os fatores primos. Acredita-se que a fatoração de inteiros grandes seja um problema computacionalmente muito difícil, e a segurança de muitos protocolos criptográficos amplamente utilizados baseia-se na sua inviabilidade.

Outra definição do MDC é útil na matemática avançada, particularmente na teoria dos anéis. O máximo divisor comum de dois números não-nulos e é também a sua menor combinação linear inteira positiva, isto é, o menor número positivo da forma onde e são inteiros. O conjunto de todas as combinações lineares inteiras de e é, na verdade, o mesmo que o conjunto de todos os múltiplos de (, onde é um número inteiro). Na linguagem matemática moderna, o ideal gerado por e é o ideal gerado apenas por  (um ideal gerado por um único elemento é chamado de ideal principal, e todos os ideais dos inteiros são ideais principais). Algumas propriedades do MDC são, de fato, mais fáceis de visualizar com esta descrição, por exemplo, o fato de que qualquer divisor comum de e também divide o MDC (ele divide ambos os termos de ). A equivalência desta definição de MDC com as outras definições é descrita abaixo.

O MDC de três ou mais números é igual ao produto dos fatores primos comuns a todos os números, mas também pode ser calculado obtendo-se repetidamente os MDCs de pares de números. Por exemplo,

Deste modo, o algoritmo de Euclides, que computa o MDC de dois inteiros, é suficiente para calcular o MDC de um número arbitrário de inteiros.

Descrição Procedimento

O algoritmo de Euclides pode ser pensado como a construção de uma sequência de números inteiros não-negativos que começa com os dois inteiros dados e e terminará eventualmente com o número inteiro zero: com O inteiro será então o MDC e podemos afirmar que O algoritmo indica como construir os restos intermediários através da divisão com resto no par precedente encontrando um quociente inteiro de modo que:

Como a sequência de inteiros não-negativos é estritamente decrescente, ela eventualmente deve terminar. Por outras palavras, uma vez que para todo e cada é um inteiro estritamente menor que o precedente não pode haver infinitos inteiros não-negativos menores que zero e, portanto, o algoritmo deve terminar. De facto, o algoritmo terminará sempre no -ésimo passo com igual a zero.

Para ilustrar, suponha que se solicite o MDC de 1071 e 462. A sequência é inicialmente e, a fim de encontrar precisamos de encontrar inteiros e tais que:

Isto dá o quociente uma vez que Isto determina e assim a sequência agora é O próximo passo é continuar a sequência para encontrar , encontrando inteiros e tais que:

Isto dá o quociente uma vez que Isto determina e a sequência agora é O passo seguinte é continuar a sequência para encontrar , encontrando inteiros e tais que:

Isto dá o quociente uma vez que Isto determina e a sequência é concluída como , já que nenhum outro número inteiro não-negativo menor que pode ser encontrado. O penúltimo resto é, portanto, o MDC solicitado:

Podemos generalizar ligeiramente abandonando qualquer requisito de ordenação nos dois valores iniciais e Se o algoritmo pode continuar e encontrar trivialmente que , visto que a sequência de restos será Se então também podemos continuar uma vez que sugerindo que o próximo resto deve ser o próprio , e a sequência é Normalmente, isto seria inválido porque quebra o requisito , mas agora temos por construção, logo o requisito é automaticamente satisfeito e o algoritmo de Euclides pode continuar normalmente. Portanto, abandonar qualquer ordenação entre os dois primeiros inteiros não afeta a conclusão de que a sequência deve eventualmente terminar, porque o próximo resto sempre satisfará e tudo continua como acima. As únicas modificações que precisam de ser feitas são que apenas para e que a subsequência de inteiros não-negativos para é estritamente decrescente, excluindo assim de ambas as afirmações.

Prova de validade A validade do algoritmo de Euclides pode ser provada por um argumento de dois passos. No primeiro passo, mostra-se que o último resto não-nulo divide tanto quanto . Por ser um divisor comum, ele deve ser menor ou igual ao máximo divisor comum . No segundo passo, mostra-se que qualquer divisor comum de e , incluindo , deve dividir ; portanto, deve ser menor ou igual a . Estas duas desigualdades opostas implicam .

Para demonstrar que divide tanto quanto (o primeiro passo), divide o seu predecessor

visto que o resto final é zero. também divide o seu predecessor anterior

porque divide ambos os termos no lado direito da equação. Iterando o mesmo argumento, divide todos os restos precedentes, incluindo e . Nenhum dos restos precedentes , , etc., divide e , uma vez que deixam um resto. Como é um divisor comum de e , .