Algoritmo de Euclides – Wikipédia a enciclopédia livre

Prévia do material em texto

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.
Algoritmo de Euclides
Origem: Wikipédia, a enciclopédia livre.
Em matemática, o algoritmo de Euclides é 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
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.
Índice
1 História do desenvolvimento do algoritmo
2 Descrição do algoritmo
2.1 Versão original (geométrica)
3 Demonstração da terminação e exatidão do algoritmo
3.1 Pseudocódigo
4 Exemplo
5 Ver também
6 Bibliografia recomendada
7 Referências
[a]
[1]
Esta figura na obra "Escola de Atenas" de
Rafael retrata muito provavelmente
Euclides.
História do desenvolvimento do algoritmo
O algoritmo de Euclides é um dos mais antigos algoritmos ainda
em uso. 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. 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.
O algoritmo era provavelmente conhecido por Eudoxo de Cnido (cerca de 375 a.C.). Poderá ainda ser
anterior a Eudoxo, a julgar pelo uso do termo técnico ἀνθυφαίρεσις (anthyphairesis, subtração
recíproca) em trabalhos de Euclides e Aristóteles.
Séculos mais tarde, o algoritmo de Euclides terá sido reinventado de forma independente na Índia e China,
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 descrevu o algoritmo
como o "pulverizador", por causa da sua eficácia a resolver equações diofantinas. Embora um caso
especial do teorema chinês do resto já fora descrito pelo matemático e astrónomo chinês Sun Tzu, 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). 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 . 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.
Descrição do algoritmo
Versão original (geométrica)
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 não é um número racional, mas no caso de dois segmentos comensuráveis pretende-se determinar a
[2]
[3][4]
[5]
[2][6]
[7][8]
[9]
[10]
[11] [12]
[13]
[14]
[11]
[15]
Representação do número de passos
necessários no algoritmo de Euclides.
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:
1. 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.
2. 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.
3. 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 por divisão euclidiana mostra que, para qualquer tal que é não nulo,
existe um inteiro tal que : 
e ainda . A série de inteiros naturais é portanto estritamente decrescente, e atingirá
o valor num número finito de passos. A existência de um último resto não nulo está assim estabelecida.
Seja o índice deste último resto não nulo. Para mostrarar que é o MDC procurado, note-se
que a relação anterior se escreve como , o que mostra que divide .
Tomando , deduz-se que divide também ; também, e por
recorrência, note-se que divide todos os termos da série ; em particular os primeiros termos e . 
 é então um divisor comum de e . Reciprocamente, todo o divisor comum de a e b dividirá também 
, e de novo por recorrência, dividirá todos os termos da série ; em particular .
 é então um divisor comum de a e b que é divisível por todo e qualquer divisor comum: é assim o MDC.
Pseudocódigo
AlgoritmoDeEuclides(a: inteiro; b: inteiro): inteiro
variáveis
 divisor: inteiro
 dividendo: inteiro
 c: inteiro
início
 dividendo = a
 divisor = b
 enquanto resto(dividendo/divisor) ≠ 0
 início
 c = resto(dividendo/divisor)
 dividendo = divisor
 divisor = c
 fim-enquanto
 
 AlgoritmoDeEuclides = dividendo
fim-função
Ele também pode ser expresso utilizando recursividade:
AlgoritmoDeEuclides(a: inteiro; b: inteiro): inteiro
início
 se b = 0 então
 AlgoritmoDeEuclides = a
 senão
 AlgoritmoDeEuclides = AlgoritmoDeEuclides(b,resto(a,b))
 fim-se
fim-função
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
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
1. ↑ Thomas L. Heath, The Thirteen Books of Euclid's Elements, 2nd ed. [Facsimile. Original publication:
Cambridge University Press, 1925], 1956, Dover Publications
2. ↑ Knuth, p. 318.
3. ↑ Weil A. Number Theory. Boston: Birkhäuser, 1983. 4–6 p. ISBN 0-8176-3141-0
4. ↑ Jones A. Companion encyclopedia of the history and philosophy of the mathematical sciences. Nova
Iorque: Routledge, 1994. 46–48 p. ISBN 0-415-09238-8
5. ↑ van der Waerden BL. Science Awakening. Groningen: P. Noordhoff Ltd, 1954. 114–115 p.
6. ↑ von Fritz K. (1945). "The Discovery of Incommensurability by Hippasus of Metapontum". Ann. Math. 46:
242–264. DOI:10.2307/1969021 (http://dx.doi.org/10.2307/1969021) .
7. ↑ Heath TL. Mathematics in Aristotle. [S.l.]: Oxford Press, 1949. 80–83 p.
8. ↑ David Fowler. The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University
Press, 1987. 31–66 p. ISBN 0-19-853912-6
9. ↑ Becker O. (1933). "Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles
und Euklid" 2: 311–333.
10. ↑ Stillwell, p. 31.
11. ↑ Tattersall, p. 70.
12. ↑ Rosen, pp. 86–87.
13. ↑ Ore, pp. 247–248.
14. ↑ Tattersall, pp. 72, 184–185.
15. ↑ Tattersall, pp. 72–76.
Obtida de "http://pt.wikipedia.org/w/index.php?title=Algoritmo_de_Euclides&oldid=32851986"
Categorias: Teoria dos números Algoritmos matemáticos
Menu de navegação
Esta página foi modificada pela última vez à(s) 23h00min de 5 de novembro de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
a b
a b
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.