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

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

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:

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

Tem-se:

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

Demonstração
A verificação é direta, exigindo cálculos bastante simples.

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

Demonstração
Utilizando a fórmula de Binet, basta observar que o módulo de ${\hat {\varphi }}$ é menor que $1$, e consequentemente, quando $n\to \infty$, tem-se ${\hat {\varphi }}^{n}\to 0$

• $F_{n}\geq \varphi ^{n-1}$

Demonstração
A justificativa será dada por indução: $F_{1}=1\geq 1=\varphi ^{0}$ Se for verdade que $F_{n}\geq \varphi ^{n-1}$, então: $F_{n+1}=F_{n}+F_{n-1}\geq \varphi ^{n-1}+\varphi ^{n-2}=\varphi ^{n-2}(\varphi +1)=\varphi ^{n-2}\varphi ^{2}=\varphi ^{n}$

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

Demonstração

De fato, valem as seguintes equivalências: $\log \varphi <{\frac {1}{5}}\Leftrightarrow 5\log \varphi <1\Leftrightarrow \log \varphi ^{5}<1$ Mas $\varphi ^{5}=5\varphi +3$ (verifique a partir de $\varphi ^{2}=\varphi +1$), e $\varphi >{\frac {8}{5}}$ pois $\varphi >{\frac {8}{5}}\Leftrightarrow {\frac {1+{\sqrt {5}}}{2}}>{\frac {8}{5}}\Leftrightarrow 5(1+{\sqrt {5}})>16\Leftrightarrow 5{\sqrt {5}}>11\Leftrightarrow 125=25\cdot 5>121$ Sendo que esta última desigualdade é verdadeira.

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.

Demonstração

A relação entre os termos da sequência pode ser descrita matricialmente da seguinte forma: ${\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}={\begin{bmatrix}1&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}F_{n}\\F_{n-1}\end{bmatrix}}$ Para simplificar, será adotada a seguinte notação: $Q={\begin{bmatrix}1&1\\1&0\end{bmatrix}}$ A partir de um simples argumento de indução (veja exercício 1), obtem-se: ${\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}=Q^{n}\cdot {\begin{bmatrix}F_{1}\\F_{0}\end{bmatrix}}$ Neste ponto, recorre-se à Álgebra linear, para obter um jeito simples de calcular o produto acima. Se puder ser escrito ${\begin{bmatrix}1\\0\end{bmatrix}}=\alpha v+\alpha 'v'$, com $v$ e $v'$ sendo auto-vetores de $Q$, ou seja, vetores não nulos tais que $Qv=\lambda _{1}v$ e $Qv'=\lambda _{2}v'$, será possível obter: ${\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}=Q^{n}(\alpha v+\alpha 'v')=\alpha (Q^{n}v)+\alpha '(Q^{n}v')=\alpha (\lambda _{1}^{n}v)+\alpha '(\lambda _{2}^{n}v')$ A partir daí será bastante simples conseguir a fórmula explicita para $F_{n}$ (a segunda componente do vetor à esquerda), pois $v,v',\alpha ,\alpha ',\lambda _{1},\lambda _{2}$ seriam constantes. É, portanto, necessário determinar essas constantes, a começar pelos auto-valores de $Q$. Tem-se: ${\begin{bmatrix}1&1\\1&0\end{bmatrix}}\cdot {\begin{bmatrix}x\\y\end{bmatrix}}=\lambda {\begin{bmatrix}x\\y\end{bmatrix}}\Leftrightarrow \left\{{\begin{matrix}x&+&y&=&\lambda x\\x&&&=&\lambda y\end{matrix}}\right.$ Logo $\lambda y+y=\lambda ^{2}y$, ou seja, $(\lambda ^{2}-\lambda -1)\cdot y=0$ Assim, $y=0$ (que implica $x=0$) ou $\lambda ^{2}-\lambda -1=0$. 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: $\lambda _{1}=\varphi ={\frac {1+{\sqrt {5}}}{2}}$ $\lambda _{2}={\hat {\varphi }}={\frac {1-{\sqrt {5}}}{2}}$ Além disso, se $\lambda$ é raiz da equação, então para cada $y\not =0$, o vetor ${\begin{bmatrix}\lambda y\\y\end{bmatrix}}=y{\begin{bmatrix}\lambda \\1\end{bmatrix}}$ é um auto-vetor de $Q$. Em particular, se $y=1$, os auto-vetores correspondentes a cada raiz da equação quadrática são: $v={\begin{bmatrix}\varphi \\1\end{bmatrix}}$ $v'={\begin{bmatrix}{\hat {\varphi }}\\1\end{bmatrix}}$ De modo que $Qv=\varphi v$ e $Qv'={\hat {\varphi }}v'$ Resta escrever ${\begin{bmatrix}1\\0\end{bmatrix}}=\alpha v+\alpha 'v'$ conforme se pretendia. Isso é fácil, já que são conhecidos $v={\begin{bmatrix}\varphi \\1\end{bmatrix}}$ e $v'={\begin{bmatrix}{\hat {\varphi }}\\1\end{bmatrix}}$: $\left\{{\begin{matrix}1&=&\alpha \varphi &+&\alpha '{\hat {\varphi }}\\0&=&\alpha &+&\alpha '\end{matrix}}\right.$ Da segunda equação, segue que $\alpha '=-\alpha$. Substituindo esse valor na primeira equação, resulta: $1=\alpha \varphi -\alpha '{\hat {\varphi }}=\alpha (\varphi -{\hat {\varphi }})$ Como ${\hat {\varphi }}=1-\varphi$ (verifique!), tem-se $1=\alpha (\varphi -1+\varphi )=\alpha (2\varphi -1)=\alpha {\sqrt {5}}$. Logo, $\alpha ={\frac {1}{\sqrt {5}}}$. Assim, ${\begin{bmatrix}1\\0\end{bmatrix}}={\frac {1}{\sqrt {5}}}(v-v')$. Em consequência: ${\begin{bmatrix}F_{n+1}\\F_{n}\end{bmatrix}}=\alpha (\lambda _{1}^{n}v)+\alpha '(\lambda _{2}^{n}v')={\frac {1}{\sqrt {5}}}(\varphi ^{n}{\begin{bmatrix}\varphi \\1\end{bmatrix}})-{\frac {1}{\sqrt {5}}}({\hat {\varphi }}^{n}{\begin{bmatrix}{\hat {\varphi }}\\1\end{bmatrix}})$ Em particular, escrevendo a igualdade entre as segundas coordenadas desses vetores, obtem-se a fórmula desejada: $F_{n}={\frac {1}{\sqrt {5}}}(\varphi ^{n}-{\hat {\varphi }}^{n})$

Exercícios

1. 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}}$

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.