Algoritmo de Euclides Reformatar


Número de divisões necessárias

Representemos por \(\left(f_{n}\right)_{n\in\mathbb{N}}\) a sucessão de Fibonacci \(1,1,2,3,5,8,13,21,...\)

Para verificarmos que

(P) O número de divisões necessárias ao algoritmo para encontrar o máximo divisor comum entre dois naturais não excede cinco vezes o número de dígitos do menor deles

vamos utilizar os seguintes resultados:

Para ver a demonstração deste resultado, clique aqui

Sejam \(a\) e \(b\) naturais. Se \(a=b\), o algoritmo dá a resposta numa etapa e \(1\leq5\). Note-se que se o algoritmo dá a resposta ao fim de uma divisão é porque \(b\) é múltiplo de \(a\) e (P) é válido.

Se \(a<b\) e \(a\) tem \(k\) dígitos, então \(a<10^{k}\).

Se o algoritmo de Euclides requer \(n\geq2\) divisões, sabemos pelo resultado 1 que \(a\geq f_{n+1}\). E portanto devemos ter \[10^{k}> f_{n+1}.\]

Para todo \(m>2\), \(f_{m}>\left(\frac{8}{5}\right)^{m-2}\) .

Pelo resultado 2, temos que, como \(n\geq3\) , \(n>2\) e o resultado 2 é válido para \( f_{n+1}\), \(f_{n+1}>\left(\frac{8}{5}\right)^{n-1}\).

Assim, \[10^{k}>f_{n+1}>\left(\frac{8}{5}\right)^{n-1}\]e, como \(\left(\frac{8}{5}\right)^{5}>10\), vem \[10^{5k}>\left[\left(\frac{8}{5}\right)^{5}\right]^{n-1}>10^{n-1}\]

Portanto \[\begin{array}{cl} & 5k>n-1\Leftrightarrow\\ \Leftrightarrow & 5k+1>n\Leftrightarrow\\ \Leftrightarrow & 5k\geq n \end{array}\] que era o resultado que queríamos provar.

(Note-se que este raciocínio não seria aplicável se substituirmos \(5\) por um número \(j<5\), porque \(\left(\frac{8}{5}\right)^{j}<10\) se \(1\leq j<5\).)

Que não há outro raciocínio que permite "baixar" o factor \(5\) no enunciado dado, mostra-o o facto de o cálculo do \(mdc\left(f_{6},f_{7}\right)=mdc(8,17)\) com o algoritmo de Euclides exigir \(5\) divisões.

O factor \(5\) é, pois, o melhor possível naquele enunciado.