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. É 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 calcula o máximo divisor comum (MDC) de dois números naturais a e b. O máximo divisor comum g é o maior número natural que divide tanto a quanto b 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 mdc(a, b) ou, de forma mais simples, como (a, b), 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 mdc(a, b) = 1, então diz-se que a e b são coprimos (ou primos entre si). Esta propriedade não implica que a ou b sejam eles próprios números primos. Por exemplo, 6 e 35 fatoram-se como 6 = 2 × 3 e 35 = 5 × 7, de modo que não são primos, mas os seus fatores primos são diferentes, logo 6 e 35 são coprimos, sem outros fatores comuns além de 1. Seja g = mdc(a, b). Como a e b são ambos múltiplos de g, eles podem ser escritos como a = mg e b = ng, e não existe um número maior G > g para o qual isso seja verdade. Os números naturais m e n devem ser coprimos, uma vez que qualquer fator comum poderia ser fatorado de m e n para tornar g maior. Assim, qualquer outro número c que divida tanto a quanto b também deve dividir g. O máximo divisor comum g de a e b é o único divisor comum (positivo) de a e b que é divisível por qualquer outro divisor comum c.
Noutra versão do algoritmo de Euclides, o quociente a cada passo é aumentado em uma unidade se o resto negativo resultante for menor em magnitude do que o resto positivo típico. Anteriormente, a equação assumia que |rk−1| > rk > 0. No entanto, um resto negativo alternativo ek pode ser calculado: Se rk for substituído por ek quando |ek| < |rk|, então obtém-se uma variante do algoritmo de Euclides de tal modo que Leopold Kronecker mostrou que esta versão exige o menor número de passos de qualquer versão do algoritmo de Euclides. Mais genericamente, foi provado que, para quaisquer números de entrada a e b, o número de passos é mínimo se e somente se qk for escolhido de modo que | r k + 1 r k | < 1 φ ∼ 0.618 , {\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,} onde φ {\displaystyle \varphi } é a proporção áurea.
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 r − 2 = a {\displaystyle r_{-2}=a} e r − 1 = b {\displaystyle r_{-1}=b} e terminará eventualmente com o número inteiro zero: { r − 2 = a , r − 1 = b , r 0 , r 1 , ⋯ , r n − 1 , r n = 0 } {\displaystyle \{r_{-2}=a,\ r_{-1}=b,\ r_{0},\ r_{1},\ \cdots ,\ r_{n-1},\ r_{n}=0\}} com r k + 1 < r k . {\displaystyle r_{k+1}<r_{k}.} O inteiro r n − 1 {\displaystyle r_{n-1}} será então o MDC e podemos afirmar que mdc ( a , b ) = r n − 1 . {\displaystyle {\text{mdc}}(a,b)=r_{n-1}.} O algoritmo indica como construir os restos intermediários r k {\displaystyle r_{k}} através da divisão com resto no par precedente ( r k − 2 , r k − 1 ) {\displaystyle (r_{k-2},\ r_{k-1})} encontrando um quociente inteiro q k {\displaystyle q_{k}} de modo que:
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 rN−1 divide tanto a quanto b. Por ser um divisor comum, ele deve ser menor ou igual ao máximo divisor comum g. No segundo passo, mostra-se que qualquer divisor comum de a e b, incluindo g, deve dividir rN−1; portanto, g deve ser menor ou igual a rN−1. Estas duas desigualdades opostas implicam rN−1 = g. Para demonstrar que rN−1 divide tanto a quanto b (o primeiro passo), rN−1 divide o seu predecessor rN−2 visto que o resto final rN é zero. rN−1 também divide o seu predecessor anterior rN−3 porque divide ambos os termos no lado direito da equação. Iterando o mesmo argumento, rN−1 divide todos os restos precedentes, incluindo a e b. Nenhum dos restos precedentes rN−2, rN−3, etc., divide a e b, uma vez que deixam um resto. Como rN−1 é um divisor comum de a e b, rN−1 ≤ g.
Exemplo resolvido
Para ilustração, o algoritmo de Euclides pode ser usado para encontrar o máximo divisor comum de a = 1071 e b = 462. Para começar, subtraem-se múltiplos de 462 de 1071 até que o resto seja menor que 462. Dois desses múltiplos podem ser subtraídos (q0 = 2), deixando um resto de 147: Em seguida, subtraem-se múltiplos de 147 de 462 até que o resto seja menor que 147. Três múltiplos podem ser subtraídos (q1 = 3), deixando um resto de 21: Depois, subtraem-se múltiplos de 21 de 147 até que o resto seja menor que 21. Sete múltiplos podem ser subtraídos (q2 = 7), não deixando resto: Como o último resto é zero, o algoritmo termina com 21 como o máximo divisor comum de 1071 e 462. Isto concorda com o mdc(1071, 462) encontrado pela fatoração em primos acima. Na forma de tabela, os passos são:
Visualização
O algoritmo de Euclides pode ser visualizado em termos da analogia do ladrilhamento apresentada acima para o máximo divisor comum. Assuma que desejamos cobrir exatamente um retângulo a×b com ladrilhos quadrados, onde a é o maior dos dois números. Primeiro, tentamos ladrilhar o retângulo usando ladrilhos quadrados b×b; no entanto, isto deixa um retângulo residual r0×b não ladrilhado, onde r0 < b. Tentamos então ladrilhar o retângulo residual com ladrilhos quadrados r0×r0. Isto deixa um segundo retângulo residual r1×r0, o qual tentamos ladrilhar usando ladrilhos quadrados r1×r1, e assim por diante. A sequência termina quando não houver retângulo residual, isto é, quando os ladrilhos quadrados cobrirem exatamente o retângulo residual anterior. O comprimento dos lados do menor ladrilho quadrado é o MDC das dimensões do retângulo original. Por exemplo, o menor ladrilho quadrado na figura adjacente é de 21×21 (mostrado a vermelho), e 21 é o MDC de 1071 e 462, as dimensões do retângulo original (mostrado a verde).
Divisão euclidiana
A cada passo k, o algoritmo de Euclides computa um quociente qk e um resto rk a partir de dois números rk−1 e rk−2 onde rk é não-negativo e estritamente menor que o valor absoluto de rk−1. O teorema que fundamenta a definição da divisão euclidiana garante que tal quociente e resto sempre existam e sejam únicos. Na versão original do algoritmo de Euclides, o quociente e o resto são encontrados por subtração repetida; ou seja, rk−1 é subtraído de rk−2 repetidamente até que o resto rk seja menor que rk−1. Depois disso, rk e rk−1 são trocados e o processo é iterado. A divisão euclidiana reduz todos os passos entre duas trocas a um único passo, sendo assim mais eficiente. Além disso, os quocientes não são necessários, pelo que se pode substituir a divisão euclidiana pela operação módulo, que fornece apenas o resto. Deste modo, a iteração do algoritmo de Euclides torna-se simplesmente
Implementações
As implementações do algoritmo podem ser expressas em pseudocódigo. Por exemplo, a versão baseada em divisão pode ser programada como No início da k-ésima iteração, a variável b contém o último resto rk−1, ao passo que a variável a contém o seu predecessor, rk−2. O passo b := a mod b é equivalente à fórmula de recursão acima rk ≡ rk−2 mod rk−1. A variável temporária t contém o valor de rk−1 enquanto o próximo resto rk está a ser calculado. No final da iteração do ciclo, a variável b contém o resto rk, ao passo que a variável a contém o seu predecessor, rk−1. (Se forem permitidas entradas negativas, ou se a função mod puder retornar valores negativos, a última linha deverá ser substituída por retorna abs(a).)
O algoritmo de Euclides é um dos algoritmos mais antigos em uso comum. Ele aparece em Os Elementos de Euclides (c. 300 a.C.), especificamente no Livro 7 (Proposições 1–2) e no Livro 10 (Proposições 2–3). No Livro 7, o algoritmo é formulado para inteiros, ao passo que no Livro 10, é formulado para comprimentos de segmentos de reta. (No uso moderno, dir-se-ia que foi formulado aí para números reais. Mas comprimentos, áreas e volumes, representados como números reais no uso moderno, não são medidos nas mesmas unidades e não existe uma unidade natural de comprimento, área ou volume; o conceito de números reais era desconhecido naquela época.) O último algoritmo é geométrico. O MDC de dois comprimentos a e b corresponde ao maior comprimento g que mede a e b uniformemente; por outras palavras, os comprimentos a e b são ambos múltiplos inteiros do comprimento g. O algoritmo provavelmente não foi descoberto por Euclides, que compilou resultados de matemáticos anteriores nos seus Elementos. O matemático e historiador B. L. van der Waerden sugere que o Livro VII deriva de um livro-texto sobre teoria dos números escrito por matemáticos na escola de Pitágoras. O algoritmo já era provavelmente conhecido por Eudoxo de Cnido (cerca de 375 a.C.). O algoritmo pode ser até anterior a Eudoxo, a julgar pelo uso do termo técnico ἀνθυφαίρεσις (anthyphairesis, subtração recíproca) em obras de Euclides e Aristóteles. Claude Brezinski, seguindo as observações de Papo de Alexandria, credita o algoritmo a Teeteto (c. 417 – c. 369 a.C.).
Imagem: Drini · BY-SA · Openverse
Um corpo finito é um conjunto de números com quatro operações generalizadas. As operações são chamadas de adição, subtração, multiplicação e divisão e têm as suas propriedades habituais, tais como comutatividade, associatividade e distributividade. Um exemplo de um corpo finito é o conjunto de 13 números {0, 1, 2, ..., 12} usando a aritmética modular. Neste corpo, os resultados de qualquer operação matemática (adição, subtração, multiplicação ou divisão) são reduzidos em módulo 13; isto é, múltiplos de 13 são adicionados ou subtraídos até que o resultado caia dentro do intervalo 0–12. Por exemplo, o resultado de 5 × 7 = 35 \pmod{13} = 9. Tais corpos finitos podem ser definidos para qualquer primo p; usando definições mais sofisticadas, também podem ser definidos para qualquer potência m de um primo pm. Os corpos finitos são frequentemente chamados de corpos de Galois e são abreviados como GF(p) ou GF(pm).
Identidade de Bézout
A identidade de Bézout afirma que o máximo divisor comum g de dois inteiros a e b pode ser representado como uma soma linear dos dois números originais a e b. Por outras palavras, é sempre possível encontrar inteiros s e t de tal modo que g = sa + tb. Os inteiros s e t podem ser calculados a partir dos quocientes q0, q1, etc., revertendo a ordem das equações no algoritmo de Euclides. Começando pela penúltima equação, g pode ser expresso em termos do quociente qN−1 e dos dois restos precedentes, rN−2 e rN−3: Esses dois restos podem ser igualmente expressos em termos dos seus quocientes e restos precedentes, A substituição destas fórmulas para rN−2 e rN−3 na primeira equação produz g como uma soma linear dos restos rN−4 e rN−5. O processo de substituição de restos por fórmulas envolvendo os seus predecessores pode ser continuado até que os números originais a e b sejam alcançados:
Ideais principais e problemas relacionados
A identidade de Bézout fornece ainda outra definição do máximo divisor comum g de dois números a e b. Considere o conjunto de todos os números ua + vb, onde u e v são dois inteiros quaisquer. Visto que a e b são ambos divisíveis por g, todos os números no conjunto são divisíveis por g. Por outras palavras, cada número do conjunto é um múltiplo inteiro de g. Isto é verdade para qualquer divisor comum de a e b. No entanto, ao contrário de outros divisores comuns, o máximo divisor comum é um membro do conjunto; pela identidade de Bézout, a escolha u = s e v = t fornece g. Um divisor comum menor não pode ser membro do conjunto, uma vez que todo membro do conjunto deve ser divisível por g. Inversamente, qualquer múltiplo m de g pode ser obtido escolhendo u = ms e v = mt, onde s e t são os inteiros da identidade de Bézout. Isto pode ser visto multiplicando a identidade de Bézout por m,
Algoritmo de Euclides estendido
Os inteiros s e t da identidade de Bézout podem ser computados de forma eficiente usando o algoritmo de Euclides estendido. Esta extensão adiciona duas equações recursivas ao algoritmo de Euclides Usando esta recursão, os inteiros de Bézout s e t são dados por s = sN e t = tN, onde N + 1 é o passo no qual o algoritmo termina com rN+1 = 0. A validade desta abordagem pode ser demonstrada por indução. Assuma que a fórmula de recursão está correta até ao passo k − 1 do algoritmo; ou seja, assuma que para todo j menor que k. O k-ésimo passo do algoritmo fornece a equação Uma vez que se assumiu que a fórmula de recursão está correta para rk−2 e rk−1, eles podem ser expressos em termos das correspondentes variáveis s e t
Método matricial
Os inteiros s e t também podem ser encontrados usando um método de matrizes equivalente. A sequência de equações do algoritmo de Euclides pode ser escrita como um produto de matrizes quociente 2×2 multiplicando um vetor bidimensional de restos Seja M representativo do produto de todas as matrizes quociente Isto simplifica o algoritmo de Euclides para a forma Para expressar g como uma soma linear de a e b, ambos os lados desta equação podem ser multiplicados pela inversa da matriz M. O determinante de M é igual a (−1)N+1, já que é igual ao produto dos determinantes das matrizes quociente, cada um dos quais é menos um. Visto que o determinante de M nunca é zero, o vetor dos restos finais pode ser resolvido usando a inversa de M
Lema de Euclides e fatoração única
A identidade de Bézout é essencial para muitas aplicações do algoritmo de Euclides, tal como demonstrar a fatoração única de números em fatores primos. Para ilustrar isto, suponha que um número L pode ser escrito como um produto de dois fatores u e v, ou seja, L = uv. Se outro número w também divide L mas é coprimo de u, então w deve dividir v, pelo seguinte argumento: Se o máximo divisor comum de u e w é 1, então inteiros s e t podem ser encontrados de modo a que pela identidade de Bézout. Multiplicar ambos os lados por v fornece a relação: Uma vez que w divide ambos os termos do lado direito, ele também deve dividir o lado esquerdo, v. Este resultado é conhecido como o lema de Euclides. Especificamente, se um número primo divide L, então ele deve dividir pelo menos um fator de L. Inversamente, se um número w é coprimo de cada um de uma série de números a1, a2, ..., an, então w é também coprimo do seu produto, a1 × a2 × ... × an.
Equações diofantinas lineares
As equações diofantinas são equações nas quais as soluções estão restritas a inteiros; receberam o nome do matemático alexandrino do século III Diofanto. Uma equação diofantina linear típica procura inteiros x e y de tal modo que onde a, b e c são inteiros dados. Isto pode ser escrito como uma equação para x na aritmética modular: Seja g o máximo divisor comum de a e b. Ambos os termos em ax + by são divisíveis por g; portanto, c também deve ser divisível por g, ou a equação não terá soluções. Ao dividir ambos os lados por c/g, a equação pode ser reduzida à identidade de Bézout onde s e t podem ser encontrados pelo algoritmo de Euclides estendido. Isto fornece uma solução para a equação diofantina, x1 = s (c/g) e y1 = t (c/g).
A eficiência computacional do algoritmo de Euclides foi estudada minuciosamente. Esta eficiência pode ser descrita pelo número de passos de divisão que o algoritmo requer, multiplicado pelo custo computacional de cada passo. A primeira análise conhecida do algoritmo de Euclides é devida a A. A. L. Reynaud em 1811, que mostrou que o número de passos de divisão na entrada (u, v) é limitado por v; mais tarde, ele melhorou isto para v/2 + 2. Posteriormente, em 1841, P. J. E. Finck mostrou que o número de passos de divisão é no máximo 2 log2 v + 1, e logo o algoritmo de Euclides é executado em tempo polinomial no tamanho da entrada. Émile Léger, em 1837, estudou o pior caso, que é quando as entradas são números de Fibonacci consecutivos. A análise de Finck foi refinada por Gabriel Lamé em 1844, que mostrou que o número de passos necessários para a conclusão nunca é mais do que cinco vezes o número h de dígitos na base 10 do número menor b.
Número de passos
O número de passos para calcular o MDC de dois números naturais, a e b, pode ser denotado por T(a, b). Se g for o MDC de a e b, então a = mg e b = ng para dois números coprimos m e n. Então como pode ser visto dividindo todos os passos no algoritmo de Euclides por g. Pelo mesmo argumento, o número de passos permanece o mesmo se a e b forem multiplicados por um fator comum w: T(a, b) = T(wa, wb). Portanto, o número de passos T pode variar dramaticamente entre pares vizinhos de números, tais como T(a, b) e T(a, b + 1), dependendo do tamanho dos dois MDCs. A natureza recursiva do algoritmo de Euclides fornece outra equação Se o algoritmo de Euclides requerer N passos para um par de números naturais a > b > 0, os menores valores de a e b para os quais isto é verdade são os números de Fibonacci FN+2 e FN+1, respetivamente. Mais precisamente, se o algoritmo de Euclides requer N passos para o par a > b, então tem-se a ≥ FN+2 e b ≥ FN+1. Isto pode ser demonstrado por indução. Se N = 1, b divide a sem resto; os menores números naturais para os quais isto é verdade são b = 1 e a = 2, que são F2 e F3, respetivamente. Agora assuma que o resultado é válido para todos os valores de N até M − 1. O primeiro passo do algoritmo de M passos é a = q0b + r0, e o algoritmo de Euclides requer M − 1 passos para o par b > r0. Por hipótese de indução, tem-se b ≥ FM+1 e r0 ≥ FM. Portanto, a = q0b + r0 ≥ b + r0 ≥ FM+1 + FM = FM+2, que é a desigualdade pretendida. Esta prova, publicada por Gabriel Lamé em 1844, representa o início da teoria da complexidade computacional, e também a primeira aplicação prática dos números de Fibonacci.
Custo computacional por passo
Em cada passo k do algoritmo de Euclides, o quociente qk e o resto rk são computados para um dado par de inteiros rk−2 e rk−1 O custo computacional por passo está associado principalmente em encontrar qk, uma vez que o resto rk pode ser calculado rapidamente a partir de rk−2, rk−1, e qk O custo computacional de dividir números de h-bits escala como O(h(ℓ + 1)), onde ℓ é o comprimento do quociente. Para efeito de comparação, o algoritmo original de Euclides baseado em subtração pode ser muito mais lento. Uma única divisão inteira é equivalente ao número q de subtrações do quociente. Se a razão entre a e b for muito grande, o quociente é grande e muitas subtrações serão necessárias. Por outro lado, foi mostrado que é muito provável que os quocientes sejam inteiros pequenos. A probabilidade de um dado quociente q é de aproximadamente ln |u/(u − 1)| onde u = (q + 1)2. Para ilustração, a probabilidade de um quociente de 1, 2, 3 ou 4 é de sensivelmente 41,5%, 17,0%, 9,3% e 5,9%, respetivamente. Visto que a operação de subtração é mais rápida que a divisão, particularmente para números grandes, o algoritmo de Euclides baseado em subtração é competitivo com a versão baseada em divisão. Isto é explorado na versão binária do algoritmo de Euclides.
Métodos alternativos
O algoritmo de Euclides é amplamente utilizado na prática, especialmente para números pequenos, devido à sua simplicidade. Para comparação, a eficiência de alternativas ao algoritmo de Euclides pode ser determinada. Uma abordagem ineficiente para encontrar o MDC de dois números naturais a e b é calcular todos os seus divisores comuns; o MDC é então o maior divisor comum. Os divisores comuns podem ser encontrados dividindo ambos os números por inteiros sucessivos de 2 até ao número menor b. O número de passos desta abordagem cresce linearmente com b, ou exponencialmente com o número de dígitos. Outra abordagem ineficiente é encontrar os fatores primos de um ou de ambos os números. Como notado acima, o MDC é igual ao produto dos fatores primos partilhados pelos dois números a e b. Os métodos atuais de fatoração em primos também são ineficientes; muitos sistemas modernos de criptografia baseiam-se mesmo nessa ineficiência.
Embora o algoritmo de Euclides seja usado para encontrar o máximo divisor comum de dois números naturais (inteiros positivos), ele pode ser generalizado para os números reais e para outros objetos matemáticos, tais como polinômios, inteiros quadráticos e quatérnios de Hurwitz. Nestes últimos casos, o algoritmo de Euclides é usado para demonstrar a propriedade crucial da fatoração única, ou seja, que tais números podem ser fatorados de forma única em elementos irredutíveis, os análogos dos números primos. A fatoração única é essencial para muitas provas da teoria dos números.
Números racionais e reais
O algoritmo de Euclides pode ser aplicado a números reais, como descrito por Euclides no Livro 10 dos seus Elementos. O objetivo do algoritmo é identificar um número real g tal que dois números reais dados, a e b, sejam múltiplos inteiros dele: a = mg e b = ng, onde m e n são inteiros. Esta identificação é equivalente a encontrar uma relação inteira entre os números reais a e b; isto é, determina inteiros s e t de tal modo que sa + tb = 0. Se tal equação for possível, a e b são chamados de comprimentos comensuráveis, caso contrário, são comprimentos incomensuráveis. O algoritmo de Euclides para números reais difere do seu homólogo inteiro em dois aspetos. Primeiro, os restos rk são números reais, embora os quocientes qk sejam inteiros como antes. Segundo, não é garantido que o algoritmo termine num número finito N de passos. Se terminar, a fração a/b é um número racional, isto é, a razão de dois inteiros
Polinômios
Polinômios numa única variável x podem ser adicionados, multiplicados e fatorados em polinômios irredutíveis, que são os análogos dos números primos para os inteiros. O polinômio máximo divisor comum g(x) de dois polinômios a(x) e b(x) é definido como o produto dos seus polinômios irredutíveis partilhados, o qual pode ser identificado usando o algoritmo de Euclides. O procedimento básico é semelhante ao dos inteiros. A cada passo k, um polinômio quociente qk(x) e um polinômio resto rk(x) são identificados para satisfazer a equação recursiva onde r−2(x) = a(x) e r−1(x) = b(x). Cada polinômio quociente é escolhido de tal forma que cada resto é zero ou possui um grau que é menor do que o grau do seu predecessor: grau[rk(x)] < grau[rk−1(x)]. Como o grau é um inteiro não-negativo, e visto que diminui a cada passo, o algoritmo de Euclides conclui num número finito de passos. O último resto não-nulo é o máximo divisor comum dos dois polinômios originais, a(x) e b(x).
Inteiros gaussianos
Os inteiros gaussianos são números complexos da forma α = u + vi, onde u e v são inteiros ordinários[nota 2] e i é a raiz quadrada de menos um. Ao definir um análogo do algoritmo de Euclides, pode-se demonstrar que os inteiros gaussianos são unicamente fatoráveis, pelo argumento acima. Esta fatoração única é útil em muitas aplicações, tais como na derivação de todos os ternos pitagóricos ou na prova do teorema dos dois quadrados de Fermat. Geralmente, o algoritmo de Euclides é conveniente em tais aplicações, mas não essencial; por exemplo, os teoremas podem ser frequentemente provados por outros argumentos. O algoritmo de Euclides desenvolvido para dois inteiros gaussianos α e β é praticamente o mesmo que para os inteiros ordinários, mas difere em dois aspetos. Como antes, definimos r−2 = α e r−1 = β, e a tarefa a cada passo k é identificar um quociente qk e um resto rk de tal modo que
Domínios euclidianos
Um conjunto de elementos sob duas operações binárias, denotadas como adição e multiplicação, é chamado de domínio euclidiano se formar um anel comutativo R e, grosso modo, se um algoritmo de Euclides generalizado puder ser realizado sobre eles. As duas operações de um tal anel não precisam de ser a adição e a multiplicação da aritmética ordinária; em vez disso, podem ser mais gerais, como as operações de um grupo matemático ou de um monoide. Ainda assim, estas operações gerais devem respeitar muitas das leis que governam a aritmética ordinária, tais como a comutatividade, a associatividade e a distributividade. O algoritmo de Euclides generalizado requer uma função euclidiana, isto é, um mapeamento f de R no conjunto dos inteiros não-negativos tal que, para quaisquer dois elementos não-nulos a e b em R, existam q e r em R de tal modo que a = qb + r e f(r) < f(b). Exemplos de tais mapeamentos são o valor absoluto para os inteiros, o grau para polinômios univariados (de uma variável) e a norma para os inteiros gaussianos acima. O princípio básico é que cada passo do algoritmo reduz f inexoravelmente; consequentemente, se f pode ser reduzida apenas um número finito de vezes, o algoritmo deve parar num número finito de passos. Este princípio baseia-se na propriedade da boa ordenação dos inteiros não-negativos, que assevera que todo conjunto não vazio de inteiros não-negativos tem um menor membro.
Anéis não comutativos
O algoritmo de Euclides pode ser aplicado a alguns anéis não comutativos, tais como o conjunto de quatérnios de Hurwitz. Sejam α e β representantes de dois elementos de um tal anel. Eles possuem um divisor comum à direita δ se α = ξδ e β = ηδ para alguma escolha de ξ e η no anel. Similarmente, eles possuem um divisor comum à esquerda se α = dξ e β = dη para alguma escolha de ξ e η no anel. Visto que a multiplicação não é comutativa, existem duas versões do algoritmo de Euclides, uma para divisores à direita e outra para divisores à esquerda. Escolhendo os divisores à direita, o primeiro passo para encontrar o mdc(α, β) pelo algoritmo de Euclides pode ser escrito
