Teoria de números/Eficiência do algoritmo de Euclides

Neste capítulo, será discutido quão eficiente é o algoritmo de Euclides para o cálculo do MDC. De forma mais precisa, se forem dados dois números inteiros:

Quantas etapas (divisões) do algoritmo são necessárias para que um resto seja zero?

Fazendo estimativas editar

Recorde-se que o algoritmo baseia-se na construção da sequência:

cujos termos verificam as seguintes igualdades:

1
2
k-1
k pois

O algoritmo fornece , que é o último resto não nulo, obtido em passos (divisões).

Uma observação importante é que o resto de uma divisão é sempre menor que a metade do dividendo:

Sendo a primeira desigualdade válida porque e a segunda porque . Deste modo, tem-se

e em geral

, para cada .

Assim, comparando os termos cujos índices são pares, segue:

Por indução, resulta para cada termo:

De modo análogo, ao comparar os termos ímpares, e usar novamente indução, segue:

Com isso, a sequência dos decresce geometricamente, pois está fixado. O fato de ser uma sequência decrescente já havia sido demonstrado quando se justificou o funcionamento do algoritmo de Euclides. A novidade aqui é a velocidade com que a sequência decresce. Pelos cálculos anteriores, os restos diminuem, no mínimo, tão rápido quanto os termos da progressão geométrica .

A questão colocada era: Quantas divisões são necessárias para que o resto seja zero?

Analisando a progressão geométrica dada anteriormente, conclui-se que algum de seus termos é menor do que . Nesse caso, o resto correspondente será nulo, e o algoritmo para. Para ser mais exato, como

o menor índice inteiro que torna menor que é

Onde denota o maior inteiro que não supera (a parte inteira de ).

Então , e consequentemente , pois os restos são números inteiros não-negativos.

Assim, sabendo que o algoritmo para exatamente quando , conlui-se que tal índice não pode ser maior que , em símbolos:

Para melhor compreender o significado dessa estimativa, considere que tem dígitos decimais. Então:

Aplicando o logaritmo em ambos os membros da segunda desigualdade, resulta

Logo, , que para valores grandes de é aproximadamente .

Embora esta não seja a melhor aproximação para , já é bastante útil, pois mostra que o número de etapas cresce linearmente com o número de dígitos de .

O pior caso editar

Para obter uma estimativa mais precisa do número de etapas que o algoritmo de Euclides leva para determinar o MDC de dois números, será considerada a seguinte questão:

Qual é o menor valor de para o qual o algoritmo leva passos?

Veja alguns exemplos utilizando a representação matricial do algoritmo:

Para :

Para :

Para :

É fácil perceber que é mínimo quando os valores forem todos iguais a , cada entrada da matriz é um polinômio nas variáveis (que são positivas), e cujos coeficiêntes são (se puder, acrescente uma justificativa mais formal).

Se cada quociente for substituído por na fórmula de recorrência

Esta passará a ser:

Que vale para satisfazendo .

A nova relação lembra a fórmula que define a sequência de Fibonacci, embora esteja "ao contrário".


Este módulo tem a seguinte tarefa pendente: Conferir se o expoente k+1 está correto ou se deveria ser k, na próxima equação

Matricialmente, as condições produzem as seguintes igualdades:

, sendo que .

Com um simples uso do princípio de indução finita, consegue-se:

, desde que .

Deste modo,

Como , segue que

Teorema

Dado , sejam e os menores números tais que o algoritmo de Euclides aplicado a e leva exatamente passos, então e .

Exemplificando editar

Para determinar o valor de , seria necessário efetuar cinco divisões:

Logo, . Aproveitando este exemplo, observe que:

No entanto, se qualquer dos números for menor, o algoritmo requer menos etapas. Por exemplo, ao determinar tem-se:

Donde, .

Já o cálculo de é ainda mais simples:

Portanto, .

Melhorando as estimativas editar

Sabendo qual é o pior caso para a aplicação do algoritmo de Euclides, pode-se deduzir uma melhor estimativa de sua eficiência. Uma análise mais elaborada que aquela apresentada no início do capítulo fornece o seguinte resultado:

Teorema de Lamé editar

Teorema

O número de passos (de divisões) no algoritmo de Euclides com entradas   e   é limitado superiormente por   vezes a quantidade de dígitos decimais em  .

Gabriel-Lamé
 
  Este módulo tem a seguinte tarefa pendente: Incluir breve biografia sobre Lamé.

Para demonstrar o teorema de Lamé, é importante ter em mente algumas propriedades relacionadas a sequência de Fibonacci e ao número de ouro:

 

Tem-se:

  •  
Demonstração
A verificação é direta, exigindo cálculos bastante simples.
  •  , arredondado para o inteiro mais próximo.
Demonstração
Utilizando a fórmula de Binet, basta observar que o módulo de   é menor que  , e consequentemente, quando  , tem-se  
  •  
Demonstração
A justificativa será dada por indução:
  1.  
  2. Se for verdade que  , então:
 
  •  
Demonstração
De fato, valem as seguintes equivalências:

 

Mas   (verifique a partir de  ), e   pois

 

Sendo que esta última desigualdade é verdadeira.

Como foi visto anteriormente, quando   é exige exatamente   passos, é tem-se   e  . Logo,

 

Aplicando o logaritmo em ambos os menbros, segue:

 

ou seja

 

Mas  , então:

 , onde   é o número de dígitos de  

Demonstração da fórmula de Binet editar

Nesta seção, será deduzida a fórmula de Binet:

 

onde   e  .

A principal razão para se utilizar está fórmula, em vez da definição recursiva da sequência de Fibonacci, é que ela permite a obtenção de um termo da sequência sem precisar calcular os anteriores.

Demonstração
A relação entre os termos da sequência pode ser descrita matricialmente da seguinte forma:
 

Para simplificar, será adotada a seguinte notação:

 

A partir de um simples argumento de indução (veja exercício 1), obtem-se:

 

Neste ponto, recorre-se à Álgebra linear, para obter um jeito simples de calcular o produto acima. Se puder ser escrito

 , com   e   sendo auto-vetores de  , ou seja, vetores não nulos tais que   e  , será possível obter:
 

A partir daí será bastante simples conseguir a fórmula explicita para   (a segunda componente do vetor à esquerda), pois   seriam constantes.

É, portanto, necessário determinar essas constantes, a começar pelos auto-valores de  . Tem-se:

 

Logo  , ou seja,   Assim,   (que implica  ) ou  . O primeiro caso não é de interesse, pois auto-vetores não são nulos.

Note que a equação acima possui duas raízes:

  •  
  •  

Além disso, se   é raiz da equação, então para cada  , o vetor

  é um auto-vetor de  .

Em particular, se  , os auto-vetores correspondentes a cada raiz da equação quadrática são:

  •  
  •  

De modo que   e  

Resta escrever   conforme se pretendia. Isso é fácil, já que são conhecidos   e  :

 

Da segunda equação, segue que  . Substituindo esse valor na primeira equação, resulta:  

Como   (verifique!), tem-se  . Logo,  .

Assim,  . Em consequência:

 

Em particular, escrevendo a igualdade entre as segundas coordenadas desses vetores, obtem-se a fórmula desejada:

 

Exercícios editar

  1. Verifique, utilizando o princípio de indução, que:
     
  2. Escreva outra demonstração para a fórmula de Binet, utilizando o princípio de indução.

Por enquanto, não há muitos exercícios sobre este capítulo. O leitor está convidado a adicionar mais ítens a essa seção, para ajudar a melhorar o texto.