_____________
 *  Este artigo está baseado no texto de uma conferência pronunciada no Primeiro Fórum sobre o Ensino de Matemática, em novembro de 1992, no Instituto de Matemática da UFPB, Campina Grande.
 

Hoje ensina-se, nas escolas do 1.° e 2.° graus, a extrair o máximo divisor comum de dois inteiros por um processo que exemplificamos no caso do mdc(243,37):

As operações efetuadas acima foram as seguintes:

243 = 6 x 37 + 21
  37 = 21 x 1 + 16
  21 = l x 16 + 5
  16 = 5 x 3+1
    5 = 1 x 5.

O algoritmo termina quando o resto da divisão é nulo; o máximo divisor comum é o último divisor obtido.

0 algoritmo do processo apresentado acima é o célebre algoritmo de Euclides, conhecido desde a antiguidade. Ele encontra-se exposto, para números, na Proposição 1 do livro VII dos Elementos de Euclides, escritos em torno de 300 a.C. Aplicado a grandezas (figura abaixo), o algoritmo, como demonstrado nas Proposições 2 e 3 do livro X, permite verificar se elas são ou não comensuráveis: quando o são, ele termina após um número finito de passos e determina sua maior medida comum; caso contrário, ele prossegue indefinidamente.

AB e CD são comensuráveis e FD é a sua "maior medida comum".

Em linguagem numérica moderna, o algoritmo de Euclides para achar o máximo divisor comum de dois números a e b é inteiramente equivalente a escrever o quociente a/b como fração contínua. Usando parte do algoritmo da página anterior, temos, por exemplo,

Portanto, através do algoritmo de Euclides podemos dizer que um número real tem representação em fração contínua infinita se, e somente se, ele é irracional, ou seja, representa uma razão entre grandezas incomensuráveis.

A aplicação do algoritmo, em sua versão para grandezas, à diagonal e ao lado de um quadrado permite mostrar, sem usar o Teorema de Pitágoras, que esses dois segmentos são incomensuráveis ([4], p. 127).

Os historiadores da Matemática acreditam que esse algoritmo era conhecido já em 400 a.C. Ele é de importância fundamental em teoria dos números, e sua apresentação nas escolas pode ser enriquecida em vários aspectos:

-    Fazendo referência à história do algoritmo.   O simples fato de que ele é o mais antigo algoritmo não trivial ainda em uso ([1], vol. II, p. 294) já mereceria destaque.

-     Mencionando sua importância matemática.   Ele é usado para o estudo que Euclides faz da teoria dos números, e ainda hoje os livros desse assunto dão uma ênfase bem merecida ao algoritmo.  Além disso, como a noção de algoritmo   tem adquirido importância crescente em Matemática nos últimos anos, o algoritmo de Euclides permite discutir o que é um algoritmo, como demonstrar que um algoritmo realmente chega ao fim, discutir o que é eficiência de um algoritmo, etc.  Nesse sentido, convém observar que hoje há algoritmos mais eficientes do que o de Euclides para achar o máximo divisor comum, pelo menos se estivermos trabalhando com um computador, usando aritmética binária. Por exemplo, o algoritmo de Silver, Terzian e Stein, de  1962 ([1], vol. II, p. 297).

-      Aplicando o algoritmo de Euclides em problemas interessantes, ou seja, fazendo aplicações dignas de nota da noção de máximo divisor comum.

A fim de demonstrar o algoritmo de Euclides, necessitamos do seguinte resultado:

TEOREMA l.  Sejam   a   e   b   dois inteiros positivos e   a = bq + r, com  0 r < b.   Então mdc(a,b) = mdc(b, r).

Com efeito, se  a = bq + r,  então  r = a bq.   Seja  k  um divisor comum de  a  e de  b;  então k\a  e  k\b. Assim,  k\r, ou seja, k é um divisor comum de b e de r. Reciprocamente, como a = bq + r, vem imediatamente que todo divisor comum de  b  e de  r  é divisor comum de  b  e de  a.

Assim, o conjunto dos divisores comuns de a e de b é igual ao conjunto dos divisores comuns de b e de r. Logo, mdc(a ,b) = mdc(b, r).

Demonstrado esse resultado, podemos enunciar e provar o algoritmo de Euclides:

TEOREMA 2. Sejam a e b inteiros positivos, com a b.   Usando sucessivamente o algoritmo da divisão, escreva

a = bq₁ + b₁,     0 < b₁ < b,

b = b₁q₂ + b₂,       0 < b₂  < b₁,

b₁ = b₂q₃ + b₃,     0 < b3 < b₂,

. . .                                         

b_n-2 = b_n-l q_n + b_n,       0<b_n<b_n-1,

b_n-l  = b_nq_{n + l}

Então mdc(a,b) = b_n.

Com efeito, em primeiro lugar, o processo acima realmente chega ao fim. De fato, como 0 < b_n < b_n-1 < ^{. . .} < b₁ < 6, vemos que esse processo não pode repetir-se indefinidamente, pois temos uma seqüência estritamente decrescente de inteiros positivos e há um número finito de inteiros entre 0 e b. Ora, pelo Teorema 1, mdc(a,b) = mdc(b,b₁) = mdc(b₁,b₂) = mdc(b₂,b₃) =  ^{. . .} mdc(b_n-1,b_n).  Mas mdc(b_n-1,b_n) = b_n, pois b_n-1 é um múltiplo de   b_n,  o que conclui a demonstração do teorema.

OBS.: Euclides, nos Elementos, não apresenta o algoritmo na forma acima. Sua construção é a seguinte: Dados  a  e  b inteiros, sejam

a₁ = max (a,b) min (a,b)

b₁ = min (a,b),

e, de maneira geral,

a_i+1 = max(a_i,b_i) min(a_i,b_i)

b_i+1 = min(a_i,b_i)

Isso significa, em cada estágio, subtrair o número menor do maior e repetir sucessivamente o processo, até obter a_k = b_k para algum k. Este valor comum será o máximo divisor comum de a e de b. Essa versão do algoritmo dá origem ao chamado "Jogo de Euclides" (ver RPM 14, p. 24).

Usando a formulação original de Euclides, o exemplo no início deste artigo seria disposto como abaixo:

O algoritmo de Euclides era também conhecido pelos matemáticos chineses. No livro Nove capítulos da arte matemática, escrito entre 206 a.C. e 221 d.C, encontramos uma descrição para o algoritmo idêntica à apresentada por Euclides. Esse livro se baseia em uma obra mais antiga, datada entre 221 a.C. e 206 a.C.

Usando o algoritmo de Euclides, são necessárias n + 1 divisões para vermos que mdc(a,b) = b_n , pois só chegamos a uma conclusão quando verificarmos que    b_n-1  = b_n q_n+1 + b_n+1  = b_n q_n+1 + 0 = b_n q_n+1.

Chamaremos de comprimento do algoritmo de Euclides o número de divisões necessárias para calcular o mdc(a,b). Usando a notação do teorema, o comprimento do algoritmo de Euclides é n +1.

O algoritmo de Euclides é bem eficiente. Por exemplo, se quisermos verificar que mdc(97,24) = 1, serão necessários apenas dois passos:

97 = 4 x 24 + 1

24 = 24 x 1.

Agora, se queremos calcular  mdc(21479,24),  temos

21479 = 894 x 24 + 23, 24 = 1 x 23 + 1,

23 = 1  23.

Ou seja, em 3 passos vemos que  mdc(21479,24) = 1.   Por fim, como último exemplo, para calcular  mdc(49745692,24),  temos

49745692 = 2072737 x 24 + 4,

24 = 6 x 4;

isto é, em apenas 2 passos chegamos ao resultado desejado.

Dados dois números inteiros e positivos a e b, uma pergunta natural é: qual o comprimento do algoritmo de Euclides aplicado a eles? Em outras palavras, quantas divisões são necessárias para calcular o máximo divisor comum de  a  e  b.

É imediato verificar que, se mantivermos b fixo, mesmo que a    seja muito grande em relação a    b, o número de divisões no algoritmo de Euclides não pode crescer.   Em verdade, esse número depende apenas de  b.

TEOREMA 3. Suponha, que a e b são inteiros positivos, com a b. Então, o comprimento do algoritmo de Euclides para, achar mdc(a,b) depende somente de b e é, no máximo, igual a  b.

Com efeito, usando mais uma vez a notação do Teorema 1, sabemos que, no algoritmo, mdc(a,b) = b_n e que 0 < b_n < b_n-1 < ^{. . .} < b₁ < b. Como há no máximo b 1 inteiros distintos não negativos entre 0 e b, vemos que n b 1, donde n + 1 b. Ora, como já vimos, são necessárias n + 1 divisões para determinar o máximo divisor comum. Assim, são necessárias no máximo b divisões para achar  mdc(a,b).

No entanto, esse resultado não é muito bom. Por exemplo, se b = 99, devemos ter que n + 1 99 e chegamos à conclusão de que talvez tenhamos que efetuar 99 divisões para calcular o máximo divisor comum!

O Teorema de Lamé melhora muito essa situação:

TEOREMA 4 ( Lamé). Sejam a e b inteiros positivos. Então, o comprimento do algoritmo de Euclides aplicado a   a   e a   b   é menor ou igual a cinco vezes o número de dígitos na representação decimal de  b.

Segundo o teorema, se b é igual a 99, então o número de divisões no algoritmo de Euclides é no máximo 10, não sendo in­fluenciado por a. Isso representa um progresso notável em relação à estimativa anterior.

Esse teorema é devido a Lamé *. Embora não tenha se dedicado sistematicamente à teoria dos números, ele deixou algumas jóias sobre o assunto, uma das quais é o teorema acima.

__________
*   Gabriel Lamé (1795-1870), engenheiro e matemático francês, conhecido por seus trabalhos sobre a equação do calor e criador das coordenadas curvilíneas.

A demonstração do Teorema de Lamé é um exemplo de utilização inteligente dos números de Fibonacci.

Como sabemos, estes números foram introduzidos por Leonardo de Pisa (1170(?)-1250), também chamado de Fibonacci, em seu livro Líber Abbaci, de 1202, onde encontramos, como um exercício sobre multiplicação, o famoso "problema dos coelhos": Começando com um casal de coelhos, supondo que nenhum coelho morre, que cada casal gera um novo casal por mês e que um casal de coelhos começa a ter filhotes com um mês de idade, quantos casais de coelhos teremos após 12 meses? (V. RPM 6, p. 9.)

E fácil ver que a solução do problema é dada pela seqüência

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,

em que cada termo dá o número de coelhos no primeiro, segundo, . . ., décimo segundo mês.

A lei de formação dos termos dessa seqüência é

fn =  f_{n - l} + f_{n - 2}

e ela tem se revelado muito importante, atualmente, no estudo dos algoritmos usados em computação (teórica ou prática).

Embora isso não seja muito conhecido, em 1611, Johann Kepler (1571-1630) também considerou a mesma seqüência, ao estudar a disposição de folhas e flores nas plantas ("filotaxia").

A primeira aplicação dos números de Fibonacci ao estudo dos algoritmos foi dada por Lamé, em 1844, no teorema enunciado acima. Em verdade, essa foi a primeira aplicação "significativa" desses números.

Para efetuarmos a demonstração, voltemos ao algoritmo de Euclides. Em primeiro lugar, b_n 1, pois b_n é um número inteiro. De  b_n-1 = b_nq_n+1,  vemos que  b_n-1 2,  pois  b_n-1 > b_n.  Assim,  b_n  f₁   e  b_n-1 f₂.   Então,

b_n-2  = b_n-1 q_n + b_n f₂ + f₁ = f₃ ,   pois    q_n   1.

Analogamente,

b_n-3  = b_n-2 q_n-1 + b_n-1 f₃ + f₂  = f₄ ,   pois    q_n-1   1.

Continuando dessa maneira, vemos, de maneira geral, que

b_n-k f_k+1    para    k = 0,1,2, . . . ,n - 1,

e, enfim,

b = b₁q₂ + b₂ f_n + f_n-1 =f_n+1,

ou seja, fazendo  b₀ = b,  temos:

b_n-k f_k+1,    para    k = 0,1,2,..., n.

Ilustrando:

Esse resultado nos mostra que o comprimento do algoritmo de Euclides é menor ou igual ao número de ordem do maior número de Fibonacci menor ou igual a  b.

Podemos ver que esse resultado é o melhor possível achando o máximo divisor comum entre dois números de Fibonacci consecutivos. Calculemos, por exemplo,  mdc(21,13) = mdc(f₇, f₆):

21 = 13 + 8

13 = 8 + 5

  8 = 5 + 3

  5 = 3 + 2

  3 = 2 + 1

  2 = 1 x 2 + 0.

Nesse exemplo,  f₇  e  f₆  não desempenham nenhum papel essencial, pois o mesmo acontece no caso geral, para achar  mdc(f_n-1, f_n).

Mas

e assim sucessivamente, chegando enfim a

Em particular,

Ora, calcula-se facilmente, usando uma tábua de logaritmos ou uma máquina de calcular, que

Se o número de algarismos na representação decimal de b é s, então

e, portanto, b < 10^s, donde log₁₀b < s, e vemos que n < 5s. Como n é um inteiro estritamente menor do que 5s, temos que n + 1 < 5s,  o resultado procurado.

Referências Bibliográficas

[1] KNUTH, Donald E. The Art of Computer Programming, vol.  2:  Seminumerical Algoríthms. Addison-Wesley, 1969.

[2]  ROBERTS,  Joe.    Elementary Number Theory,  a Problem Oriented Approach. Mass., MIT, Cambridge, 1978.

[3]   USPENSKY, J.V. e HEASLETT M. A. Elementary Number Theory. New York, McGraw Hill, 1939.

[4]   van der WAERDEN, B. L. Science A wakening. Gronigen, Walters Noodhoff, 3.ª ed.

[5]  van der WAERDEN, B. L. Geometry and Álgebra in Ancient Civilizations. Berlin, Springer-Verlag, 1983.