Algoritmo de Euclides

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 ${\displaystyle r_{-2}=a}$ e ${\displaystyle r_{-1}=b}$ e terminará eventualmente com o número inteiro zero: ${\displaystyle \{r_{-2}=a,\ r_{-1}=b,\ r_{0},\ r_{1},\ \cdots ,\ r_{n-1},\ r_{n}=0\}}$ com ${\displaystyle r_{k+1}<r_{k}.}$ O inteiro ${\displaystyle r_{n-1}}$ será então o MDC e podemos afirmar que ${\displaystyle {\text{mdc}}(a,b)=r_{n-1}.}$ O algoritmo indica como construir os restos intermediários ${\displaystyle r_{k}}$ através da divisão com resto no par precedente ${\displaystyle (r_{k-2},\ r_{k-1})}$ encontrando um quociente inteiro ${\displaystyle q_{k}}$ de modo que:

${\displaystyle r_{k-2}=q_{k}\cdot r_{k-1}+r_{k}{\text{, com }}\ r_{k-1}>r_{k}\geq 0.}$

Como a sequência de inteiros não-negativos ${\displaystyle \{r_{k}\}}$ é estritamente decrescente, ela eventualmente deve terminar. Por outras palavras, uma vez que ${\displaystyle r_{k}\geq 0}$ para todo ${\displaystyle k,}$ e cada ${\displaystyle r_{k}}$ é um inteiro estritamente menor que o precedente ${\displaystyle r_{k-1},}$ 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 n-ésimo passo com ${\displaystyle r_{n}}$ igual a zero.^[15]

Para ilustrar, suponha que se solicite o MDC de 1071 e 462. A sequência é inicialmente ${\displaystyle \{r_{-2}=1071,\ r_{-1}=462\}}$ e, a fim de encontrar ${\displaystyle r_{0},}$ precisamos de encontrar inteiros ${\displaystyle q_{0}}$ e ${\displaystyle r_{0}<r_{-1}}$ tais que:

${\displaystyle 1071=q_{0}\cdot 462+r_{0}.}$

Isto dá o quociente ${\displaystyle q_{0}=2}$ uma vez que ${\displaystyle 1071=2\cdot 462+147.}$ Isto determina ${\displaystyle r_{0}=147}$ e assim a sequência agora é ${\displaystyle \{1071,\ 462,\ r_{0}=147\}.}$ O próximo passo é continuar a sequência para encontrar ${\displaystyle r_{1}}$, encontrando inteiros ${\displaystyle q_{1}}$ e ${\displaystyle r_{1}<r_{0}}$ tais que:

${\displaystyle 462=q_{1}\cdot 147+r_{1}.}$

Isto dá o quociente ${\displaystyle q_{1}=3}$ uma vez que ${\displaystyle 462=3\cdot 147+21.}$ Isto determina ${\displaystyle r_{1}=21}$ e a sequência agora é ${\displaystyle \{1071,\ 462,\ 147,\ r_{1}=21\}.}$ O passo seguinte é continuar a sequência para encontrar ${\displaystyle r_{2}}$, encontrando inteiros ${\displaystyle q_{2}}$ e ${\displaystyle r_{2}<r_{1}}$ tais que:

${\displaystyle 147=q_{2}\cdot 21+r_{2}.}$

Isto dá o quociente ${\displaystyle q_{2}=7}$ uma vez que ${\displaystyle 147=7\cdot 21+0.}$ Isto determina ${\displaystyle r_{2}=0}$ e a sequência é concluída como ${\displaystyle \{1071,\ 462,\ 147,\ 21,\ r_{2}=0\}}$, já que nenhum outro número inteiro não-negativo menor que ${\displaystyle 0}$ pode ser encontrado. O penúltimo resto ${\displaystyle 21}$ é, portanto, o MDC solicitado:

${\displaystyle {\text{mdc}}(1071,\ 462)=21.}$

Podemos generalizar ligeiramente abandonando qualquer requisito de ordenação nos dois valores iniciais ${\displaystyle a}$ e ${\displaystyle b.}$ Se ${\displaystyle a=b,}$ o algoritmo pode continuar e encontrar trivialmente que ${\displaystyle {\text{mdc}}(a,\ a)=a}$, visto que a sequência de restos será ${\displaystyle \{a,\ a,\ 0\}.}$ Se ${\displaystyle a<b,}$ então também podemos continuar uma vez que ${\displaystyle a\equiv 0\cdot b+a,}$ sugerindo que o próximo resto deve ser o próprio ${\displaystyle a}$, e a sequência é ${\displaystyle \{a,\ b,\ a,\ \cdots \}.}$ Normalmente, isto seria inválido porque quebra o requisito ${\displaystyle r_{0}<r_{-1}}$, mas agora temos ${\displaystyle a<b}$ 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á ${\displaystyle r_{0}<b}$ e tudo continua como acima. As únicas modificações que precisam de ser feitas são que ${\displaystyle r_{k}<r_{k-1}}$ apenas para ${\displaystyle k\geq 0,}$ e que a subsequência de inteiros não-negativos ${\displaystyle \{r_{k-1}\}}$ para ${\displaystyle k\geq 0}$ é estritamente decrescente, excluindo assim ${\displaystyle a=r_{-2}}$ de ambas as afirmações.

A validade do algoritmo de Euclides pode ser provada por um argumento de dois passos.^[16] No primeiro passo, mostra-se que o último resto não-nulo r_N−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 r_N−1; portanto, g deve ser menor ou igual a r_N−1. Estas duas desigualdades opostas implicam r_N−1 = g.

Para demonstrar que r_N−1 divide tanto a quanto b (o primeiro passo), r_N−1 divide o seu predecessor r_N−2

r_N−2 = q_N r_N−1

visto que o resto final r_N é zero. r_N−1 também divide o seu predecessor anterior r_N−3

r_N−3 = q_N−1 r_N−2 + r_N−1

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

No segundo passo, qualquer número natural c que divida tanto a quanto b (por outras palavras, qualquer divisor comum de a e b) divide os restos r_k. Por definição, a e b podem ser escritos como múltiplos de c: a = mc e b = nc, onde m e n são números naturais. Portanto, c divide o resto inicial r₀, uma vez que r₀ = a − q₀b = mc − q₀nc = (m − q₀n)c. Um argumento análogo mostra que c também divide os restos subsequentes r₁, r₂, etc. Portanto, o máximo divisor comum g deve dividir r_N−1, o que implica que g ≤ r_N−1. Como a primeira parte do argumento mostrou o inverso (r_N−1 ≤ g), conclui-se que g = r_N−1. Assim, g é o máximo divisor comum de todos os pares sucessivos:^[17][18]

${\displaystyle g={\text{mdc}}(a,b)={\text{mdc}}(a,r_{0})={\text{mdc}}(r_{0},r_{1})=\dots ={\text{mdc}}(r_{k-1},r_{k})=\dots ={\text{mdc}}(r_{N-2},r_{N-1})={\text{mdc}}(r_{N-1},0)=r_{N-1}}$

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 (q₀ = 2), deixando um resto de 147:

1071 = 2 × 462 + 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 (q₁ = 3), deixando um resto de 21:

462 = 3 × 147 + 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 (q₂ = 7), não deixando resto:

147 = 7 × 21 + 0.

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:

O algoritmo de Euclides pode ser visualizado em termos da analogia do ladrilhamento apresentada acima para o máximo divisor comum.^[19] 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 r₀×b não ladrilhado, onde r₀ < b. Tentamos então ladrilhar o retângulo residual com ladrilhos quadrados r₀×r₀. Isto deixa um segundo retângulo residual r₁×r₀, o qual tentamos ladrilhar usando ladrilhos quadrados r₁×r₁, 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).

A cada passo k, o algoritmo de Euclides computa um quociente q_k e um resto r_k a partir de dois números r_k−1 e r_k−2

r_k−2 = q_k r_k−1 + r_k,

onde r_k é não-negativo e estritamente menor que o valor absoluto de r_k−1. O teorema que fundamenta a definição da divisão euclidiana garante que tal quociente e resto sempre existam e sejam únicos.^[20]

Na versão original do algoritmo de Euclides, o quociente e o resto são encontrados por subtração repetida; ou seja, r_k−1 é subtraído de r_k−2 repetidamente até que o resto r_k seja menor que r_k−1. Depois disso, r_k e r_k−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

r_k = r_k−2 mod r_k−1.

As implementações do algoritmo podem ser expressas em pseudocódigo. Por exemplo, a versão baseada em divisão pode ser programada como^[21]

função mdc(a, b)
    enquanto b ≠ 0
        t := b
        b := a mod b
        a := t
    retorna a

No início da k-ésima iteração, a variável b contém o último resto r_k−1, ao passo que a variável a contém o seu predecessor, r_k−2. O passo b := a mod b é equivalente à fórmula de recursão acima r_k ≡ r_k−2 mod r_k−1. A variável temporária t contém o valor de r_k−1 enquanto o próximo resto r_k está a ser calculado. No final da iteração do ciclo, a variável b contém o resto r_k, ao passo que a variável a contém o seu predecessor, r_k−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).)

Na versão baseada em subtração, que foi a versão original de Euclides, o cálculo do resto (b := a mod b) é substituído por uma subtração repetida.^[22] Ao contrário da versão baseada na divisão, que trabalha com inteiros arbitrários como entrada, a versão baseada na subtração pressupõe que a entrada consista em inteiros positivos e para quando a = b:

função mdc(a, b)
    enquanto a ≠ b 
        se a > b
            a := a − b
        senão
            b := b − a
    retorna a

As variáveis a e b alternam contendo os restos anteriores r_k−1 e r_k−2. Assuma que a é maior que b no início de uma iteração; então a é igual a r_k−2, uma vez que r_k−2 > r_k−1. Durante a iteração do ciclo, a é reduzido por múltiplos do resto anterior b até que a seja menor que b. Então a é o próximo resto r_k. De seguida, b é reduzido por múltiplos de a até ser novamente menor que a, resultando no próximo resto r_k+1, e assim por diante.

A versão recursiva^[23] baseia-se na igualdade dos MDCs de restos sucessivos e na condição de paragem mdc(r_N−1, 0) = r_N−1.

função mdc(a, b)
    se b = 0
        retorna a
    senão
        retorna mdc(b, a mod b)

(Como acima, se forem permitidas entradas negativas, ou se a função mod puder retornar valores negativos, a instrução retorna a deverá ser substituída por retorna max(a, −a).)

Para ilustração, o mdc(1071, 462) é calculado a partir do equivalente mdc(462, 1071 mod 462) = mdc(462, 147). Este último MDC é calculado a partir do mdc(147, 462 mod 147) = mdc(147, 21), que por sua vez é calculado a partir do mdc(21, 147 mod 21) = mdc(21, 0) = 21.

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.^[24][25] Anteriormente, a equação

r_k−2 = q_k r_k−1 + r_k

assumia que |r_k−1| > r_k > 0. No entanto, um resto negativo alternativo e_k pode ser calculado:

r_k−2 = (q_k + 1) r_k−1 + e_k

se r_k−1 > 0 ou

r_k−2 = (q_k – 1) r_k−1 + e_k

se r_k−1 < 0.

Se r_k for substituído por e_k quando |e_k| < |r_k|, então obtém-se uma variante do algoritmo de Euclides de tal modo que

|r_k| ≤ |r_k−1| / 2

a cada passo.

Leopold Kronecker mostrou que esta versão exige o menor número de passos de qualquer versão do algoritmo de Euclides.^[24][25] 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 q_k for escolhido de modo que ${\displaystyle \left|{\frac {r_{k+1}}{r_{k}}}\right|<{\frac {1}{\varphi }}\sim 0.618,}$ onde ${\displaystyle \varphi }$ é a proporção áurea.^[26]

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.^[56] Por outras palavras, é sempre possível encontrar inteiros s e t de tal modo que g = sa + tb.^[57][58]

Os inteiros s e t podem ser calculados a partir dos quocientes q₀, q₁, etc., revertendo a ordem das equações no algoritmo de Euclides.^[59] Começando pela penúltima equação, g pode ser expresso em termos do quociente q_N−1 e dos dois restos precedentes, r_N−2 e r_N−3:

g = r_N−1 = r_N−3 − q_N−1 r_N−2.

Esses dois restos podem ser igualmente expressos em termos dos seus quocientes e restos precedentes,

r_N−2 = r_N−4 − q_N−2 r_N−3 e

r_N−3 = r_N−5 − q_N−3 r_N−4.

A substituição destas fórmulas para r_N−2 e r_N−3 na primeira equação produz g como uma soma linear dos restos r_N−4 e r_N−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:

r₂ = r₀ − q₂ r₁

r₁ = b − q₁ r₀

r₀ = a − q₀ b.

Após todos os restos r₀, r₁, etc. terem sido substituídos, a equação final expressa g como uma soma linear de a e b, de modo que g = sa + tb.

O algoritmo de Euclides, e logo a identidade de Bézout, pode ser generalizado para o contexto de domínios euclidianos.

A identidade de Bézout fornece ainda outra definição do máximo divisor comum g de dois números a e b.^[12] 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,

mg = msa + mtb.

Portanto, o conjunto de todos os números ua + vb é equivalente ao conjunto de múltiplos m de g. Noutras palavras, o conjunto de todas as possíveis somas de múltiplos inteiros de dois números (a e b) é equivalente ao conjunto de múltiplos de mdc(a, b). Diz-se que o MDC é o gerador do ideal de a e b. Esta definição de MDC levou aos conceitos modernos em álgebra abstrata de um ideal principal (um ideal gerado por um único elemento) e de um domínio de ideais principais (um domínio no qual todo ideal é um ideal principal).

Certos problemas podem ser resolvidos usando este resultado.^[60] Por exemplo, considere dois copos de medição de volume a e b. Ao adicionar/subtrair u múltiplos do primeiro copo e v múltiplos do segundo copo, qualquer volume ua + vb pode ser medido. Estes volumes são todos múltiplos de g = mdc(a, b).

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^[61]

s_k = s_k−2 − q_ks_k−1

t_k = t_k−2 − q_kt_k−1

com os valores iniciais

s₋₂ = 1, t₋₂ = 0

s₋₁ = 0, t₋₁ = 1.

Usando esta recursão, os inteiros de Bézout s e t são dados por s = s_N e t = t_N, onde N + 1 é o passo no qual o algoritmo termina com r_N+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

r_j = s_j a + t_j b

para todo j menor que k. O k-ésimo passo do algoritmo fornece a equação

r_k = r_k−2 − q_kr_k−1.

Uma vez que se assumiu que a fórmula de recursão está correta para r_k−2 e r_k−1, eles podem ser expressos em termos das correspondentes variáveis s e t

r_k = (s_k−2 a + t_k−2 b) − q_k(s_k−1 a + t_k−1 b).

Reorganizar esta equação produz a fórmula de recursão para o passo k, como pretendido

r_k = s_k a + t_k b = (s_k−2 − q_ks_k−1) a + (t_k−2 − q_kt_k−1) b.

Os inteiros s e t também podem ser encontrados usando um método de matrizes equivalente.^[62] A sequência de equações do algoritmo de Euclides

${\displaystyle {\begin{aligned}a&=q_{0}b+r_{0}\\b&=q_{1}r_{0}+r_{1}\\&\,\,\,\vdots \\r_{N-2}&=q_{N}r_{N-1}+0\end{aligned}}}$

pode ser escrita como um produto de matrizes quociente 2×2 multiplicando um vetor bidimensional de restos

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}b\\r_{0}\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{0}\\r_{1}\end{pmatrix}}=\cdots =\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}{\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}\,.}$

Seja M representativo do produto de todas as matrizes quociente

${\displaystyle \mathbf {M} ={\begin{pmatrix}m_{11}&m_{12}\\m_{21}&m_{22}\end{pmatrix}}=\prod _{i=0}^{N}{\begin{pmatrix}q_{i}&1\\1&0\end{pmatrix}}={\begin{pmatrix}q_{0}&1\\1&0\end{pmatrix}}{\begin{pmatrix}q_{1}&1\\1&0\end{pmatrix}}\cdots {\begin{pmatrix}q_{N}&1\\1&0\end{pmatrix}}\,.}$

Isto simplifica o algoritmo de Euclides para a forma

${\displaystyle {\begin{pmatrix}a\\b\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}r_{N-1}\\0\end{pmatrix}}=\mathbf {M} {\begin{pmatrix}g\\0\end{pmatrix}}\,.}$

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.^[62][63] 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

${\displaystyle {\begin{pmatrix}g\\0\end{pmatrix}}=\mathbf {M} ^{-1}{\begin{pmatrix}a\\b\end{pmatrix}}=(-1)^{N+1}{\begin{pmatrix}m_{22}&-m_{12}\\-m_{21}&m_{11}\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}\,.}$

Visto que a equação superior fornece

g = (−1)^N+1 ( m₂₂ a − m₁₂ b),

os dois inteiros da identidade de Bézout são s = (−1)^N+1m₂₂ e t = (−1)^Nm₁₂. O método matricial é tão eficiente quanto a recursão equivalente, com duas multiplicações e duas adições por passo do algoritmo de Euclides.

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.^[64] 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

1 = su + tw

pela identidade de Bézout. Multiplicar ambos os lados por v fornece a relação:

v = suv + twv = sL + twv

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.^[65] 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 a₁, a₂, ..., a_n, então w é também coprimo do seu produto, a₁ × a₂ × ... × a_n.^[65]

O lema de Euclides é suficiente para provar que todo número possui uma fatoração única em números primos.^[66] Para ver isto, assuma o contrário, que existem duas fatorações independentes de L em m e n fatores primos, respetivamente

L = p₁p₂...p_m = q₁q₂...q_n.

Como cada primo p divide L por hipótese, ele também deve dividir um dos fatores q; uma vez que cada q é também primo, deve verificar-se que p = q. Dividir iterativamente pelos fatores p mostra que cada p tem um correspondente igual q; as duas fatorações em primos são idênticas exceto pela sua ordem. A fatoração única de números em primos tem muitas aplicações em provas matemáticas, como mostrado abaixo.

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.^[67] Uma equação diofantina linear típica procura inteiros x e y de tal modo que^[68]

ax + by = c

onde a, b e c são inteiros dados. Isto pode ser escrito como uma equação para x na aritmética modular:

ax ≡ c \pmod b.

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

sa + tb = g,

onde s e t podem ser encontrados pelo algoritmo de Euclides estendido.^[69] Isto fornece uma solução para a equação diofantina, x₁ = s (c/g) e y₁ = t (c/g).

Em geral, uma equação diofantina linear não tem soluções, ou tem um número infinito de soluções.^[70] Para encontrar o último caso, considere duas soluções, (x₁, y₁) e (x₂, y₂), onde

ax₁ + by₁ = c = ax₂ + by₂

ou equivalentemente

a(x₁ − x₂) = b(y₂ − y₁).

Portanto, a menor diferença entre duas soluções de x é b/g, ao passo que a menor diferença entre duas soluções de y é a/g. Assim, as soluções podem ser expressas como

x = x₁ − bu/g

y = y₁ + au/g.

Ao permitir que u varie sobre todos os inteiros possíveis, uma família infinita de soluções pode ser gerada a partir de uma única solução (x₁, y₁). Se as soluções forem obrigadas a ser inteiros positivos (x > 0, y > 0), apenas um número finito de soluções poderá ser possível. Esta restrição sobre as soluções aceitáveis permite que alguns sistemas de equações diofantinas com mais incógnitas do que equações tenham um número finito de soluções;^[71] isto é impossível para um sistema de equações lineares quando as soluções podem ser qualquer número real (ver sistema subdeterminado).

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 p^m. Os corpos finitos são frequentemente chamados de corpos de Galois e são abreviados como GF(p) ou GF(p^m).

Num tal corpo com m números, cada elemento não-nulo a tem um único inverso multiplicativo modular, a⁻¹, tal que aa⁻¹ = a⁻¹a ≡ 1 \pmod m. Este inverso pode ser encontrado resolvendo a equação de congruência ax ≡ 1 \pmod m,^[72] ou a equação diofantina linear equivalente^[73]

ax + my = 1.

Esta equação pode ser resolvida pelo algoritmo de Euclides, como descrito acima. Encontrar inversos multiplicativos é um passo essencial no algoritmo RSA, que é amplamente utilizado no comércio eletrônico; especificamente, a equação determina o inteiro usado para descriptografar a mensagem.^[74] Embora o algoritmo RSA use anéis em vez de corpos, o algoritmo de Euclides ainda pode ser usado para encontrar um inverso multiplicativo quando este existir. O algoritmo de Euclides também tem outras aplicações em códigos de correção de erros; por exemplo, pode ser usado como uma alternativa ao algoritmo de Berlekamp-Massey para decodificar códigos BCH e Reed-Solomon, que se baseiam em corpos de Galois.^[75]

O algoritmo de Euclides também pode ser usado para resolver múltiplas equações diofantinas lineares.^[76] Tais equações surgem no teorema chinês do resto, que descreve um método inovador para representar um número inteiro x. Em vez de representar um inteiro pelos seus algarismos, ele pode ser representado pelos seus restos x_i módulo um conjunto de N números coprimos m_i:^[77]

${\displaystyle {\begin{aligned}x_{1}&\equiv x{\pmod {m_{1}}}\\x_{2}&\equiv x{\pmod {m_{2}}}\\&\,\,\,\vdots \\x_{N}&\equiv x{\pmod {m_{N}}}\,.\end{aligned}}}$

O objetivo é determinar x a partir dos seus N restos x_i. A solução é combinar as múltiplas equações numa única equação diofantina linear com um módulo M muito maior que é o produto de todos os módulos individuais m_i, e definir M_i como

${\displaystyle M_{i}={\frac {M}{m_{i}}}.}$

Assim, cada M_i é o produto de todos os módulos exceto m_i. A solução depende de encontrar N novos números h_i tais que

${\displaystyle M_{i}h_{i}\equiv 1{\pmod {m_{i}}}\,.}$

Com estes números h_i, qualquer inteiro x pode ser reconstruído a partir dos seus restos x_i pela equação

${\displaystyle x\equiv (x_{1}M_{1}h_{1}+x_{2}M_{2}h_{2}+\cdots +x_{N}M_{N}h_{N}){\pmod {M}}\,.}$

Uma vez que estes números h_i são os inversos multiplicativos dos M_i, eles podem ser encontrados usando o algoritmo de Euclides, como descrito na subseção anterior.

O algoritmo de Euclides pode ser usado para organizar o conjunto de todos os números racionais positivos numa árvore de busca binária infinita, chamada de árvore de Stern-Brocot. O número 1 (expresso como a fração 1/1) é colocado na raiz da árvore, e a localização de qualquer outro número a/b pode ser encontrada computando mdc(a,b) utilizando a forma original do algoritmo de Euclides, na qual cada passo substitui o maior dos dois números dados pela sua diferença com o número menor (não o seu resto), parando quando dois números iguais são alcançados. Um passo do algoritmo de Euclides que substitui o primeiro dos dois números corresponde a um passo na árvore de um nó para o seu filho à direita, e um passo que substitui o segundo dos dois números corresponde a um passo na árvore de um nó para o seu filho à esquerda. A sequência de passos construída desta forma não depende de a/b ser dado na forma irredutível, e forma um caminho da raiz até um nó contendo o número a/b.^[78] Este fato pode ser usado para provar que cada número racional positivo aparece exatamente uma vez nesta árvore.

Por exemplo, 3/4 pode ser encontrado começando na raiz, indo uma vez para a esquerda e depois duas vezes para a direita:

${\displaystyle {\begin{aligned}&\operatorname {mdc} (3,4)&\leftarrow \\={}&\operatorname {mdc} (3,1)&\rightarrow \\={}&\operatorname {mdc} (2,1)&\rightarrow \\={}&\operatorname {mdc} (1,1).\end{aligned}}}$

O algoritmo de Euclides tem quase a mesma relação com outra árvore binária sobre os números racionais, chamada de Árvore de Calkin-Wilf. A diferença é que o caminho é invertido: em vez de produzir um caminho da raiz da árvore até um alvo, produz um caminho do alvo até à raiz.

O algoritmo de Euclides tem uma relação estreita com as frações contínuas.^[79] A sequência de equações pode ser escrita na forma

${\displaystyle {\begin{aligned}{\frac {a}{b}}&=q_{0}+{\frac {r_{0}}{b}}\\{\frac {b}{r_{0}}}&=q_{1}+{\frac {r_{1}}{r_{0}}}\\{\frac {r_{0}}{r_{1}}}&=q_{2}+{\frac {r_{2}}{r_{1}}}\\&\,\,\,\vdots \\{\frac {r_{k-2}}{r_{k-1}}}&=q_{k}+{\frac {r_{k}}{r_{k-1}}}\\&\,\,\,\vdots \\{\frac {r_{N-2}}{r_{N-1}}}&=q_{N}\,.\end{aligned}}}$

O último termo do lado direito é sempre igual ao inverso do lado esquerdo da equação seguinte. Assim, as duas primeiras equações podem ser combinadas para formar

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {r_{1}}{r_{0}}}}}\,.}$

A terceira equação pode ser usada para substituir o termo do denominador r₁/r₀, resultando em

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {r_{2}}{r_{1}}}}}}}\,.}$

A razão final de restos r_k/r_k−1 pode sempre ser substituída usando a equação seguinte na série, até à equação final. O resultado é uma fração contínua

${\displaystyle {\frac {a}{b}}=q_{0}+{\cfrac {1}{q_{1}+{\cfrac {1}{q_{2}+{\cfrac {1}{\ddots +{\cfrac {1}{q_{N}}}}}}}}}=[q_{0};q_{1},q_{2},\ldots ,q_{N}]\,.}$

No exemplo resolvido acima, o mdc(1071, 462) foi calculado, e os quocientes q_k foram 2, 3 e 7, respetivamente. Portanto, a fração 1071/462 pode ser escrita como

${\displaystyle {\frac {1071}{462}}=2+{\cfrac {1}{3+{\cfrac {1}{7}}}}=[2;3,7]}$

o que pode ser confirmado por cálculo.

Calcular um máximo divisor comum é um passo essencial em vários algoritmos de fatoração de inteiros,^[80] tais como o algoritmo rho de Pollard,^[81] o algoritmo de Shor,^[82] o método de fatoração de Dixon^[83] e a fatoração de curva elíptica de Lenstra.^[84] O algoritmo de Euclides pode ser usado para encontrar este MDC de forma eficiente. A fatoração com frações contínuas utiliza frações contínuas, as quais são determinadas com recurso ao algoritmo de Euclides.^[85]

O número de passos para calcular o MDC de dois números naturais, a e b, pode ser denotado por T(a, b).^[96] 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

T(a, b) = T(m, n)

como pode ser visto dividindo todos os passos no algoritmo de Euclides por g.^[97] 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

T(a, b) = 1 + T(b, r₀) = 2 + T(r₀, r₁) = … = N + T(r_N−2, r_N−1) = N + 1

onde T(x, 0) = 0 por hipótese.^[96]

Em cada passo k do algoritmo de Euclides, o quociente q_k e o resto r_k são computados para um dado par de inteiros r_k−2 e r_k−1

r_k−2 = q_k r_k−1 + r_k.

O custo computacional por passo está associado principalmente em encontrar q_k, uma vez que o resto r_k pode ser calculado rapidamente a partir de r_k−2, r_k−1, e q_k

r_k = r_k−2 − q_k r_k−1.

O custo computacional de dividir números de h-bits escala como O(h(ℓ + 1)), onde ℓ é o comprimento do quociente.^[93]

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)².^[114] 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,^[115] o algoritmo de Euclides baseado em subtração é competitivo com a versão baseada em divisão.^[116] Isto é explorado na versão binária do algoritmo de Euclides.^[117]

A combinação do número estimado de passos com o custo computacional estimado por passo mostra que o algoritmo de Euclides cresce quadraticamente (h²) com o número médio de dígitos h nos dois números iniciais a e b. Seja h₀, h₁, ..., h_N−1 representativo do número de dígitos nos sucessivos restos r₀, r₁, ..., r_N−1. Uma vez que o número de passos N cresce linearmente com h, o tempo de execução é limitado por

${\displaystyle O{\Big (}\sum _{i<N}h_{i}(h_{i}-h_{i+1}+2){\Big )}\subseteq O{\Big (}h\sum _{i<N}(h_{i}-h_{i+1}+2){\Big )}\subseteq O(h(h_{0}+2N))\subseteq O(h^{2}).}$

O algoritmo de Euclides é amplamente utilizado na prática, especialmente para números pequenos, devido à sua simplicidade.^[118] 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.^[8] 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.^[11]

O algoritmo binário do MDC é uma alternativa eficiente que substitui a divisão por operações mais rápidas ao explorar a representação binária utilizada pelos computadores.^[119][120] No entanto, esta alternativa também escala como O(h²). Geralmente é mais rápido do que o algoritmo de Euclides em computadores reais, embora escale da mesma forma.^[94] Pode-se obter eficiência adicional examinando apenas os dígitos iniciais dos dois números a e b.^[121][122] O algoritmo binário pode ser estendido para outras bases (algoritmos k-ários),^[123] com aumentos de velocidade de até cinco vezes.^[124] O algoritmo do MDC de Lehmer usa o mesmo princípio geral do algoritmo binário para acelerar o cálculo do MDC em bases arbitrárias.

Uma abordagem recursiva para números inteiros muito grandes (com mais de 25 000 dígitos) leva a algoritmos de MDC de inteiros de tempo quase linear,^[125] como os de Schönhage,^[126][127] e Stehlé e Zimmermann.^[128] Estes algoritmos exploram a forma da matriz 2×2 do algoritmo de Euclides dada acima. Estes métodos quase lineares escalam em geral como O(h log h² log log h).^[94][95]

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.^[28] 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.^[132][133]

O algoritmo de Euclides para números reais difere do seu homólogo inteiro em dois aspetos. Primeiro, os restos r_k são números reais, embora os quocientes q_k 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

${\displaystyle {\frac {a}{b}}={\frac {mg}{ng}}={\frac {m}{n}},}$

e pode ser escrita como uma fração contínua finita [q₀; q₁, q₂, ..., q_N]. Se o algoritmo não parar, a fração a/b é um número irracional e pode ser descrita por uma fração contínua infinita [q₀; q₁, q₂, …].^[134] Exemplos de frações contínuas infinitas são a proporção áurea φ = [1; 1, 1, ...] e a raiz quadrada de dois, √2 = [1; 2, 2, ...].^[135] Quando aplicado a dois números reais arbitrários, é improvável que o algoritmo pare, uma vez que quase todas as razões a/b de dois números reais são irracionais.^[136]

Uma fração contínua infinita pode ser truncada num passo k [q₀; q₁, q₂, ..., q_k] para produzir uma aproximação de a/b que melhora à medida que k aumenta. A aproximação é descrita por convergentes m_k/n_k; o numerador e os denominadores são coprimos e obedecem à relação de recorrência

${\displaystyle {\begin{aligned}m_{k}&=q_{k}m_{k-1}+m_{k-2}\\n_{k}&=q_{k}n_{k-1}+n_{k-2},\end{aligned}}}$

onde m₋₁ = n₋₂ = 1 e m₋₂ = n₋₁ = 0 são os valores iniciais da recursão. A convergente m_k/n_k é a melhor aproximação por número racional de a/b com denominador n_k:^[137]

${\displaystyle \left|{\frac {a}{b}}-{\frac {m_{k}}{n_{k}}}\right|<{\frac {1}{n_{k}^{2}}}.}$

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.^[129] O procedimento básico é semelhante ao dos inteiros. A cada passo k, um polinômio quociente q_k(x) e um polinômio resto r_k(x) são identificados para satisfazer a equação recursiva

${\displaystyle r_{k-2}(x)=q_{k}(x)r_{k-1}(x)+r_{k}(x),}$

onde r₋₂(x) = a(x) e r₋₁(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[r_k(x)] < grau[r_k−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).^[138]

Por exemplo, considere os seguintes dois polinômios quárticos, que se fatoram cada um em dois polinômios quadráticos

${\displaystyle {\begin{aligned}a(x)&=x^{4}-4x^{3}+4x^{2}-3x+14=(x^{2}-5x+7)(x^{2}+x+2)\qquad {\text{e}}\\b(x)&=x^{4}+8x^{3}+12x^{2}+17x+6=(x^{2}+7x+3)(x^{2}+x+2).\end{aligned}}}$

Ao dividir a(x) por b(x), obtém-se um resto r₀(x) = x³ + (2/3)x² + (5/3)x − (2/3). No passo seguinte, b(x) é dividido por r₀(x), produzindo um resto r₁(x) = x² + x + 2. Finalmente, dividir r₀(x) por r₁(x) produz um resto nulo, indicando que r₁(x) é o polinômio máximo divisor comum de a(x) e b(x), o que é consistente com a sua fatoração.

Muitas das aplicações descritas acima para inteiros transitam para os polinômios.^[139] O algoritmo de Euclides pode ser usado para resolver equações diofantinas lineares e problemas do resto chinês para polinômios; frações contínuas de polinômios também podem ser definidas.

O algoritmo de Euclides para polinômios tem outras aplicações, tais como as cadeias de Sturm, um método para contar os zeros de um polinômio que residem dentro de um dado intervalo real.^[140] Isto, por sua vez, tem aplicações em várias áreas, como o critério de estabilidade de Routh-Hurwitz na teoria de controle.^[141]

Por fim, os coeficientes dos polinômios não precisam de ser extraídos dos inteiros, números reais ou sequer dos números complexos. Por exemplo, os coeficientes podem ser extraídos de um corpo geral, como os corpos finitos GF(p) descritos acima. As conclusões correspondentes sobre o algoritmo de Euclides e as suas aplicações mantêm-se mesmo para tais polinômios.^[129]

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.^[142] Ao definir um análogo do algoritmo de Euclides, pode-se demonstrar que os inteiros gaussianos são unicamente fatoráveis, pelo argumento acima.^[43] 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.^[142] 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,^[143] mas difere em dois aspetos. Como antes, definimos r₋₂ = α e r₋₁ = β, e a tarefa a cada passo k é identificar um quociente q_k e um resto r_k de tal modo que

${\displaystyle r_{k}=r_{k-2}-q_{k}r_{k-1},}$

onde cada resto é estritamente menor que o seu predecessor: ${\displaystyle |r_{k}|<|r_{k-1}|}$. A primeira diferença é que os quocientes e restos são eles próprios inteiros gaussianos e, assim, são números complexos. Os quocientes q_k são geralmente encontrados arredondando as partes real e complexa da razão exata (como o número complexo α/β) para os inteiros mais próximos.^[143] A segunda diferença reside na necessidade de definir como é que um resto complexo pode ser "menor" do que outro. Para fazer isto, uma função de norma f(u + vi) = u² + v² é definida, convertendo cada inteiro gaussiano u + vi num inteiro ordinário. Após cada passo k do algoritmo de Euclides, a norma do resto f(r_k) é menor do que a norma do resto anterior, f(r_k−1). Uma vez que a norma é um inteiro não-negativo e diminui a cada passo, o algoritmo de Euclides para os inteiros gaussianos termina num número finito de passos.^[144] O último resto não-nulo é mdc(α, β), o inteiro gaussiano de maior norma que divide tanto α quanto β; este é único a menos de multiplicação por uma unidade, ±1 ou ±i.^[145]

Muitas das outras aplicações do algoritmo de Euclides transitam para os inteiros gaussianos. Por exemplo, ele pode ser usado para resolver equações diofantinas lineares e problemas do resto chinês para inteiros gaussianos;^[146] frações contínuas de inteiros gaussianos também podem ser definidas.^[143]

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.^[147][148] 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).^[149] 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.^[150][151] 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.^[152]

O teorema fundamental da aritmética aplica-se a qualquer domínio euclidiano: Qualquer número de um domínio euclidiano pode ser fatorado de forma única em elementos irredutíveis. Qualquer domínio euclidiano é um domínio de fatoração única (DFU), embora o inverso não seja verdadeiro.^[152] Os domínios euclidianos e os DFUs são subclasses dos domínios MDC, domínios nos quais um máximo divisor comum de dois números existe sempre.^[153] Por outras palavras, pode existir um máximo divisor comum (para todos os pares de elementos num domínio), embora possa não ser possível encontrá-lo usando um algoritmo de Euclides. Um domínio euclidiano é sempre um domínio de ideais principais (DIP), um domínio de integridade no qual todo ideal é um ideal principal.^[154] Novamente, o inverso não é verdadeiro: nem todo DIP é um domínio euclidiano.

A fatoração única dos domínios euclidianos é útil em muitas aplicações. Por exemplo, a fatoração única dos inteiros gaussianos é conveniente para derivar fórmulas para todos os ternos pitagóricos e para provar o teorema dos dois quadrados de Fermat.^[142] A fatoração única também foi um elemento-chave numa tentativa de prova do Último Teorema de Fermat publicada em 1847 por Gabriel Lamé, o mesmo matemático que analisou a eficiência do algoritmo de Euclides, baseada numa sugestão de Joseph Liouville.^[155] A abordagem de Lamé exigia a fatoração única de números da forma x + ωy, onde x e y são inteiros, e ω = e^2iπ/n é uma n-ésima raiz de 1, isto é, ωⁿ = 1. Embora esta abordagem seja bem-sucedida para alguns valores de n (como n = 3, os inteiros de Eisenstein), em geral tais números não se fatoram de forma única. Esta falha da fatoração única nalguns corpos ciclotômicos levou Ernst Kummer ao conceito de números ideais e, mais tarde, Richard Dedekind aos ideais.^[156]

Fatoração única de inteiros quadráticos

Os anéis de inteiros quadráticos são úteis para ilustrar os domínios euclidianos. Os inteiros quadráticos são generalizações dos inteiros gaussianos nas quais a unidade imaginária i é substituída por um número ω. Assim, eles têm a forma u + vω, onde u e v são inteiros e ω tem uma de duas formas, dependendo de um parâmetro D. Se D não for igual a um múltiplo de quatro mais um, então

${\displaystyle \omega ={\sqrt {D}}.}$

Se, no entanto, D for igual a um múltiplo de quatro mais um, então

${\displaystyle \omega ={\frac {1+{\sqrt {D}}}{2}}.}$

Se a função f corresponder a uma função de norma, como a usada para ordenar os inteiros gaussianos acima, então o domínio é conhecido como norma-euclidiano. Os anéis norma-euclidianos de inteiros quadráticos são exatamente aqueles onde D é um dos valores −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 ou 73.^[157][158] Os casos D = −1 e D = −3 produzem os inteiros gaussianos e os inteiros de Eisenstein, respetivamente.

Se a f for permitido ser qualquer função euclidiana, então a lista de possíveis valores de D para os quais o domínio é euclidiano ainda não é conhecida.^[159] O primeiro exemplo de um domínio euclidiano que não era norma-euclidiano (com D = 69) foi publicado em 1994.^[159] Em 1973, Weinberger provou que um anel de inteiros quadráticos com D > 0 é euclidiano se, e somente se, for um domínio de ideais principais, partindo do princípio que a hipótese generalizada de Riemann é válida.^[130]

O algoritmo de Euclides pode ser aplicado a alguns anéis não comutativos, tais como o conjunto de quatérnios de Hurwitz.^[131][160] 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.^[131][160] Escolhendo os divisores à direita, o primeiro passo para encontrar o mdc(α, β) pelo algoritmo de Euclides pode ser escrito

${\displaystyle \rho _{0}=\alpha -\psi _{0}\beta =(\xi -\psi _{0}\eta )\delta ,}$

onde ψ₀ representa o quociente e ρ₀ o resto. Aqui o quociente e o resto são escolhidos de modo a que (se for não-nulo) o resto cumpra N(ρ₀) < N(β) para uma "função euclidiana" N definida de forma análoga às funções euclidianas dos domínios euclidianos no caso não comutativo.^[160] Esta equação mostra que qualquer divisor comum à direita de α e β é igualmente um divisor comum do resto ρ₀. A equação análoga para os divisores à esquerda seria

${\displaystyle \rho _{0}=\alpha -\beta \psi _{0}=\delta (\xi -\eta \psi _{0}).}$

Com qualquer uma das escolhas, o processo é repetido como acima até que o maior divisor comum à direita ou à esquerda seja identificado. Assim como no domínio euclidiano, o "tamanho" do resto ρ₀ (formalmente, a sua função euclidiana ou "norma") deve ser estritamente menor que β, e deve existir apenas um número finito de possíveis tamanhos para ρ₀, de modo que é garantido que o algoritmo termine.^[161]

Muitos resultados para o MDC transitam para os números não comutativos. Por exemplo, a identidade de Bézout afirma que o mdc(α, β) à direita pode ser expresso como uma combinação linear de α e β.^[162] Por outras palavras, existem números σ e τ tais que

${\displaystyle \Gamma _{\text{direita}}=\sigma \alpha +\tau \beta .}$

A identidade análoga para o MDC à esquerda é praticamente a mesma:

${\displaystyle \Gamma _{\text{esquerda}}=\alpha \sigma +\beta \tau .}$

A identidade de Bézout pode ser usada para resolver equações diofantinas. Por exemplo, uma das provas padrão do teorema dos quatro quadrados de Lagrange, de que todo número inteiro positivo pode ser representado como uma soma de quatro quadrados, baseia-se nos MDCs de quatérnios desta forma.^[161]