# 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

Recorde-se que o algoritmo baseia-se na construção da sequência:
    $a=r_{0}\geq b=r_{1}>r_{2}>\ldots >r_{k}>r_{k+1}=0$
cujos termos verificam as seguintes igualdades:
| 1 | $r_{0}=$ | $r_{1}q_{0}+r_{2}$ | $0\leq r_{2}<r_{1}$ |
| 2 | $r_{1}=$ | $r_{2}q_{1}+r_{3}$ | $0\leq r_{3}<r_{2}$ |
| | $\vdots$ | | |
| k-1 | $r_{k-2}=$ | $r_{k-1}q_{k-2}+r_{k}$ | $0\leq r_{k}<r_{k-1}$ |
| k | $r_{k-1}=$ | $r_{k}q_{k-1}+r_{k+1}=r_{k}q_{k-1}$ | pois $0=r_{k+1}<r_{k}$ |
O algoritmo fornece $(a,b)=r_{k}$, que é o último resto não nulo, obtido em $k$ passos (divisões).
Uma observação importante é que o resto de uma divisão é sempre menor que a metade do dividendo:
    $r_{0}=r_{1}q_{0}+r_{2}\geq r_{1}+r_{2}>2r_{2}$
Sendo a primeira desigualdade válida porque $q_{0}\geq 1$ e a segunda porque $r_{1}>r_{2}$. Deste modo, tem-se
    $r_{0}>2r_{2}$
    $r_{1}>2r_{3}$
    $r_{2}>2r_{4}$
    $r_{3}>2r_{5}$
e em geral
    $r_{k}>2r_{k+2}$, para cada $k\geq 0$.
Assim, comparando os termos cujos índices são pares, segue:
    $r_{0}<a/2$
    $r_{2}<r_{0}/2<a/4$
    $r_{4}<r_{2}/2<r_{0}/4<a/8$
    $\ldots$
Por indução, resulta para cada termo:
    $r_{2j}<a/2^{j+1}$
De modo análogo, ao comparar os termos ímpares, e usar novamente indução, segue:
    $r_{2j+1}<a/2^{j+1}$
Com isso, a sequência dos $r_{j}$ decresce geometricamente, pois $a$ 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,{\frac {a}{2}},{\frac {a}{4}},{\frac {a}{8}},{\frac {a}{16}},\ldots )$.
A questão colocada era: Quantas divisões são necessárias para que o resto $r_{k+1}$ seja zero?
Analisando a progressão geométrica dada anteriormente, conclui-se que algum de seus termos é menor do que $1$. Nesse caso, o resto correspondente será nulo, e o algoritmo para. Para ser mais exato, como
    ${\frac {a}{2^{x}}}<1\Leftrightarrow a<2^{x}\Leftrightarrow \log _{2}a<x$
o menor índice inteiro $t$ que torna ${\frac {a}{2^{t}}}$ menor que $1$ é
    $t=\lfloor \log _{2}a\rfloor +1$
Onde $\lfloor \alpha \rfloor$ denota o maior inteiro que não supera $\alpha$ (a parte inteira de $\alpha$).
Então $r_{2t}<{\frac {a}{2^{t+1}}}<{\frac {a}{2^{t}}}<1$, e consequentemente $r_{2t}=0$, pois os restos são números inteiros não-negativos.
Assim, sabendo que o algoritmo para exatamente quando $r_{k+1}=0$, conlui-se que tal índice $k+1$ não pode ser maior que $2t$, em símbolos:
    $k+1\leq 2(\lfloor \log _{2}a\rfloor +1)$
Para melhor compreender o significado dessa estimativa, considere que $a$ tem $N$ dígitos decimais. Então:
    $10^{N-1}\leq a<10^{N}$
Aplicando o logaritmo em ambos os membros da segunda desigualdade, resulta
    $\log _{2}a<N\cdot \log _{2}10$
Logo, $k+1\leq 2(\lfloor \log _{2}a\rfloor +1)<2N\cdot \log _{2}10+2$, que para valores grandes de $N$ é aproximadamente $6,6N$.
Embora esta não seja a melhor aproximação para $k$, já é bastante útil, pois mostra que o número de etapas cresce linearmente com o número de dígitos de $a$.

### O pior caso

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 $a$ para o qual o algoritmo leva $n$ passos?
Veja alguns exemplos utilizando a representação matricial do algoritmo:
Para $n=1$:
    ${\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}q_{0}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}$
Para $n=2$:
    ${\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}q_{0}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}q_{1}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}={\begin{bmatrix}q_{0}q_{1}+1&q_{0}\\q_{1}&1\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}$
Para $n=3$:
    ${\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}q_{0}q_{1}+1&q_{0}\\q_{1}&1\end{bmatrix}}\cdot {\begin{bmatrix}q_{2}&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}={\begin{bmatrix}q_{0}q_{1}q_{2}+q_{0}+q_{2}&q_{0}q_{1}+1\\q_{1}&1\end{bmatrix}}{\begin{bmatrix}d\\0\end{bmatrix}}$
É fácil perceber que $a$ é mínimo quando os valores $q_{0},\ldots ,q_{k-1}$ forem todos iguais a $1$, cada entrada da matriz é um polinômio nas variáveis $q_{j}$ (que são positivas), e cujos coeficiêntes são $1$ (se puder, acrescente uma justificativa mais formal).
Se cada quociente for substituído por $1$ na fórmula de recorrência
    $r_{j-1}=r_{j}q_{j-1}+r_{j+1}$
Esta passará a ser:
    $r_{j-1}=r_{j}+r_{j+1}$
Que vale para $j$ satisfazendo $1\leq j\leq k$.
A nova relação lembra a fórmula que define a sequência de Fibonacci, embora esteja "ao contrário".
Matricialmente, as condições $q_{0}=1,\ldots ,q_{k-1}=1$ produzem as seguintes igualdades:
    ${\begin{bmatrix}a\\b\end{bmatrix}}=\overbrace {{\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}\cdot \ldots \cdot {\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}} \cdot {\begin{bmatrix}d\\0\end{bmatrix}}={\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}^{k+1}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}$, sendo que $d=(a,b)$.
Com um simples uso do princípio de indução finita, consegue-se:
    ${\begin{bmatrix}\mathbf {1} &1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}}$, desde que $n\geq 1$.
Deste modo,
    ${\begin{bmatrix}a\\b\end{bmatrix}}={\begin{bmatrix}F_{k+2}&F_{k+1}\\F_{k+1}&F_{k}\end{bmatrix}}\cdot {\begin{bmatrix}d\\0\end{bmatrix}}={\begin{bmatrix}d\cdot F_{k+2}\\d\cdot F_{k+1}\end{bmatrix}}$
Como $d=(a,b)\geq 1$, segue que
* $a\geq F_{k+2}$
* $b\geq F_{k+1}$

#### Teorema

Dado $n\geq 1$, sejam $a$ e $b$ os menores números tais que o algoritmo de Euclides aplicado a $a$ e $b$ leva exatamente $n$ passos, então $a=F_{n+2}$ e $b=F_{n+1}$.

#### Exemplificando

Para determinar o valor de $(F_{7},F_{6})=(13,8)$, seria necessário efetuar cinco divisões:
    $13=8\cdot 1+5$ $8=5\cdot 1+3$ $5=3\cdot 1+2$ $3=2\cdot 1+\mathbf {1}$ $2=\mathbf {1} \cdot 2+0$
Logo, $(13,8)=1$. Aproveitando este exemplo, observe que:
    ${\begin{bmatrix}13\\8\end{bmatrix}}={\begin{bmatrix}13&8\\8&5\end{bmatrix}}\cdot {\begin{bmatrix}1\\0\end{bmatrix}}={\begin{bmatrix}F_{5+2}&F_{5+1}\\F_{5+1}&F_{5}\end{bmatrix}}\cdot {\begin{bmatrix}1\\0\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{5+1}\cdot {\begin{bmatrix}1\\0\end{bmatrix}}$
No entanto, se qualquer dos números for menor, o algoritmo requer menos etapas. Por exemplo, ao determinar $(13,7)$ tem-se:
    $13=7\cdot 1+6$ $7=6\cdot 1+\mathbf {1}$ $6=\mathbf {1} \cdot 6+0$
Donde, $(13,7)=1$.
Já o cálculo de $(12,8)$ é ainda mais simples:
    $12=8\cdot 1+\mathbf {4}$ $8=\mathbf {4} \cdot 2+0$
Portanto, $(12,8)=4$.

## Melhorando as estimativas

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é
#### Teorema

O número de passos (de divisões) no algoritmo de Euclides com entradas $u$ e $v$ é limitado superiormente por $5$ vezes a quantidade de dígitos decimais em $min(u,v)$.
Para demonstrar o teorema de Lamé, é importante ter em mente algumas propriedades relacionadas a sequência de Fibonacci e ao número de ouro:
    $\varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.618$
Tem-se:
* $\varphi ^{2}=\varphi +1$
* $F_{n}={\frac {\varphi ^{n}}{\sqrt {5}}}$, arredondado para o inteiro mais próximo.
* $F_{n}\geq \varphi ^{n-1}$
* $\log \varphi <{\frac {1}{5}}$
Como foi visto anteriormente, quando $(a,b)$ é exige exatamente $n$ passos, é tem-se $a\geq F_{n}+2$ e $b\geq F_{n}+1$. Logo,
    $a\geq F_{n}+2\geq \varphi ^{n+1}$
Aplicando o logaritmo em ambos os menbros, segue:
    $(n+1)\log \varphi \leq \log a$
ou seja
    $n\leq {\frac {\log a}{\log \varphi }}=\log _{\varphi }a$
Mas ${\frac {1}{\log \varphi }}<5$, então:
    $n\leq {\frac {1}{\log \varphi }}\cdot \log a<5\log _{\varphi }a<5N$, onde $N$ é o número de dígitos de $a$

## Demonstração da fórmula de Binet

Nesta seção, será deduzida a fórmula de Binet:
    $F_{n}={\frac {1}{\sqrt {5}}}\left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right)={\frac {\varphi ^{n}-{\hat {\varphi }}^{n}}{\sqrt {5}}}$
onde $\varphi ={\frac {1+{\sqrt {5}}}{2}}$ e ${\hat {\varphi }}={\frac {1-{\sqrt {5}}}{2}}$.
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.

## Exercícios

* Verifique, utilizando o princípio de indução, que:
    ${\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}\cdot {\begin{bmatrix}F_{1}\\F_{0}\end{bmatrix}}$
* 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.