Ver código fonte para Algoritmo de Euclides

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

Em [[matemática]], o '''algoritmo de Euclides'''{{Ref_label|a|a|none}} é um método simples e eficiente de encontrar o [[máximo divisor comum]] entre dois [[números inteiros]] diferentes de zero. É um dos [[algoritmo]]s mais antigos, conhecido desde que surgiu nos Livros&nbsp;VII e X da obra [[Elementos (livro)|Elementos]] de [[Euclides]]<ref>[[Thomas L. Heath]], ''The Thirteen Books of Euclid's Elements'', 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref> 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&nbsp;=&nbsp;21&nbsp;×&nbsp;12; 105&nbsp;=&nbsp;21&nbsp;×&nbsp;5); já que 252&nbsp;−&nbsp;105&nbsp;=&nbsp;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 [[algoritmo de Euclides estendido|reverter os passos do algoritmo de Euclides]], o MDC pode ser expresso como [[combinação linear|soma]] dos dois números originais, cada um multiplicado por um [[número inteiro]] positivo ou negativo, por exemplo: {{nowrap begin}}21 = 5 × 105 + (−2) × 252.{{nowrap end}} 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 [[algoritmo]]s numéricos mais antigos ainda em uso corrente. O algoritmo original foi descrito apenas para [[Número natural|números naturais]] e comprimentos geométricos, mas foi generalizado no século XIX para outras classes de números como os [[inteiro gaussiano|inteiros gaussianos]] e [[polinómio]]s de uma variável. Isto conduziu a noções da moderna [[álgebra abstrata]] tais como os [[domínio euclidiano|domínios euclidianos]]. O algoritmo de Euclides foi ainda generalizado mais a outras estruturas matemáticas, como os [[nó (matemática)|nós]] e [[polinómio multivariado|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.<ref>{{Citation |último =Toussaint |primeiro =Godfried |autorlink =Godfried Toussaint |url=http://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf |título=The Euclidean algorithm generates traditional musical rhythms |periódico=Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science |local=Banff, Alberta, Canada |outros=July 31 to August 3, 2005 |páginas=47–56 }}</ref> Ele é um elemento-chave dos [[RSA|algoritmos RSA]], um método de  [[criptografia de chave pública]] usado no [[comércio eletrônico]]. Ele é usado para resolver as [[equação diofantina|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ção contínua|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 ==
[[Imagem:Sanzio 01 Euclid.jpg|thumb|250px|Esta figura na obra "[[Escola de Atenas]]" de [[Rafael Sanzio|Rafael]] retrata muito provavelmente Euclides.]]

O algoritmo de Euclides é um dos mais antigos algoritmos ainda em uso.<ref name=autogenerated2>Knuth, p. 318.</ref> 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úmero real|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''.<ref name="Weil_1983">{{citar livro|autor=Weil A|autorlink=André Weil |ano= 1983 |título= Number Theory |publicado= Birkhäuser |local= Boston | isbn = 0-8176-3141-0 |páginas= 4–6}}</ref><ref name="Jones_1994">{{citar livro|autor = Jones A |ano= 1994 |capítulo= Greek mathematics to AD 300 |título= Companion encyclopedia of the history and philosophy of the mathematical sciences |publicado= Routledge |local= Nova Iorque | isbn = 0-415-09238-8 |páginas= 46–48}}</ref> O [[matemático]] e historiador [[Bartel Leendert van der Waerden|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]].<ref name="van_der_Waerden_1954">{{citar livro|autor=van der Waerden BL|autorlink=Bartel Leendert van der Waerden |ano= 1954 |título= Science Awakening | series = trad. Arnold Dresden |publicado= P. Noordhoff Ltd |local= Groningen |páginas= 114–115}}</ref> O algoritmo era provavelmente conhecido por [[Eudoxo de Cnido]] (cerca de 375 a.C.).<ref name=autogenerated2 /><ref>{{citar periódico|autor = von Fritz K |data= 1945 |título= The Discovery of Incommensurability by Hippasus of Metapontum |periódico= Ann. Math. | volume = 46 |páginas= 242–264 | doi = 10.2307/1969021}}</ref> Poderá ainda ser anterior a Eudoxo,<ref>{{citar livro|autor = [[T. L. Heath|Heath TL]] |ano= 1949 |título= Mathematics in Aristotle |publicado= Oxford Press |páginas= 80–83}}</ref><ref>{{citar livro|autor = David Fowler |ano= 1987 |título= The Mathematics of Plato's Academy: A New Reconstruction |publicado= Oxford University Press |local= Oxford | isbn = 0-19-853912-6 |páginas= 31–66}}</ref> a julgar pelo uso do termo técnico ἀνθυφαίρεσις (''anthyphairesis'', [[subtração]] recíproca) em trabalhos de Euclides e [[Aristóteles]].<ref>{{citar periódico|autor = Becker O |ano= 1933 |título= Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid |periódico= Quellen und Studien zur Geschichte der Mathematik B | volume = 2 |páginas= 311–333}}</ref>

Séculos mais tarde, o algoritmo de Euclides terá sido reinventado de forma independente na Índia e China,<ref>Stillwell, p. 31.</ref> sobretudo para resolver [[equação diofantina|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",<ref name=autogenerated1>Tattersall, p. 70.</ref> por causa da sua eficácia a resolver equações diofantinas.<ref>Rosen, pp. 86–87.</ref> Embora um caso especial do [[teorema chinês do resto]] já fora descrito pelo matemático e astrónomo chinês [[Sun Tzu (matemático)|Sun Tzu]],<ref>Ore, pp. 247–248.</ref> 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]]).<ref>Tattersall, pp. 72, 184–185.</ref> 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]] .<ref name=autogenerated1 /> Na Europa, era usado para resolver equações diofantinas e desenvolvimento de [[fração contínua|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.<ref>Tattersall, pp. 72–76.</ref>

== 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:

<math>MDC(a,b) = MDC(b, r)</math>

onde <math>r</math> é o resto da divisão de <math>a</math> por <math>b</math>.

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: <math>r = a - bq</math>, onde <math>q = \frac{a}{b}</math> é uma divisão inteira.

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

<math>r_{k+1} = r_{k-1} - r_kq</math>

que nos diz que para calcular o próximo resto, basta multiplicar o resto atual por <math>q = \frac{r_{k-1}}{r_k}</math> 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 (<math>r_k</math>) é o máximo divisor comum.

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

<code>MDC (a, b)
   if (b == 0)
       return a
   else
       return MDC(b, a % b)
</code>

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

<code>
MDC(a, b)
    while (b != 0)
        r = a % b
        a = b
        b = r
    return a;
</code>

=== Versão original (geométrica) ===
[[Imagem:Euclidean algorithm running time X Y.png|thumb|250px|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 <math>\sqrt{2}</math> 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 [[Os Elementos|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:

<div style="width:75%">
{{citar|1='''Para encontrar a máxima medida comum de dois números que não sejam primos entre si.'''
[[Imagem:Euclides VII-2.svg|centro|200px]]
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.
|2=[[Euclides]]. ''[[Os Elementos|Elementos]] VII.2''}}</div>

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 <math>(a_n)</math> por [[divisão euclidiana]] mostra que, para qualquer <math>n</math> tal que <math>a_{n+1}</math> é não nulo, existe um inteiro <math>q_{n+2}</math> tal que :
<math> a_{n}=q_{n+2}\times a_{n+1}+a_{n+2}</math>

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

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

<math>a_{N+1}</math> é 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:
{|class="wikitable" style="text-align:center"
|-
|348
|156
|-
|<nowiki>-</nowiki>312
----
36 ≠ 0
|2
|}

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

{|class="wikitable" style="text-align:center"
|-
|156
|36
|-
|<nowiki>-</nowiki>144
----
12 ≠ 0
|4
|}

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

{|class="wikitable" style="text-align:center"
|-
|36
|12
|-
|<nowiki>-</nowiki>36
----
0
|3
|}

{|class="wikitable" style="text-align:center"
|-
!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|Teoria de números|Máximo divisor comum#Algoritmo de Euclides para o MDC|Algoritmo de Euclides}}
* [[Algoritmo de Euclides estendido]]

== Bibliografia recomendada ==
* COUTINHO, Severino Coullier. ''Números inteiros e criptografia RSA''. [[Rio de Janeiro (estado)|Rio de Janeiro]]: [[IMPA]], [[2005]]. 226 p.&nbsp;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 (estado)|São Paulo]]: [[Editora da Universidade de São Paulo]], [[2003]]. ISBN 85-314-0458-4

{{Referências}}

{{Portal3|Matemática}}

[[Categoria:Teoria dos números]]
[[Categoria:Algoritmos matemáticos]]