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?
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
.
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


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,
.
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:
|
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:

- Se for verdade que
, então:

|

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

|
- Verifique, utilizando o princípio de indução, que:

- 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.