Algoritmo de Euclides

Em matemática, o algoritmo de Euclides^[a] é um método simples e eficiente de encontrar o máximo divisor comum entre dois números inteiros diferentes de zero. É um dos algoritmos mais antigos, conhecido desde que surgiu nos Livros VII e X da obra Elementos de Euclides^[1] por volta de 300 a.C.. O algoritmo não exige qualquer fatoração.

O MDC de dois números inteiros é o maior número inteiro que divide ambos sem deixar resto. O algoritmo de Euclides é baseado no princípio de que o MDC não muda se o menor número for subtraído ao maior. Por exemplo, 21 é o MDC de 252 e 105 (252 = 21 × 12; 105 = 21 × 5); já que 252 − 105 = 147, o MDC de 147 e 105 é também 21. Como o maior dos dois números é reduzido, a repetição deste processo irá gerar sucessivamente números menores, até convergir em zero. Nesse momento, o MDC é o outro número inteiro, maior que zero. Ao reverter os passos do algoritmo de Euclides, o MDC pode ser expresso como soma dos dois números originais, cada um multiplicado por um número inteiro positivo ou negativo, por exemplo: 21 = 5 × 105 + (−2) × 252. Esta importante propriedade é denominada identidade de Bézout.

A mais antiga descrição que se conhece do método usado no algoritmo de Euclides é da sua obra Elementos (c. 300 a.C.), o que o torna um dos algoritmos numéricos mais antigos ainda em uso corrente. O algoritmo original foi descrito apenas para números naturais e comprimentos geométricos, mas foi generalizado no século XIX para outras classes de números como os inteiros gaussianos e polinómios de uma variável. Isto conduziu a noções da moderna álgebra abstrata tais como os domínios euclidianos. O algoritmo de Euclides foi ainda generalizado mais a outras estruturas matemáticas, como os nós e polinómios multivariados.

O algoritmo tem muitas aplicações teóricas e práticas. Ele pode ser usado para gerar quase todas as importantes aplicações tradicionais usados em diferentes culturas em todo o mundo.^[2] Ele é um elemento-chave dos algoritmos RSA, um método de criptografia de chave pública usado no comércio eletrônico. Ele é usado para resolver as equações de diofantina, tal como na descoberta de números que seja safistatório em múltiplas congruências (teorema chinês do resto) ou inverso multiplicativo de um número finito. Ele pode também ser usado para construir frações contínuas, em um método para o teorema de Sturm para descobrir raízes reais em um polinômio, e em vários algoritmos modernos em fatoração de inteiros. Finalmente, é uma ferramenta básica para obter na teoria dos números modernas, tal como teorema de Fermat-Lagrange e no teorema fundamental da aritmética.

História do desenvolvimento do algoritmo

Esta figura na obra "Escola de Atenas" de Rafael retrata muito provavelmente Euclides.

O algoritmo de Euclides é um dos mais antigos algoritmos ainda em uso.^[3] Surge na sua obra Os Elementos (c. 300 a.C.), especificamente nos Livros 7 (Proposições 1–2) e 10 (Proposições 2–3). No Livro 7, o algoritmo é formulado para inteiros, enquanto no Livro 10 é formulado para comprimentos de segmentos lineares (dir-se-ia hoje que estaria formulado para números reais). Comprimentos, áreas e volumes, representados como números reais hoje em dia, não são medidos nas mesmas unidades, e não existe uma unidade natural de comprimento, área ou volume. O conceito de número real era desconhecido à época de Euclides. O último algoritmo é geométrico. O MDC de dois comprimentos a e b corresponde ao maior comprimento g que mede propriamente a e b; por outras palavras, os comprimentos a e b são o resultado da multiplicação do comprimento g por números inteiros.

O algoritmo não foi provavelmente concebido por Euclides, que compilou resultados de matemáticos anteriores nos seus Elementos.^[4]^[5] O matemático e historiador Bartel van der Waerden sugere que o Livro VII provém de um texto em teoria dos números escrito por matemáticos da escola de Pitágoras.^[6] O algoritmo era provavelmente conhecido por Eudoxo de Cnido (cerca de 375 a.C.).^[3]^[7] Poderá ainda ser anterior a Eudoxo,^[8]^[9] a julgar pelo uso do termo técnico ἀνθυφαίρεσις (anthyphairesis, subtração recíproca) em trabalhos de Euclides e Aristóteles.^[10]

Séculos mais tarde, o algoritmo de Euclides terá sido reinventado de forma independente na Índia e China,^[11] sobretudo para resolver equações diofantinas que surgiram relacionadas com a Astronomia e a elaboração de calendários precisos. No final do século V, o matemático indiano e astrónomo Aryabhata descreveu o algoritmo como o "pulverizador",^[12] por causa da sua eficácia a resolver equações diofantinas.^[13] Embora um caso especial do teorema chinês do resto já fora descrito pelo matemático e astrónomo chinês Sun Tzu,^[14] a solução geral foi publicada por Ch’in Chiu-Shao na sua obra de 1247 chamada Shushu Jiuzhang (數書九章 Tratado Matemático em Nove Partes).^[15] O algoritmo de Euclides foi descrito pela primeira vez na Europa na segunda edição de Problèmes plaisants et délectables (Problemas aprazíveis e deleitáveis, 1624) de Bachet de Méziriac .^[12] Na Europa, era usado para resolver equações diofantinas e desenvolvimento de frações contínuas. O algoritmo de Euclides estendido foi publicado pelo matemático inglês Nicholas Saunderson, que o atribuiu a Roger Cotes como método para calcular frações contínuas de forma eficiente.^[16]

Descrição do algoritmo

Definição do algoritmo

A ideia principal no Algoritmo de Euclides é que o MDC pode ser calculado recursivamente, usando o resto da divisão como entrada para o próximo passo, o que é baseado na seguinte propriedade do MDC:

$MDC(a,b)=MDC(b,r)$

onde $r$ é o resto da divisão de $a$ por $b$ .

Isso quer dizer que o resto da divisão em uma chamada do algoritmo será usado como entrada para a próxima chamada.

Sabemos que esse resto é calculado da seguinte forma: $r=a-bq$ , onde $q={\frac {a}{b}}$ é uma divisão inteira.

Desta forma, podemos substituir as variáveis para obter uma sequência: usando $a=r_{k-1}$ , $b=r_{k}$ e $r=r_{k+1}$ , temos a seguinte sequência:

$r_{k+1}=r_{k-1}-r_{k}q$

que nos diz que para calcular o próximo resto, basta multiplicar o resto atual por $q={\frac {r_{k-1}}{r_{k}}}$ e depois subtrair do resto anterior.

Quando o próximo resto for igual a zero, o algoritmo termina a execução e o resto atual ( $r_{k}$ ) é o máximo divisor comum.

A partir dessas observações, podemos facilmente derivar uma versão completa do algoritmo:

MDC (a, b)

  if (b == 0)
      return a
  else
      return MDC(b, a % b)

Desta versão recursiva, é fácil derivar a versão iterativa: é necessário apenas observar que a condição de parada $b=0$ e que na chamada subsequente do algoritmo, o valor de $a$ é o valor antigo de $b$ e o valor do novo $b$ é o valor do resto.

MDC(a, b)

   while (b != 0)
       r = a % b
       a = b
       b = r
   return a;

Versão original (geométrica)

Representação do número de passos necessários no algoritmo de Euclides.

Na concepção grega da matemática, os números eram entendidos como magnitudes geométricas. Um tema recorrente na geometria grega era o da comensurabilidade de dois segmentos: dois segmentos (números) AB e CD são comensuráveis quando existe um terceiro segmento PQ que cabe exactamente um número inteiro de vezes nos primeiros dois, ou seja, PQ «mede» (mensura: medida) os segmentos AB e CD.

Nem todos os pares de segmentos são comensuráveis, como observaram os pitagóricos quando estabeleceram que ${\sqrt {2}}$ não é um número racional, mas no caso de dois segmentos comensuráveis pretende-se determinar a maior medida comum possível.

Euclides descreveu na proposição VII.2 dos seus Elementos um método que permite determinar a maior medida comum de dois números (segmentos) que não sejam primos entre si, embora na época tal método se explicasse em termos geométricos, o que se ilustra na transcrição seguinte:

Para encontrar a máxima medida comum de dois números que não sejam primos entre si.

Sejam AB e CD os dois números que não são primos entre si. É necessário então encontrar a máxima medida comum de AB e CD.
Se CD mede AB então é uma medida comum já que CD se mede a si mesmo. É manifesto que também é a maior medida pois nada maior que CD pode medir CD. Mas se CD não mede AB então algum número restará de AB e CD, o menor sendo continuamente resto do maior e que medirá o número que o precede. Porque uma unidade não ficará pois se assim não for, AB e CD serão primos entre si [Prop. VII.1], o que é contrário ao que se supôs.
Portanto, ficará algum número que medirá o número que o precede. E seja CD a medir BE deixando EA menor que si mesmo e seja EA medindo DF deixando FC menor que si mesmo e seja FC medida de AE. Então, como FC mede AE e AE mede DF, FC será então medida de DF. E também se mede a si mesmo. Portanto também medirá todo o segmento CD. e CD mede BE. Então CF mede BE e também mede EA. Assim mede todo o segmento BA e também mede CD. Isto é, CF mede tanto AB como CD, pelo que é uma medida comum de AB e CD.
Afirmo que também é a maior medida comum possível porque se não o fosse, então um número maior que CF mede os números AB e CD. Seja este G. Dado que G mede CD e CD mede BE, G também mede BE. Além disso, mede todo o segmento BA pelo que mede também o resíduo AE. E AE mede DF pelo que G também mede DF. Mede ainda todo o segmento DC pelo que mede também o resíduo CF, ou seja, o maior mede o menor, o que é impossível.
Portanto, nenhum número maior que CF pode medir os números AB e CD. Então CF é a maior medida comum de AB e CD, o que era o que se queria demonstrar.
— Euclides. Elementos VII.2

Numa linguagem mais moderna, o algoritmo poderia ser descrito da seguinte forma:

Dados dois segmentos AB e CD (com AB>CD), retira-se CD de AB tantas vezes quanto possível. Se não houver resto, então CD é a máxima medida comum.
Se se obtém um resto EF, este é menor que CD e podemos repetir o processo: retira-se EF tantas vezes quanto possível de CD. Se no final não restar nada, EF é a medida comum. No caso contrário obtém-se um novo resíduo GH menor que EF.
O processo repete-se até não haver nenhum resto. O último resto obtido é a maior medida comum.

O facto de os segmentos serem comesuráveis é a chave para assegurar que o processo termina sempre, como se prova de seguida.

Demonstração da terminação e exatidão do algoritmo

A própria definição da série $(a_{n})$ por divisão euclidiana mostra que, para qualquer $n$ tal que $a_{n+1}$ é não nulo, existe um inteiro $q_{n+2}$ tal que : $a_{n}=q_{n+2}\times a_{n+1}+a_{n+2}$

e ainda $0\leq a_{n+2}<a_{n+1}.$ A série de inteiros naturais $(a_{n})$ é portanto estritamente decrescente, e atingirá o valor $0$ num número finito de passos. A existência de um último resto não nulo está assim estabelecida.

Seja $N+1$ o índice deste último resto não nulo. Para mostrar que $a_{N+1}$ é o MDC procurado, note-se que a relação anterior se escreve como $a_{N}=q_{N+2}\times a_{N+1},$ o que mostra que $a_{N+1}$ divide $a_{N}.$ Tomando $a_{N-1}=q_{N+1}\times a_{N}+a_{N+1},$ deduz-se que $a_{N+1}$ divide também $a_{N-1};$ também, e por recorrência, note-se que $a_{N+1}$ divide todos os termos da série $a_{n};$ em particular os primeiros termos $a$ e $b.$ $a_{N+1}$ é então um divisor comum de $a$ e $b.$ Reciprocamente, todo o divisor comum de a e b dividirá também $a_{2}=a-q_{2}\times b,$ e de novo por recorrência, dividirá todos os termos da série $(a_{n});$ em particular $a_{N+1}.$

$a_{N+1}$ é então um divisor comum de a e b que é divisível por todo e qualquer divisor comum: é assim o MDC.

Exemplo

Tomemos os números 348 e 156:

348	156
-312 36 ≠ 0	2

Como o resto não é zero, substituímos o dividendo e o divisor:

156	36
-144 12 ≠ 0	4

Como o resto não é zero, substituímos o dividendo e o divisor:

36	12
-36 0	3

quociente	2	4	3
348	156	36	12
resto	36	12	0

Portanto, o máximo divisor comum dos inteiros 348 e 156 é 12.

Ver também

Wikilivros

O wikilivro Teoria de números tem uma página sobre Algoritmo de Euclides

Algoritmo de Euclides estendido

Bibliografia recomendada

COUTINHO, Severino Coullier. Números inteiros e criptografia RSA. Rio de Janeiro: IMPA, 2005. 226 p. ISBN 85-244-0124-9
MILIES, Francisco César Polcino; COELHO, Sônia Pitta. Números: Uma introdução à Matemática. 3.ed. São Paulo: Editora da Universidade de São Paulo, 2003. ISBN 85-314-0458-4

Referências

↑ Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications
↑ Toussaint, Godfried, July 31 to August 3, 2005, «The Euclidean algorithm generates traditional musical rhythms» (PDF), Banff, Alberta, Canada, Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science: 47–56
↑ ^a ^b Knuth, p. 318.
↑ Weil A (1983). Number Theory. Boston: Birkhäuser. pp. 4–6. ISBN 0-8176-3141-0
↑ Jones A (1994). «Greek mathematics to AD 300». Companion encyclopedia of the history and philosophy of the mathematical sciences. Nova Iorque: Routledge. pp. 46–48. ISBN 0-415-09238-8
↑ van der Waerden BL (1954). Science Awakening. Col: trad. Arnold Dresden. Groningen: P. Noordhoff Ltd. pp. 114–115
↑ von Fritz K (1945). «The Discovery of Incommensurability by Hippasus of Metapontum». Ann. Math. 46: 242–264. doi:10.2307/1969021
↑ Heath TL (1949). Mathematics in Aristotle. [S.l.]: Oxford Press. pp. 80–83
↑ David Fowler (1987). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. pp. 31–66. ISBN 0-19-853912-6
↑ Becker O (1933). «Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid». Quellen und Studien zur Geschichte der Mathematik B. 2: 311–333
↑ Stillwell, p. 31.
↑ ^a ^b Tattersall, p. 70.
↑ Rosen, pp. 86–87.
↑ Ore, pp. 247–248.
↑ Tattersall, pp. 72, 184–185.
↑ Tattersall, pp. 72–76.

[1] Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, Dover Publications

[2] Toussaint, Godfried, July 31 to August 3, 2005, «The Euclidean algorithm generates traditional musical rhythms» (PDF), Banff, Alberta, Canada, Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science: 47–56

[autogenerated2-3] Knuth, p. 318.

[Weil_1983-4] Weil A (1983). Number Theory. Boston: Birkhäuser. pp. 4–6. ISBN 0-8176-3141-0

[Jones_1994-5] Jones A (1994). «Greek mathematics to AD 300». Companion encyclopedia of the history and philosophy of the mathematical sciences. Nova Iorque: Routledge. pp. 46–48. ISBN 0-415-09238-8

[van_der_Waerden_1954-6] van der Waerden BL (1954). Science Awakening. Col: trad. Arnold Dresden. Groningen: P. Noordhoff Ltd. pp. 114–115

[7] von Fritz K (1945). «The Discovery of Incommensurability by Hippasus of Metapontum». Ann. Math. 46: 242–264. doi:10.2307/1969021

[8] Heath TL (1949). Mathematics in Aristotle. [S.l.]: Oxford Press. pp. 80–83

[9] David Fowler (1987). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. pp. 31–66. ISBN 0-19-853912-6

[10] Becker O (1933). «Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid». Quellen und Studien zur Geschichte der Mathematik B. 2: 311–333

[11] Stillwell, p. 31.

[autogenerated1-12] Tattersall, p. 70.

[13] Rosen, pp. 86–87.

[14] Ore, pp. 247–248.

[15] Tattersall, pp. 72, 184–185.

[16] Tattersall, pp. 72–76.

[a]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]