Algoritmo Euclidiano - Euclidean algorithm

Método de Euclides para encontrar o máximo divisor comum (GCD) de dois comprimentos iniciais BA e DC, ambos definidos como múltiplos de um comprimento de "unidade" comum. Sendo o comprimento DC mais curto, ele é usado para "medir" BA, mas apenas uma vez porque o EA restante é menor que DC. EA agora mede (duas vezes) o comprimento DC mais curto, com o restante FC mais curto que EA. Então FC mede (três vezes) o comprimento EA. Como não há resto, o processo termina com FC sendo o GCD. À direita , o exemplo de Nicômaco com os números 49 e 21 resultando em seu GCD de 7 (derivado de Heath 1908: 300).

Em matemática , o algoritmo euclidiano , ou algoritmo de Euclides , é um método eficiente para calcular o máximo divisor comum (GCD) de dois inteiros (números), o maior número que os divide sem deixar resto . Recebeu o nome do antigo matemático grego Euclides , que o descreveu pela primeira vez em seus Elementos (c. 300 aC). É um exemplo de algoritmo , um procedimento passo a passo para realizar um cálculo de acordo com regras bem definidas e é um dos algoritmos mais antigos em uso comum. Ele pode ser usado para reduzir as frações à sua forma mais simples e é parte de muitos outros cálculos criptográficos e teóricos numéricos.

O algoritmo euclidiano é baseado no princípio de que o maior divisor comum de dois números não muda se o número maior for substituído por sua diferença com o número menor. Por exemplo, 21 é o GCD de 252 e 105 (como 252 = 21 × 12 e 105 = 21 × 5), e o mesmo número 21 também é o GCD de 105 e 252 - 105 = 147. Uma vez que esta substituição reduz o maior dos dois números, repetir este processo dá pares sucessivamente menores de números até que os dois números se tornem iguais. Quando isso ocorre, eles são o GCD dos dois números originais. Por invertendo os passos ou usando o algoritmo de Euclides estendida , o MDC pode ser expressa como uma combinação linear dos dois números originais, que é a soma dos dois números, cada uma multiplicada por um número inteiro (por exemplo, 21 = 5 × 105 + (−2) × 252). O fato de o GCD sempre poder ser expresso dessa forma é conhecido como a identidade de Bézout .

A versão do algoritmo euclidiano descrito acima (e por Euclides) pode levar muitos passos de subtração para encontrar o GCD quando um dos números fornecidos é muito maior que o outro. Uma versão mais eficiente do algoritmo encurta essas etapas, em vez de substituir o maior dos dois números por seu resto quando dividido pelo menor dos dois (com esta versão, o algoritmo para ao atingir um resto zero). Com essa melhoria, o algoritmo nunca requer mais etapas do que cinco vezes o número de dígitos (base 10) do inteiro menor. Isso foi comprovado por Gabriel Lamé em 1844 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 euclidiano tem muitas aplicações teóricas e práticas. É usado para reduzir as frações à sua forma mais simples e para realizar a divisão em aritmética modular . Os cálculos que usam esse algoritmo fazem parte dos protocolos criptográficos usados ​​para proteger as comunicações da Internet e nos métodos para quebrar esses criptosistemas pela fatoração de grandes números compostos . O algoritmo euclidiano pode ser usado para resolver equações diofantinas , como encontrar números que satisfaçam múltiplas congruências de acordo com o teorema do resto chinês , para construir frações contínuas e para encontrar aproximações racionais precisas para números reais. Finalmente, ele pode ser usado como uma ferramenta básica para provar teoremas na teoria dos números , como o teorema dos quatro quadrados de Lagrange e a unicidade das fatorações primárias . 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 19 para outros tipos de números, como inteiros gaussianos e polinômios de uma variável. Isso levou a noções algébricas abstratas modernas , como os domínios euclidianos .

Antecedentes: maior divisor comum

O algoritmo euclidiano calcula o máximo divisor comum (GCD) de dois números naturais a e b . A maior divisor comum g é o maior número natural que divide tanto um e b sem deixar um resíduo. Os sinônimos para o GCD incluem o maior fator comum (GCF), o maior fator comum (HCF), o maior divisor comum (HCD) e a maior medida comum (GCM). O maior divisor comum é frequentemente escrito como mdc ( ab ) ou, mais simplesmente, como ( ab ), embora a última notação seja ambígua, também usada para conceitos como um ideal no anel de inteiros , que está próximo relacionado ao GCD.

Se GCD ( ab ) = 1, então um e b são referidos como sendo primos entre si (ou relativamente primo). Esta propriedade não implica que a ou b sejam eles próprios números primos . Por exemplo, nem 6 nem 35 são números primos, uma vez que ambos têm dois fatores primos: 6 = 2 × 3 e 35 = 5 × 7. No entanto, 6 e 35 são coprimos. Nenhum número natural diferente de 1 divide 6 e 35, uma vez que eles não têm fatores primos em comum.

"Retângulo alto e delgado dividido em uma grade de quadrados. O retângulo tem dois quadrados de largura e cinco quadrados de altura."
Um retângulo de 24 x 60 é coberto com dez ladrilhos quadrados de 12 x 12, onde 12 é o GCD de 24 e 60. Mais geralmente, um retângulo a -by- b pode ser coberto com ladrilhos quadrados de comprimento lateral c somente se c for um divisor comum de a e b .

Seja g = mdc ( ab ). Uma vez que um e b são ambos múltiplos de g , que pode ser escrito um  =  mg e b  =  ng , e não existe um número maior G  >  g para os quais isto é 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 divide tanto um e b também deve dividir g . A maior divisor comum g de um e b é a única (positivo) divisor comum de um e b que é divisível por qualquer outro divisor comum c .

O GCD pode ser visualizado da seguinte forma. Considere uma área retangular a por b , e qualquer divisor comum c que divide a e b exatamente. Os lados do retângulo podem ser divididos em segmentos de comprimento c , que divide o retângulo em uma grade de quadrados de comprimento c . O maior divisor comum g é o maior valor de c para o qual isso é possível. Para ilustração, uma área retangular de 24 por 60 pode ser dividida em uma grade de: quadrados 1 por 1, quadrados 2 por 2, quadrados 3 por 3, quadrados 4 por 4, 6 por -6 quadrados ou quadrados 12 por 12. Portanto, 12 é o maior divisor comum de 24 e 60. Uma área retangular de 24 por 60 pode ser dividida em uma grade de quadrados de 12 por 12, com dois quadrados ao longo de uma aresta (24/12 = 2) e cinco quadrados ao longo do outro (60/12 = 5).

O GCD de dois números um e b é o produto dos factores primos partilhados pelos dois números, onde um mesmo factor primo podem ser utilizados várias vezes, mas apenas durante o tempo que o produto destes factores divide tanto um e b . Por exemplo, uma vez que 1386 pode ser fatorado em 2 × 3 × 3 × 7 × 11, e 3213 pode ser fatorado em 3 × 3 × 3 × 7 × 17, o maior divisor comum de 1386 e 3213 é igual a 63 = 3 × 3 × 7, o produto de seus fatores primos compartilhados. Se dois números não têm fatores primos em comum, seu maior divisor comum é 1 (obtido aqui como uma instância do produto vazio ), em outras palavras, eles são coprimos. Uma vantagem chave do algoritmo euclidiano é que ele pode encontrar o GCD com eficiência sem ter que calcular os fatores primos. Acredita-se que a fatoração de grandes inteiros seja um problema computacionalmente muito difícil, e a segurança de muitos protocolos criptográficos amplamente usados é baseada em sua inviabilidade.

Outra definição do GCD é útil em matemática avançada, particularmente na teoria dos anéis . A maior divisor comum g   de dois números diferentes de zero a e b é também menor a sua combinação linear integrante positivo, isto é, o menor número positivo da forma de u  +  v , onde u e v são números inteiros. O conjunto de todas as combinações lineares integrais de um e b é, na verdade, o mesmo que o conjunto de todos os múltiplos de g ( mg , onde m é um número inteiro). Em linguagem matemática moderna, o ideal gerado por um e b é o ideal gerado por  g sozinho (um ideal gerado por um único elemento é chamado de ideal principal , e todos os ideais dos inteiros são ideais principais). Algumas propriedades do GCD são de fato mais fácil ver com esta descrição, por exemplo, o fato de que qualquer divisor comum de um e b também divide o GCD (que divide ambos os termos de ua  +  vb ). A equivalência desta definição de GCD com as outras definições é descrita abaixo.

O GCD 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 tomando-se repetidamente os GCDs de pares de números. Por exemplo,

mdc ( abc ) = mdc ( a , mdc ( bc )) = mdc (mdc ( ab ),  c ) = mdc (mdc ( ac ),  b ).

Assim, o algoritmo de Euclides, que calcula o GCD de dois inteiros, é suficiente para calcular o GCD de muitos inteiros arbitrariamente.

Descrição

Procedimento

O algoritmo euclidiano prossegue em uma série de etapas de forma que a saída de cada etapa seja usada como entrada para a próxima. Seja k um inteiro que conta os passos do algoritmo, começando com zero. Assim, a etapa inicial corresponde a k  = 0, a próxima etapa corresponde a k  = 1 e assim por diante.

Cada etapa começa com dois restos não negativos r k −1 e r k −2 . Uma vez que o algoritmo garante que os restos diminuam constantemente a cada passo, r k −1 é menor que seu predecessor r k −2 . O objetivo da k- ésima etapa é encontrar um quociente q k e o resto r k que satisfaçam a equação

e que têm 0 ≤ r k  <  r k −1 . Em outras palavras, múltiplos do número menor r k −1 são subtraídos do número maior r k −2 até que o restante r k seja menor do que r k −1 .

No passo inicial ( k  = 0), os restos r −2 e r −1 são iguais a e b , os números para os quais o GCD é procurado. Na próxima etapa ( k  = 1), os restantes são iguais b e o resto r 0 da etapa inicial, e assim por diante. Assim, o algoritmo pode ser escrito como uma sequência de equações

Se a for menor que b , a primeira etapa do algoritmo troca os números. Por exemplo, se a  <  b , o quociente inicial q 0 é igual a zero e o resto r 0 é a . Assim, r k é menor que seu predecessor r k −1 para todo k  ≥ 0.

Uma vez que os restos diminuem a cada passo, mas nunca podem ser negativos, um resto r N deve eventualmente ser igual a zero, ponto em que o algoritmo para. O resto final diferente de zero r N −1 é o máximo divisor comum de a e b . O número N não pode ser infinito porque há apenas um número finito de inteiros não negativos entre o resto inicial r 0 e zero.

Prova de validade

A validade do algoritmo euclidiano pode ser comprovada por um argumento de duas etapas. Na primeira etapa, o resto final diferente de zero r N −1 é mostrado para dividir a e b . Uma vez que é um divisor comum, deve ser menor ou igual ao máximo divisor comum g . No segundo passo, é mostrado que qualquer divisor comum de um e b , incluindo g , deve dividir r N -1 ; portanto, g deve ser menor ou igual a r N −1 . Essas duas conclusões são inconsistentes, a menos que r N −1  =  g .

Para demonstrar que r N -1 divide tanto um e b (o primeiro passo), r N -1 divide o seu antecessor r N -2

r N −2 = q N r N −1

já que o resto final r N é zero. r N −1 também divide seu próximo predecessor r N −3

r N −3 = q N −1 r N −2 + r N −1

porque divide os dois termos do lado direito da equação. Iterando o mesmo argumento, r N −1 divide todos os restos anteriores, incluindo a e b . Nenhum dos restos anteriores r N -2 , r N -3 , etc dividir um e b , uma vez que deixam um resíduo. Desde r N -1 é um divisor comum de um e b , r N -1  ≤  g .

No segundo passo, qualquer número natural c que divide tanto um e b (em outras palavras, qualquer divisor comum de um 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 0 , uma vez que r 0  =  a  -  q 0 b  =  mc  -  q 0 nc  = ( m  -  q 0 n ) c . Um argumento análogo mostra que c também divide os restos subsequentes r 1 , r 2 , 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 ), segue-se que g  =  r N −1 . Assim, g é o maior divisor comum de todos os pares sucessivos:

g = mdc ( a , b ) = mdc ( b , r 0 ) = mdc ( r 0 , r 1 ) =… = mdc ( r N −2 , r N −1 ) = r N −1 .

Exemplo trabalhado

Animação em que ladrilhos quadrados cada vez menores são adicionados para cobrir um retângulo completamente.
Animação baseada em subtração do algoritmo euclidiano. O retângulo inicial tem dimensões a  = 1071 eb  = 462. Quadrados de tamanho 462 × 462 são colocados dentro dele, deixando um retângulo 462 × 147. Este retângulo é lado a lado com 147 × 147 quadrados até que fique um retângulo 21 × 147, que por sua vez é lado a lado com quadrados 21 × 21, não deixando nenhuma área descoberta. O menor tamanho quadrado, 21, é o GCD de 1071 e 462.

Para ilustração, o algoritmo euclidiano pode ser usado para encontrar o maior divisor comum de a  = 1071 eb  = 462. Para começar, múltiplos de 462 são subtraídos de 1071 até que o restante seja menor que 462. Dois desses múltiplos podem ser subtraídos ( q 0  = 2), deixando um resto de 147:

1071 = 2 × 462 + 147.

Em seguida, múltiplos de 147 são subtraídos de 462 até que o restante seja inferior a 147. Três múltiplos podem ser subtraídos ( q 1  = 3), deixando um restante de 21:

462 = 3 × 147 + 21.

Em seguida, os múltiplos de 21 são subtraídos de 147 até que o restante seja inferior a 21. Sete múltiplos podem ser subtraídos ( q 2  = 7), não deixando nenhum 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. Isso está de acordo com o mdc (1071, 462) encontrado pela fatoração de números primos acima . Na forma tabular, as etapas são:

Etapa k Equação Quociente e resto
0 1071 = q 0 462 + r 0 q 0 = 2 e r 0 = 147
1 462 = q 1 147 + r 1 q 1 = 3 e r 1 = 21
2 147 = q 2 21 + r 2 q 2 = 7 e r 2 = 0 ; algoritmo termina

Visualização

O algoritmo euclidiano pode ser visualizado em termos da analogia dos blocos dada acima para o maior divisor comum. Suponha que desejamos cobrir um retângulo a -by- b com ladrilhos exatamente quadrados, onde a é o maior dos dois números. Nós primeiro tentar telha do retângulo usando b -by- b azulejos quadrados; entretanto, isso deixa um retângulo residual r 0 -by- b até chegar, onde r 0  <  b . Tentamos então colocar o retângulo residual com ladrilhos quadrados r 0 -by- r 0 . Isso deixa um segundo retângulo residual r 1 -by- r 0 , que tentamos colocar lado a lado usando r 1 -by- r 1 ladrilhos quadrados e assim por diante. A seqüência termina quando não houver retângulo residual, ou seja, quando os ladrilhos quadrados cobrirem exatamente o retângulo residual anterior. O comprimento dos lados do menor ladrilho quadrado é o GCD das dimensões do retângulo original. Por exemplo, o menor ladrilho quadrado na figura adjacente é 21 por 21 (mostrado em vermelho), e 21 é o GCD de 1071 e 462, as dimensões do retângulo original (mostrado em verde).

Divisão euclidiana

Em cada etapa k , o algoritmo euclidiano calcula um quociente q k e o resto r k de dois números r k −1 e r k −2

r k −2 = q k r k −1 + r k

onde o r k é não negativo e é estritamente menor que o valor absoluto de r k −1 . O teorema que subjaz à definição da divisão euclidiana garante que tal quociente e resto sempre existam e sejam únicos.

Na versão original de Euclides do algoritmo, o quociente e o resto são encontrados por subtração repetida; isto é, r k −1 é subtraído de r k −2 repetidamente até que o restante 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 todas as etapas entre duas trocas em uma única etapa, que é, portanto, mais eficiente. Além disso, os quocientes não são necessários, portanto, pode-se substituir a divisão euclidiana pela operação módulo , que fornece apenas o resto. Assim, a iteração do algoritmo Euclidiano torna-se simplesmente

r k = r k −2 mod r k −1 .

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

function gcd(a, b)
    while b ≠ 0
        t := b
        b := a mod b
        a := t
    return a

No início da k- ésima iteração, a variável b mantém o último resto r k −1 , enquanto a variável a mantém seu predecessor, r k −2 . O passo b  : = a mod b é equivalente à fórmula de recursão acima r kr k −2 mod r k −1 . A variável temporária t mantém o valor de r k −1 enquanto o próximo resto r k está sendo calculado. No final da iteração do loop, a variável b mantém o resto r k , enquanto a variável a mantém seu predecessor, r k −1 .

(Se entradas negativas são permitidas, ou se a função mod pode retornar valores negativos, a última linha deve ser alterada para return max (a, −a).)

Na versão baseada em subtração, que era a versão original de Euclides, o cálculo do restante ( ) é substituído por subtração repetida. Ao contrário da versão baseada em divisão, que funciona com inteiros arbitrários como entrada, a versão baseada em subtração supõe que a entrada consiste em inteiros positivos e para quando a = b : b := a mod b

function gcd(a, b)
    while a ≠ b 
        if a > b
            a := a − b
        else
            b := b − a
    return a

As variáveis a e b se alternam mantendo os restos anteriores r k −1 e r k −2 . Suponha que a seja maior que b no início de uma iteração; então a é igual a r k −2 , pois r k −2 > r k −1 . Durante a iteração do loop, a é reduzido em múltiplos do resto anterior b até que a seja menor que b . Então a é o próximo resto r k . Então b é reduzido por múltiplos de a até que seja novamente menor que a , dando o próximo resto r k +1 , e assim por diante.

A versão recursiva é baseada na igualdade dos GCDs de resíduos sucessivos e na condição de parada gcd ( r N −1 , 0) =  r N −1 .

function gcd(a, b)
    if b = 0
        return a
    else
        return gcd(b, a mod b)

(Como acima, se entradas negativas são permitidas, ou se a função mod pode retornar valores negativos, a instrução " return a" deve ser alterada para " return max (a, −a)".)

Para ilustração, o mdc (1071, 462) é calculado a partir do mdc equivalente (462, 1071 mod 462) = mdc (462, 147). O último GCD é 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.

Método dos menores restos absolutos

Em outra versão do algoritmo de Euclides, o quociente em cada etapa é aumentado em um se o resto negativo resultante for menor em magnitude do que o resto positivo típico. Anteriormente, a equação

r k −2 = q k r k −1 + r k

assumiu 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 euclidiano de modo que

| r k | ≤ | r k −1 | / 2

em cada etapa.

Leopold Kronecker mostrou que esta versão requer o menor número de etapas de qualquer versão do algoritmo de Euclides. De modo mais geral, provou-se que, para todos os números de entrada de um e b , o número de etapas é mínima, se e somente se q k é escolhido de modo que , onde é a razão de ouro .

Desenvolvimento histórico

"Representação de Euclides como um homem barbudo segurando um par de divisórias em uma placa."
O algoritmo euclidiano foi provavelmente inventado antes de Euclides , representado aqui segurando uma bússola em uma pintura de cerca de 1474.

O algoritmo euclidiano é um dos algoritmos mais antigos de uso comum. Afigura-se em de Euclides Elementos (c. 300 aC), especificamente no Livro 7 (proposições 1-2) e Livro 10 (proposições 2-3). No Livro 7, o algoritmo é formulado para inteiros, enquanto no Livro 10, é formulado para comprimentos de segmentos de linha. (No uso moderno, dir-se-ia que foi formulado lá 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 há unidade natural de comprimento, área, ou volume; o conceito de números reais era desconhecido naquela época.) O último algoritmo é geométrico. O GCD de dois comprimentos de um e b corresponde ao maior comprimento de g que as medidas de um e b uniformemente; em 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 em seus Elementos . O matemático e historiador BL van der Waerden sugere que o Livro VII deriva de um livro sobre teoria dos números escrito por matemáticos na escola de Pitágoras . O algoritmo era provavelmente conhecido por Eudoxus de Cnidus (cerca de 375 aC). O algoritmo pode até mesmo ser anterior a Eudoxus, a julgar pelo uso do termo técnico ἀνθυφαίρεσις ( antifairese , subtração recíproca) nas obras de Euclides e Aristóteles .

Séculos depois, o algoritmo de Euclides foi descoberto independentemente tanto na Índia quanto na China, principalmente para resolver as equações diofantinas que surgiram na astronomia e fazer calendários precisos. No final do século 5, o matemático e astrônomo indiano Aryabhata descreveu o algoritmo como o "pulverizador", talvez por causa de sua eficácia na resolução de equações diofantinas. Embora um caso especial do teorema do resto chinês já tenha sido descrito no livro chinês Sunzi Suanjing , a solução geral foi publicada por Qin Jiushao em seu livro de 1247 Shushu Jiuzhang (數 書 九章Mathematical Treatise in Nine Sections ). O algoritmo euclidiano foi descrito numericamente e popularizado na Europa na segunda edição de Problèmes plaisants et délectables ( Problemas agradáveis ​​e agradáveis , 1624) de Bachet . Na Europa, era igualmente usado para resolver equações diofantinas e no desenvolvimento de frações contínuas . O algoritmo Euclidiano estendido foi publicado pelo matemático inglês Nicholas Saunderson , que o atribuiu a Roger Cotes como um método para calcular frações contínuas de forma eficiente.

No século 19, o algoritmo euclidiano levou ao desenvolvimento de novos sistemas numéricos, como inteiros gaussianos e inteiros de Eisenstein . Em 1815, Carl Gauss usou o algoritmo euclidiano para demonstrar a fatoração única de inteiros gaussianos , embora seu trabalho tenha sido publicado pela primeira vez em 1832. Gauss mencionou o algoritmo em seu Disquisitiones Arithmeticae (publicado em 1801), mas apenas como um método para frações contínuas . Peter Gustav Lejeune Dirichlet parece ter sido o primeiro a descrever o algoritmo euclidiano como base para grande parte da teoria dos números. Lejeune Dirichlet observou que muitos resultados da teoria dos números, como a fatoração única, seriam válidos para qualquer outro sistema de números ao qual o algoritmo euclidiano pudesse ser aplicado. As palestras de Lejeune Dirichlet sobre a teoria dos números foram editadas e estendidas por Richard Dedekind , que usou o algoritmo de Euclides para estudar inteiros algébricos , um novo tipo geral de número. Por exemplo, Dedekind foi o primeiro a provar o teorema dos dois quadrados de Fermat usando a fatoração única de inteiros gaussianos. Dedekind também definiu o conceito de domínio euclidiano , um sistema numérico no qual uma versão generalizada do algoritmo euclidiano pode ser definida (conforme descrito abaixo ). Nas últimas décadas do século 19, o algoritmo euclidiano foi gradualmente eclipsado pela teoria mais geral dos ideais de Dedekind .

"[O algoritmo euclidiano] é o avô de todos os algoritmos, porque é o algoritmo não trivial mais antigo que sobreviveu até os dias atuais."

Donald Knuth , The Art of Computer Programming, Vol. 2: Seminumerical Algorithms , 2ª edição (1981), p. 318.

Outras aplicações do algoritmo de Euclides foram desenvolvidas no século XIX. Em 1829, Charles Sturm mostrou que o algoritmo era útil no método da cadeia de Sturm para contar as raízes reais dos polinômios em qualquer intervalo determinado.

O algoritmo euclidiano foi o primeiro algoritmo de relação inteira , que é um método para encontrar relações inteiras entre números reais comensuráveis. Vários novos algoritmos de relação inteira foram desenvolvidos, como o algoritmo de Helaman Ferguson e RW Forcade (1979) e o algoritmo LLL .

Em 1969, Cole e Davie desenvolveram um jogo para dois jogadores baseado no algoritmo euclidiano, chamado The Game of Euclid , que possui uma estratégia ótima. Os jogadores começam com duas pilhas de um e b pedras. Os jogadores se revezam removendo m múltiplos da pilha menor da maior. Assim, se as duas pilhas consistem em x e y pedras, onde x é maior que y , o próximo jogador pode reduzir a pilha maior de x pedras para x - minhas pedras, enquanto o último é um inteiro não negativo. O vencedor é o primeiro jogador a reduzir uma pilha a zero pedras.

Aplicações matemáticas

A identidade de Bézout

Identidade de bézout afirma que o maior divisor comum g de dois inteiros a e b podem ser representados como uma soma linear dos dois números originais de um e b . Em outras palavras, sempre é possível encontrar inteiros s e t tais que g  =  sa  +  tb .

Os inteiros s e t podem ser calculados a partir dos quocientes q 0 , q 1 , etc. invertendo a ordem das equações no algoritmo de Euclides. Começando com a penúltima equação, g pode ser expresso em termos do quociente q N −1 e os dois restos anteriores, r N −2 e r N −3 :

g = r N −1 = r N −3 - q N −1 r N −2  .

Esses dois remanescentes podem ser expressos da mesma forma em termos de seus quocientes e remanescentes anteriores,

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  .

Substituir essas fórmulas por r N −2 e r N −3 na primeira equação resulta em g como uma soma linear dos restos r N −4 e r N −5 . O processo de substituição de restos por fórmulas que envolvam os seus antecessores pode ser continuado até que os números originais a e b são alcançados:

r 2 = r 0 - q 2 r 1
r 1 = b - q 1 r 0
r 0 = a - q 0 b .

Depois de todos os restos de r 0 , r 1 , etc, foram substituídos, a equação final expressa g como uma soma linear de um e b : g  =  sa  +  tb . A identidade de Bézout e, portanto, o algoritmo anterior, podem ser generalizados para o contexto de domínios euclidianos .

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 de ua  +  vb , onde u e v são quaisquer dois inteiros. Uma vez que um e b são ambos divisível por g , cada número no conjunto é divisível por g . Em outras palavras, cada número do conjunto é um múltiplo inteiro de g . Isso é verdade para cada divisor comum de a e b . No entanto, ao contrário de outros divisores comuns, o maior divisor comum é um membro do conjunto; por identidade de bézout, escolhendo u  =  s e v  =  tg . Um divisor comum menor não pode ser um membro do conjunto, uma vez que cada membro do conjunto deve ser divisível por g . Por outro lado, qualquer múltiplo m de g pode ser obtida por escolha u  =  ms e v  =  mt , onde s e t são números inteiros de identidade de Bézout. Isso 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 . Em outras palavras, o conjunto de todos os montantes possíveis de múltiplos inteiros de dois números ( um e b ) é equivalente ao conjunto de múltiplos de GCD ( a , b ). O GCD é considerado o gerador do ideal de a e b . Essa definição GCD levou aos conceitos algébricos abstratos modernos de um ideal principal (um ideal gerado por um único elemento) e um domínio ideal principal (um domínio em que todo ideal é um ideal principal).

Certos problemas podem ser resolvidos usando este resultado. Por exemplo, considere dois copos de medição de volume a e b . Adicionando / subtraindo u múltiplos da primeira xícara ev múltiplos da segunda xícara, qualquer volume ua  +  vb pode ser medido. Esses volumes são todos múltiplos de g  = gcd ( ab ).

Algoritmo Euclidiano estendido

Os inteiros s e t da identidade de Bézout podem ser calculados eficientemente usando o algoritmo euclidiano estendido . Esta extensão adiciona duas equações recursivas ao algoritmo de Euclides

s k = s k −2 - q k s k −1
t k = t k −2 - q k t k −1

com os valores iniciais

s −2 = 1, t −2 = 0
s −1 = 0, t −1 = 1.

Usando essa recursão, os inteiros de Bézout s e t são dados por s  =  s N e t  =  t N , onde N + 1 é a etapa na qual o algoritmo termina com r N + 1  = 0.

A validade desta abordagem pode ser demonstrada por indução. Suponha que a fórmula de recursão esteja correta até a etapa k  - 1 do algoritmo; em outras palavras, assuma que

r j = s j a + t j b

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

r k = r k −2 - q k r k −1 .

Uma vez que a fórmula de recursão foi assumida como correta para r k −2 e r k −1 , elas podem ser expressas em termos das variáveis s e t correspondentes

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 a etapa k , conforme necessário

r k = s k a + t k b = ( s k −2 - q k s k −1 ) a + ( t k −2 - q k t k −1 ) b .

Método Matrix

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

pode ser escrito como um produto de matrizes quocientes 2 por 2 multiplicando um vetor de resto bidimensional

Deixe M representar o produto de todas as matrizes de quociente

Isso simplifica o algoritmo euclidiano para a forma

Para expressar g como uma soma linear de um e b , ambos os lados da equação pode ser multiplicado pelo inverso da matriz M . O determinante de M é igual a (−1) N +1 , pois é igual ao produto dos determinantes das matrizes quocientes, cada uma das quais é negativa. Uma vez que o determinante de M nunca é zero, o vetor dos restos finais pode ser resolvido usando o inverso de M

Uma vez que a equação superior dá

g = (−1) N +1 ( m 22 a - m 12 b ),

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

Lema de Euclides e fatoração única

A identidade de Bézout é essencial para muitas aplicações do algoritmo de Euclides, como a demonstração da fatoração única de números em fatores primos. Para ilustrar isto, suponhamos que um número L pode ser escrito como um produto de dois factores u e v , isto é, G  =  uv . Se outro número w também divide L, mas é coprime de u , então w deve dividir v , pelo seguinte argumento: Se o maior divisor comum de u e w for 1, então os inteiros s e t podem ser encontrados de modo que

1 = su + tw  .

pela identidade de Bézout. Multiplicando ambos os lados por v dá a relação

v = suv + twv = sL + twv  .

Como w divide os dois termos do lado direito, ele também deve dividir o lado esquerdo, v . Esse resultado é conhecido como lema de Euclides . Especificamente, se um número primo divide L , então deve dividir pelo menos um fator de L . Por outro lado, se um número w é coprime para cada uma das séries de números a 1 , a 2 , ..., a n , então w também é coprime de seu produto, a 1  ×  a 2  × ... ×  a n .

O lema de Euclides é suficiente para provar que todo número tem uma fatoração única em números primos. Para ver isso, suponha o contrário, que existem duas fatorações independentes de L em m e n fatores primos, respectivamente

L = p 1 p 2p m = q 1 q 2q n  .

Uma vez que cada primo p divide L por suposição, ele também deve dividir um dos fatores q ; como cada q também é primo, deve ser que p  =  q . A divisão iterativa pelos fatores p mostra que cada p tem uma contraparte igual q ; as duas fatorações principais são idênticas, exceto por sua ordem. A fatoração única de números em primos tem muitas aplicações em provas matemáticas, como mostrado abaixo.

Equações Diofantinas Lineares

"Uma linha diagonal que vai do canto superior esquerdo ao inferior direito. Quinze círculos são espaçados em intervalos regulares ao longo da linha. Os eixos das coordenadas xy perpendiculares têm sua origem no canto esquerdo inferior; a linha cruzou o eixo y no canto superior esquerdo e cruze o eixo x no canto inferior direito. "
Gráfico de uma equação diofantina linear , 9 x  + 12 y  = 483. As soluções são mostradas como círculos azuis.

Equações diofantinas são equações em que as soluções são restritas a inteiros; eles são nomeados após o matemático Alexandrino Diophantus do século III . Um típico linear equação Diophantine procura inteiros x e y tal que

ax + by = c

onde um , b e c são números inteiros dada. Isso pode ser escrito como uma equação para x na aritmética modular :

axc mod 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 tem solução. Ao dividir os dois lados por c / g , a equação pode ser reduzida à identidade de Bezout

sa + tb = g

onde s e t podem ser encontrados pelo algoritmo Euclidiano estendido . Isso fornece uma solução para a equação Diofantina, x 1  =  s ( c / g ) ey 1  =  t ( c / g ).

Em geral, uma equação diofantina linear não tem soluções ou tem um número infinito de soluções. Para encontrar o último, considere duas soluções, ( x 1y 1 ) e ( x 2y 2 ), onde

machado 1 + por 1 = c = machado 2 + por 2

ou equivalente

a ( x 1 - x 2 ) = b ( y 2 - y 1 ).

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

x = x 1 - bu / g
y = y 1 + au / g .

Ao permitir que u varie em todos os números inteiros possíveis, uma família infinita de soluções pode ser gerada a partir de uma única solução ( x 1y 1 ). Se as soluções devem ser inteiros positivos ( x  > 0,  y  > 0), apenas um número finito de soluções pode ser possível. Esta restrição nas 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; isso é impossível para um sistema de equações lineares quando as soluções podem ser qualquer número real (consulte Sistema subdeterminado ).

Inversos multiplicativos e o algoritmo RSA

Um campo 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 possuem suas propriedades usuais, como comutatividade , associatividade e distributividade . Um exemplo de um campo finito é o conjunto de 13 números {0, 1, 2, ..., 12} usando aritmética modular . Neste campo, o resultado de qualquer operação matemática (adição, subtração, multiplicação ou divisão) é reduzido módulo 13; ou seja, múltiplos de 13 são adicionados ou subtraídos até que o resultado seja colocado no intervalo de 0–12. Por exemplo, o resultado de 5 × 7 = 35 mod 13 = 9. Esses campos finitos podem ser definidos para qualquer primo p ; usando definições mais sofisticadas, eles também podem ser definidos para qualquer potência m de um primo p m . Os campos finitos são freqüentemente chamados de campos de Galois e são abreviados como GF ( p ) ou GF ( p m ).   

Em tal campo com m números, todo elemento diferente de zero a tem um único inverso multiplicativo modular , a −1 tal que aa −1  =  a −1 a  ≡ 1 mod  m . Este inverso pode ser encontrado resolvendo a equação de congruência ax  ≡ 1 mod  m , ou a equação Diofantina linear equivalente

machado + meu = 1.

Esta equação pode ser resolvida pelo algoritmo Euclidiano, conforme descrito acima . Encontrar inversos multiplicativos é uma etapa essencial no algoritmo RSA , amplamente utilizado no comércio eletrônico ; especificamente, a equação determina o número inteiro usado para descriptografar a mensagem. Embora o algoritmo RSA use anéis em vez de campos, o algoritmo euclidiano ainda pode ser usado para encontrar um inverso multiplicativo onde existe um. O algoritmo euclidiano também tem outras aplicações em códigos de correção de erros ; por exemplo, pode ser usado como uma alternativa ao algoritmo Berlekamp-Massey para decodificar códigos BCH e Reed-Solomon , que são baseados em campos de Galois.

Teorema do resto chinês

O algoritmo de Euclides também pode ser usado para resolver várias equações diofantinas lineares. Essas equações surgem no teorema do resto chinês , que descreve um novo método para representar um inteiro x . Em vez de representar um número inteiro por seus dígitos, ele pode ser representado por seus restos x i módulo um conjunto de N números de coprimos m i :

O objetivo é determinar x a partir de seus N remanescentes x i . A solução é combinar as várias equações em uma única equação diofantina linear com um módulo muito maior M que é o produto de todos os módulos individuais m i , e definir M i como

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 de modo que

Com esses números h i , qualquer inteiro x pode ser reconstruído a partir de seus remanescentes x i pela equação

Uma vez que esses números h i são os inversos multiplicativos de M i , eles podem ser encontrados usando o algoritmo de Euclides, conforme descrito na subseção anterior.

Árvore Stern-Brocot

O algoritmo euclidiano pode ser usado para organizar o conjunto de todos os números racionais positivos em uma árvore de busca binária infinita , chamada de árvore de Stern-Brocot . O número 1 (expresso como uma fração 1/1) é colocado na raiz da árvore, e a localização de qualquer outro número a / b pode ser encontrada calculando gcd ( a , b ) usando a forma original do algoritmo euclidiano , em que cada etapa substitui o maior dos dois números dados por sua diferença com o número menor (não seu restante), parando quando dois números iguais são alcançados. Uma etapa do algoritmo euclidiano que substitui o primeiro dos dois números corresponde a uma etapa na árvore de um nó para seu filho direito, e uma etapa que substitui o segundo dos dois números corresponde a uma etapa na árvore de um nó para seu filho esquerdo. A sequência de etapas construída desta forma não depende se a / b é fornecido em termos mais baixos e forma um caminho da raiz para um nó que contém o número a / b . 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 para a esquerda uma vez e depois para a direita duas vezes:

A árvore Stern-Brocot e as sequências Stern-Brocot de ordem i para i = 1, 2, 3, 4

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

Frações contínuas

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

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

A terceira equação pode ser usada para substituir o termo denominador r 1 / r 0 , resultando

A razão final dos restos r k / r k −1 sempre pode ser substituída usando a próxima equação da série, até a equação final. O resultado é uma fração contínua

No exemplo trabalhado acima , o mdc (1071, 462) foi calculado e os quocientes q k foram 2, 3 e 7, respectivamente. Portanto, a fração 1071/462 pode ser escrita

como pode ser confirmado por cálculo.

Algoritmos de fatoração

O cálculo de um divisor comum maior é um passo essencial em várias inteiro fatoração algoritmos, tais como o algoritmo de Pollard rho , o algoritmo de Shor , método fatoração de Dixon e o Lenstra curva elíptica fatoração . O algoritmo euclidiano pode ser usado para encontrar este GCD de forma eficiente. A fatoração de fração contínua usa frações contínuas, que são determinadas usando o algoritmo de Euclides.

Eficiência algorítmica

"Um conjunto de linhas coloridas irradiando para fora da origem de um sistema de coordenadas xy. Cada linha corresponde a um conjunto de pares de números que requerem o mesmo número de etapas no algoritmo euclidiano."
Número de etapas no algoritmo euclidiano para mdc ( x , y ). Os pontos mais claros (vermelho e amarelo) indicam relativamente poucos passos, enquanto os pontos mais escuros (violeta e azul) indicam mais passos. A maior área escura segue a linha y = Φx , onde Φ é a proporção áurea .

A eficiência computacional do algoritmo de Euclides foi estudada exaustivamente. Essa eficiência pode ser descrita pelo número de etapas de divisão que o algoritmo requer, multiplicado pelo gasto computacional de cada etapa. A primeira análise conhecida do algoritmo de Euclides deve-se a AAL 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 isso para v / 2 + 2. Mais tarde, em 1841, PJE Finck mostrou que o número de etapas de divisão é no máximo 2 log 2  v  + 1 e, portanto, o algoritmo de Euclides é executado no 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 etapas necessárias para a conclusão nunca é mais do que cinco vezes o número h dos dígitos de base 10 do número menor  b .

No modelo de custo uniforme (adequado para analisar a complexidade do cálculo do mdc em números que cabem em uma única palavra de máquina), cada etapa do algoritmo leva um tempo constante , e a análise de Lamé implica que o tempo total de execução também é O ( h ). No entanto, em um modelo de computação adequado para computação com números maiores, a despesa computacional de uma única computação restante no algoritmo pode ser tão grande quanto O ( h 2 ). Nesse caso, o tempo total de todas as etapas do algoritmo pode ser analisado por meio de uma série telescópica , mostrando que também é O ( h 2 ). Técnicas algorítmicas modernas baseadas no algoritmo de Schönhage-Strassen para multiplicação rápida de números inteiros podem ser usadas para acelerar isso, levando a algoritmos quasilineares para o GCD.

Número de etapas

O número de passos para calcular o GCD de dois números naturais, um e b , podem ser representados por T ( umb ). Se g é a GCD de um e b , em seguida, um  =  mg e b  =  ng por dois números coprimas m e n . Então

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

como pode ser visto dividindo todas as etapas no algoritmo euclidiano por g . Pelo mesmo argumento, o número de passos permanece o mesmo, se um e b são multiplicados por um factor comum W : T ( um , b ) = T ( WA , WB ). Portanto, o número de etapas T pode variar dramaticamente entre pares vizinhos de números, como T ( a , b ) e T ( ab  + 1), dependendo do tamanho dos dois GCDs.

A natureza recursiva do algoritmo Euclidiano dá outra equação

T ( a , b ) = 1 + T ( b , r 0 ) = 2 + T ( r 0 , r 1 ) = ... = N + T ( r N −2 , r N −1 ) = N + 1

onde T ( x , 0) = 0 por suposição.

Pior caso

Se o algoritmo de Euclides requer N passos para um par de números naturais um  >  b  > 0, os menores valores de um e b para o qual este é verdadeiro são os números de Fibonacci F N 2 e F N 1 , respectivamente. Mais precisamente, se o algoritmo euclidiano requer N passos para o par a  >  b , então  temos a ≥  F N +2 e b  ≥  F N +1 . Isso pode ser mostrado por indução . Se N  = 1, b divide a sem resto; os menores números naturais para os quais isso é verdadeiro são b  = 1 e a  = 2, que são F 2 e F 3 , respectivamente. Agora suponha que o resultado seja válido para todos os valores de N até M  - 1. O primeiro passo do algoritmo M -step é a  =  q 0 b  +  r 0 , e o algoritmo Euclidiano requer M  - 1 passos para o par b  >  r 0 . Por hipótese de indução, tem uma b  ≥  F H 1 e r 0  ≥  F H . Portanto, a  =  q 0 b  +  r 0  ≥  b  +  r 0  ≥  F M +1  +  F M  =  F M +2 , que é a desigualdade desejada. Essa 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.

Este resultado é suficiente para mostrar que o número de passos no algoritmo de Euclides nunca pode ser mais do que cinco vezes o número de seus dígitos (base 10). Pois se o algoritmo requer N passos, então b é maior ou igual a F N +1 que por sua vez é maior ou igual a φ N −1 , onde φ é a razão áurea . Dado que b  ≥  φ N −1 , então N  - 1 ≤ log φ b . Como log 10 φ  > 1/5, ( N  - 1) / 5 <log 10 φ  log φ b  = log 10 b . Assim, N  ≤ 5 log 10 b . Assim, o algoritmo euclidiano sempre precisa de menos do que O ( h ) divisões, onde h é o número de dígitos do menor número b .

Média

O número médio de passos dados pelo algoritmo euclidiano foi definido de três maneiras diferentes. A primeira definição é o tempo médio T ( a ) necessário para calcular o GCD de um determinado número a e de um número natural menor b escolhido com igual probabilidade dos inteiros 0 a a  - 1

No entanto, como T ( ab ) flutua dramaticamente com o GCD dos dois números, a função média T ( a ) é igualmente "ruidosa".

Para reduzir esse ruído, uma segunda média τ ( a ) é tomada sobre todos os números coprime com um

Existem φ ( a ) inteiros de coprime menores que a , onde φ é a função totiente de Euler . Esta média tau cresce suavemente com um

sendo o erro residual da ordem a - (1/6) + ε , onde ε é infinitesimal . A constante C ( Constante de Porter ) nesta fórmula é igual a

onde γ é a constante de Euler-Mascheroni e ζ 'é a derivada da função zeta de Riemann . O coeficiente líder (12 / π 2 ) ln 2 foi determinado por dois métodos independentes.

Uma vez que a primeira média pode ser calculada a partir da média tau somando os divisores d de  um

pode ser aproximado pela fórmula

onde Λ ( d ) é a função Mangoldt .

Uma terceira média Y ( n ) é definida como o número médio de etapas necessárias quando a e b são escolhidos aleatoriamente (com distribuição uniforme) de 1 a n

Substituir a fórmula aproximada para T ( a ) nesta equação produz uma estimativa para Y ( n )

Despesa computacional por etapa

Em cada etapa k do algoritmo euclidiano, o quociente q k e o restante r k são calculados para um dado par de inteiros r k −2 e r k −1

r k −2 = q k r k −1 + r k .

O gasto computacional por etapa está associado principalmente com a descoberta de q k , uma vez que o restante 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 gasto computacional de dividir os números de h- bits é igual a O ( h ( +1)), onde é o comprimento do quociente.

Para comparação, o algoritmo baseado em subtração original de Euclides pode ser muito mais lento. Uma única divisão inteira é equivalente ao quociente q número de subtrações. Se o rácio de um e b é muito grande, o quociente é grande e vai ser obrigado muitos subtracções. Por outro lado, foi mostrado que os quocientes são muito provavelmente 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 aproximadamente 41,5%, 17,0%, 9,3% e 5,9%, respectivamente. Uma vez que a operação de subtração é mais rápida do que a divisão, particularmente para grandes números, o algoritmo de Euclides baseado em subtração é competitivo com a versão baseada em divisão. Isso é explorado na versão binária do algoritmo de Euclides.

Combinar o número estimado de etapas com o gasto computacional estimado por etapa mostra que o algoritmo de Euclides cresce quadraticamente ( h 2 ) com o número médio de dígitos h nos dois números iniciais a e b . Suponha que h 0 , h 1 , ..., h N −1 represente o número de dígitos nos restos sucessivos r 0r 1 , ...,  r N −1 . Uma vez que o número de etapas N cresce linearmente com h , o tempo de execução é limitado por

Métodos alternativos

O algoritmo de Euclides é amplamente utilizado na prática, principalmente para pequenos números, devido à sua simplicidade. Para comparação, a eficiência das alternativas ao algoritmo de Euclides pode ser determinada.

Uma abordagem ineficiente para encontrar o GCD de dois números naturais a e b é calcular todos os seus divisores comuns; o GCD é então o maior divisor comum. Os divisores comuns podem ser encontrados dividindo ambos os números por inteiros sucessivos de 2 ao número menor b . O número de etapas desta abordagem cresce linearmente com b , ou exponencialmente no número de dígitos. Outra abordagem ineficiente é encontrar os fatores primos de um ou de ambos os números. Conforme observado acima , o GCD é igual ao produto dos fatores primos compartilhados pelos dois números a e b . Os métodos atuais para fatoração primária também são ineficientes; muitos sistemas de criptografia modernos contam até com essa ineficiência.

O algoritmo binário GCD é uma alternativa eficiente que substitui a divisão por operações mais rápidas, explorando a representação binária usada por computadores. No entanto, essa alternativa também escala como O ( h ²) . Geralmente é mais rápido do que o algoritmo euclidiano em computadores reais, embora seja escalonado da mesma maneira. Eficiência adicional pode ser obtida examinando apenas os dígitos iniciais dos dois números a e b . O algoritmo binário pode ser estendido a outras bases ( algoritmos k -ary), com aumentos de até cinco vezes na velocidade. O algoritmo GCD de Lehmer usa o mesmo princípio geral que o algoritmo binário para acelerar os cálculos GCD em bases arbitrárias.

Uma abordagem recursiva para muito grandes números inteiros (com mais de 25.000 dígitos) conduz a quasilineares algoritmos inteiro GCD, tais como aqueles de Schönhage, e Stehle e Zimmermann. Esses algoritmos exploram a forma de matriz 2 × 2 do algoritmo euclidiano dado acima . Esses métodos quase lineares geralmente são escalados como O ( h (log h ) 2 (log log h )).

Generalizações

Embora o algoritmo euclidiano seja usado para encontrar o maior divisor comum de dois números naturais (inteiros positivos), ele pode ser generalizado para os números reais e para outros objetos matemáticos, como polinômios , inteiros quadráticos e quatérnios de Hurwitz . Nos últimos casos, o algoritmo euclidiano é usado para demonstrar a propriedade crucial da fatoração única, isto é, que tais números podem ser fatorados exclusivamente em elementos irredutíveis , as contrapartes 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 , conforme descrito por Euclides no Livro 10 de seus Elementos . O objectivo do algoritmo consiste em identificar um número real g de tal modo que duas dadas números reais, uma e b , são múltiplos inteiros do mesmo: um = mg e b = ng , onde m e n são números inteiros . Essa identificação é equivalente a encontrar uma relação inteira entre os números reais a e b ; ou seja, ele determina os inteiros s e t tais que sa + tb = 0 . Euclides usa esse algoritmo para tratar a questão dos comprimentos incomensuráveis .

O algoritmo euclidiano de número real difere de sua contraparte inteira em dois aspectos. Primeiro, os restantes r k são números reais, embora os quocientes q k sejam inteiros como antes. Em segundo lugar, não é garantido que o algoritmo termine em um número finito N de etapas. Em caso afirmativo, a fração a / b é um número racional, ou seja, a proporção de dois inteiros

e pode ser escrito como uma fração contínua finita [ q 0 ; q 1 , q 2 , ..., 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 0 ; q 1 , q 2 ,…] . Exemplos de frações contínuas infinitas são a razão áurea φ = [1; 1, 1, ...] e a raiz quadrada de dois , 2 = [1; 2, 2, ...] . É improvável que o algoritmo pare, já que quase todas as razões a / b de dois números reais são irracionais.

Uma fração contínua infinita pode ser truncada em uma etapa k [ q 0 ; Q 1 , Q 2 , ..., q k ] , para se obter uma aproximação a um / b que melhora à medida que k é aumentado. A aproximação é descrita por convergentes m k / n k ; o numerador e denominadores são coprimes e obedecem à relação de recorrência

onde m −1 = n −2 = 1 e m −2 = n −1 = 0 são os valores iniciais da recursão. O convergente m k / n k é a melhor aproximação de número racional para a / b com denominador n k :

Polinômios

Polinômios em uma ú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 inteiros. O maior divisor comum polinômio g ( x ) de dois polinômios a ( x ) e b ( x ) é definido como o produto de seus polinômios irredutíveis compartilhados, que podem ser identificados usando o algoritmo euclidiano. O procedimento básico é semelhante ao dos inteiros. Em cada etapa k , um polinômio quociente q k ( x ) e um polinômio restante r k ( x ) são identificados para satisfazer a equação recursiva

onde r −2 ( x ) = a ( x ) e r −1 ( x ) = b ( x ) . Cada quociente polinomial é escolhido de modo que cada resto seja zero ou tenha um grau menor que o grau de seu predecessor: deg [ r k ( x )] <deg [ r k −1 ( x )] . Como o grau é um número inteiro não negativo e diminui a cada etapa, o algoritmo euclidiano é concluído em um número finito de etapas. O último resto diferente de zero é o maior divisor comum dos dois polinômios originais, a ( x ) e b ( x ) .

Por exemplo, considere os dois polinômios quárticos a seguir, em que cada um fator em dois polinômios quadráticos

Dividindo a ( x ) por b ( x ) resulta um resto r 0 ( x ) = x 3 + (2/3) x 2 + (5/3) x - (2/3) . Na próxima etapa, b ( x ) é dividido por r 0 ( x ) resultando em um resto r 1 ( x ) = x 2 + x + 2 . Finalmente, dividir r 0 ( x ) por r 1 ( x ) resulta em um resto zero, indicando que r 1 ( x ) é o maior divisor polinômio comum de a ( x ) e b ( x ) , consistente com sua fatoração.

Muitas das aplicações descritas acima para inteiros são transportadas para polinômios. O algoritmo Euclidiano pode ser usado para resolver equações diofantinas lineares e problemas de restos chineses para polinômios; frações contínuas de polinômios também podem ser definidas.

O algoritmo euclidiano polinomial tem outras aplicações, como cadeias de Sturm , um método para contar os zeros de um polinômio que se encontram dentro de um determinado intervalo real . Isso, por sua vez, tem aplicações em várias áreas, como o critério de estabilidade de Routh-Hurwitz na teoria de controle .

Finalmente, os coeficientes dos polinômios não precisam ser extraídos de inteiros, números reais ou mesmo de números complexos. Por exemplo, os coeficientes podem ser extraídos de um campo geral, como os campos finitos GF ( p ) descritos acima. As conclusões correspondentes sobre o algoritmo euclidiano e suas aplicações valem até mesmo para tais polinômios.

Inteiros gaussianos

"Um conjunto de pontos dentro de um círculo. O padrão de pontos tem simetria quádrupla, ou seja, rotações de 90 graus deixam o padrão inalterado. O padrão também pode ser espelhado em cerca de quatro linhas que passam pelo centro do círculo: a vertical e a horizontal eixos e as duas linhas diagonais em ± 45 graus. "
Distribuição de primos gaussianos u + vi no plano complexo, com normas u 2 + v 2 menores que 500

Os inteiros de Gauss são números complexos da forma α = u + VI , onde u e v são comuns inteiros e i é a raiz quadrada de um negativo . Ao definir um análogo do algoritmo euclidiano, os inteiros gaussianos podem ser considerados fatoráveis ​​de maneira única, pelo argumento acima . Esta fatoração única é útil em muitas aplicações, como derivar todos os triplos pitagóricos ou provar o teorema de Fermat em somas de dois quadrados . Em geral, o algoritmo euclidiano é conveniente em tais aplicações, mas não essencial; por exemplo, os teoremas muitas vezes podem ser provados por outros argumentos.

O algoritmo euclidiano desenvolvido para dois inteiros gaussianos α e β é quase o mesmo que para inteiros ordinários, mas difere em dois aspectos. Como antes, a tarefa em cada etapa k é identificar um quociente q k e um resto r k de modo que

onde r k −2 = α , onde r k −1 = β , e onde todo resto é estritamente menor que seu predecessor: | r k | <| r k −1 | . A primeira diferença é que os quocientes e os remanescentes são, eles próprios, inteiros gaussianos e, portanto, são números complexos . Os quocientes q k são geralmente encontrados arredondando as partes reais e complexas da razão exata (como o número complexo α / β ) para os números inteiros mais próximos. A segunda diferença reside na necessidade de definir como um resto complexo pode ser "menor" do que outro. Para fazer isso, uma função norma f ( u + vi ) = u 2 + v 2 é definida, a qual converte todo inteiro gaussiano u + vi em um inteiro ordinário. Após cada etapa k do algoritmo euclidiano, a norma do resto f ( r k ) é menor que a norma do resto anterior, f ( r k −1 ) . Como a norma é um inteiro não negativo e diminui a cada passo, o algoritmo euclidiano para inteiros gaussianos termina em um número finito de passos. O resto diferente de zero final é mdc ( α , β ) , o inteiro gaussiano de maior norma que divide α e β ; é único até a multiplicação por uma unidade, ± 1 ou ± i .

Muitas das outras aplicações do algoritmo euclidiano são transferidas para inteiros gaussianos. Por exemplo, pode ser usado para resolver equações diofantinas lineares e problemas de restos chineses para inteiros gaussianos; frações contínuas de inteiros gaussianos também podem ser definidas.

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 euclidiano generalizado puder ser executado sobre eles. As duas operações desse anel não precisam ser a adição e a multiplicação da aritmética comum; em vez disso, eles podem ser mais gerais, como as operações de um grupo matemático ou monóide . No entanto, essas operações gerais devem respeitar muitas das leis que regem a aritmética comum, como comutatividade , associatividade e distributividade .

O algoritmo de Euclides generalizada requer uma função euclidiana , ou seja, um mapeamento f a partir de R para o conjunto de inteiros não negativos de tal forma que, para qualquer dos dois elementos diferentes de zero um e b em R , existem q e r em R tal que um = QB + r e f ( r ) < f ( b ) . Exemplos de tais mapeamentos são o valor absoluto para inteiros, o grau para polinômios univariados e a norma para inteiros gaussianos acima . O princípio básico é que cada etapa do algoritmo reduz f inexoravelmente; portanto, se f pode ser reduzido apenas um número finito de vezes, o algoritmo deve parar em um número finito de etapas. Este princípio se baseia na propriedade de boa ordenação dos inteiros não negativos, que afirma que todo conjunto não vazio de inteiros não negativos tem um membro menor.

O teorema fundamental da aritmética se aplica a qualquer domínio euclidiano: qualquer número de um domínio euclidiano pode ser fatorado exclusivamente em elementos irredutíveis . Qualquer domínio euclidiano é um domínio de fatoração único (UFD), embora o inverso não seja verdadeiro. Os domínios euclidianos e os UFDs são subclasses dos domínios GCD , domínios nos quais sempre existe um maior divisor comum de dois números. Em outras palavras, um maior divisor comum pode existir (para todos os pares de elementos em um domínio), embora não seja possível encontrá-lo usando um algoritmo euclidiano. Um domínio euclidiano é sempre um domínio ideal principal (PID), um domínio integral em que todo ideal é um ideal principal . Novamente, o inverso não é verdadeiro: nem todo PID é um domínio euclidiano.

A fatoração única de 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 triplos pitagóricos e para provar o teorema de Fermat nas somas de dois quadrados . A fatoração única também foi um elemento chave em uma 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, baseado em uma sugestão de Joseph Liouville . Abordagem é coxo necessário Fatorização única de números da forma x + ωy , onde x e y são números inteiros, e ω = e 2 / n é um n ° de raiz de 1, isto é, ω n = 1 . Embora essa abordagem seja bem-sucedida para alguns valores de n (como n = 3 , os inteiros de Eisenstein ), em geral, esses números não são fatorados exclusivamente. Essa falha de fatoração única em alguns campos ciclotômicos levou Ernst Kummer ao conceito de números ideais e, mais tarde, Richard Dedekind aos ideais .

Fatoração única de inteiros quadráticos

"Um conjunto de pontos dentro de um círculo. O padrão dos pontos tem simetria sêxtupla, ou seja, as rotações de 60 graus deixam o padrão inalterado. O padrão também pode ser espelhado em cerca de seis linhas que passam pelo centro do círculo: a vertical e a horizontal eixos e as quatro linhas diagonais em ± 30 e ± 60 graus. "
Distribuição de Eisenstein primes u + no plano complexo, com normas menores que 500. O número ω é uma raiz cúbica de 1 .

Os anéis inteiros quadráticos são úteis para ilustrar os domínios euclidianos. Os inteiros quadráticos são generalizações dos inteiros gaussianos em que a unidade imaginária i é substituída por um número ω . Assim, eles têm a forma de u + , onde u e v são números 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

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

Se a função f corresponde a uma função norma , como aquela usada para ordenar os inteiros gaussianos acima , então o domínio é conhecido como euclidiano norma . Os anéis euclidianos de norma 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. Os casos D = −1 e D = −3 produzem os inteiros Gaussianos e inteiros de Eisenstein , respectivamente.

Se f for permitido ser qualquer função euclidiana, então a lista de valores possíveis de D para os quais o domínio é euclidiano ainda não é conhecida. O primeiro exemplo de um domínio euclidiano que não era norma-euclidiano (com D = 69 ) foi publicado em 1994. Em 1973, Weinberger provou que um anel inteiro quadrático com D > 0 é euclidiano se, e somente se, for um principal domínio ideal , desde que a hipótese generalizada de Riemann seja válida.

Anéis não comutativos

O algoritmo euclidiano pode ser aplicado a alguns anéis não comutativos, como o conjunto de quatérnios de Hurwitz . Sejam α e β dois elementos desse anel. Eles têm um divisor direito comum δ se α = ξδ e β = ηδ para alguma escolha de ξ e η no anel. Da mesma forma, eles têm um divisor esquerdo comum se α = e β = para alguma escolha de ξ e η no anel. Como a multiplicação não é comutativa, existem duas versões do algoritmo euclidiano, uma para os divisores à direita e outra à esquerda. Escolhendo os divisores corretos, o primeiro passo para encontrar o mdc ( α , β ) pelo algoritmo euclidiano pode ser escrito

onde ψ 0 representa o quociente e ρ 0 o resto. Esta equação mostra que qualquer divisor comum à direita de α e β é igualmente um divisor comum do resto ρ 0 . A equação análoga para os divisores esquerdos seria

Com qualquer uma das opções, o processo é repetido como acima até que o maior divisor comum direito ou esquerdo seja identificado. Como no domínio euclidiano, o "tamanho" do resto ρ 0 (formalmente, sua norma ) deve ser estritamente menor que β , e deve haver apenas um número finito de tamanhos possíveis para ρ 0 , de modo que o algoritmo é garantido terminar.

A maioria dos resultados do GCD são transferidos para números não comutativos. Por exemplo, a identidade de Bézout afirma que o mdc correto ( α , β ) pode ser expresso como uma combinação linear de α e β . Em outras palavras, existem números σ e τ tais que

A identidade análoga para o GCD esquerdo é quase a mesma:

A identidade de Bézout pode ser usada para resolver as equações diofantinas. Por exemplo, uma das provas padrão do teorema de quatro quadrados de Lagrange , de que todo número inteiro positivo pode ser representado como uma soma de quatro quadrados, é baseada em GCDs de quatérnio dessa maneira.

Veja também

  • Ritmo euclidiano , um método para usar o algoritmo euclidiano para gerar ritmos musicais

Notas

Referências

Bibliografia

links externos