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\ge b=r_1>r_2>\dots >r_k>r_{k+1}=0$

cujos termos verificam as seguintes igualdades:

1	$r_0=$	$r_1{q}_0+r_2$	$0\le r_2<r_1$
2	$r_1=$	$r_2{q}_1+r_3$	$0\le r_3<r_2$
	$⋮$
k-1	$r_{k-2}=$	$r_{k-1}{q}_{k-2}+r_k$	$0\le 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\ge r_1+r_2>2r_2$

Sendo a primeira desigualdade válida porque $q_0\ge 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\ge 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$

$\dots$

Predefinição:Wikipedia 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},\dots )$.

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\iff a<2^x\iff {\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\le 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}\le 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\le 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$:

$\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{cc}{q}_0& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]$

Para $n=2$:

$\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{cc}{q}_0& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{cc}{q}_1& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]=\left[\begin{array}{cc}{q}_0{q}_1+1& q_0\\ q_1& 1\end{array}\right]\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]$

Para $n=3$:

$\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{cc}{q}_0{q}_1+1& q_0\\ q_1& 1\end{array}\right]\cdot \left[\begin{array}{cc}{q}_2& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]=\left[\begin{array}{cc}{q}_0{q}_1{q}_2+q_0+q_2& q_0{q}_1+1\\ q_1& 1\end{array}\right]\left[\begin{array}{c}d\\ 0\end{array}\right]$

É fácil perceber que $a$ é mínimo quando os valores $q_0,\dots ,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\le j\le k$.

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

Predefinição:Tarefa Matricialmente, as condições $q_0=1,\dots ,q_{k-1}=1$ produzem as seguintes igualdades:

$\left[\begin{array}{c}a\\ b\end{array}\right]=\overbrace{\left[\begin{array}{cc}\mathrm{𝟏}& 1\\ 1& 0\end{array}\right]\cdot \left[\begin{array}{cc}\mathrm{𝟏}& 1\\ 1& 0\end{array}\right]\cdot \dots \cdot \left[\begin{array}{cc}\mathrm{𝟏}& 1\\ 1& 0\end{array}\right]}\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]={\left[\begin{array}{cc}\mathrm{𝟏}& 1\\ 1& 0\end{array}\right]}^{k+1}\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]$, sendo que $d=(a,b)$.

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

${\left[\begin{array}{cc}\mathrm{𝟏}& 1\\ 1& 0\end{array}\right]}^n=\left[\begin{array}{cc}{F}_{n+1}& F_n\\ F_n& F_{n-1}\end{array}\right]$, desde que $n\ge 1$.

Deste modo,

$\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{cc}{F}_{k+2}& F_{k+1}\\ F_{k+1}& F_k\end{array}\right]\cdot \left[\begin{array}{c}d\\ 0\end{array}\right]=\left[\begin{array}{c}d\cdot F_{k+2}\\ d\cdot F_{k+1}\end{array}\right]$

Como $d=(a,b)\ge 1$, segue que

• $a\ge F_{k+2}$
• $b\ge F_{k+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+\mathrm{𝟏}$

$2=\mathrm{𝟏}\cdot 2+0$

Logo, $(13,8)=1$. Aproveitando este exemplo, observe que:

$\left[\begin{array}{c}13\\ 8\end{array}\right]=\left[\begin{array}{cc}13& 8\\ 8& 5\end{array}\right]\cdot \left[\begin{array}{c}1\\ 0\end{array}\right]=\left[\begin{array}{cc}{F}_{5+2}& F_{5+1}\\ F_{5+1}& F_5\end{array}\right]\cdot \left[\begin{array}{c}1\\ 0\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^{5+1}\cdot \left[\begin{array}{c}1\\ 0\end{array}\right]$

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+\mathrm{𝟏}$

$6=\mathrm{𝟏}\cdot 6+0$

Donde, $(13,7)=1$.

Já o cálculo de $(12,8)$ é ainda mais simples:

$12=8\cdot 1+\mathrm{𝟒}$

$8=\mathrm{𝟒}\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é

Gabriel-Lamé

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

$\phi =\frac{1+\sqrt{5}}{2}\approx 1.618$

Tem-se:

• ${\phi }^2=\phi +1$

• $F_n=\frac{{\phi }^n}{\sqrt{5}}$, arredondado para o inteiro mais próximo.

• $F_n\ge {\phi }^{n-1}$

• $\log \phi <\frac{1}{5}$

Como foi visto anteriormente, quando $(a,b)$ é exige exatamente $n$ passos, é tem-se $a\ge F_n+2$ e $b\ge F_n+1$. Logo,

$a\ge F_n+2\ge {\phi }^{n+1}$

Aplicando o logaritmo em ambos os menbros, segue:

$(n+1)\log \phi \le \log a$

ou seja

$n\le \frac{\log a}{\log \phi }={\log }_{\phi }a$

Mas $\frac{1}{\log \phi }<5$, então:

$n\le \frac{1}{\log \phi }\cdot \log a<5{\log }_{\phi }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(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n)=\frac{{\phi }^n-{\hat{\phi }}^n}{\sqrt{5}}$

onde $\phi =\frac{1+\sqrt{5}}{2}$ e $\hat{\phi }=\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. Predefinição:Demonstração

Exercícios

1. Verifique, utilizando o princípio de indução, que:

   $\left[\begin{array}{c}{F}_{n+1}\\ F_n\end{array}\right]={\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]}^n\cdot \left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]$

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.