Teoria de números/Máximo divisor comum: diferenças entre revisões

Analisando a progressão geométrica dada anteriormente, conclui-se que algum de seus termos é menor do que um<math>1\,\!</math>. Nesse caso, o resto correspondente será nulo, e o algoritmo para. Para ser mais exato, como

:<math>\frac{a}{2^{x}} =< 1 \Leftrightarrow a =< 2^{x} \Leftrightarrow \log_2 a =< x \,\!</math>

o menor índice inteiro <math>t\,\!</math> que torna <math>\frac{a}{2^jt}\,\!</math> menor que um<math>1\,\!</math> é

Onde <math>[ \alpha ]\,\!</math> denota o maior inteiro que não supera <math>\alpha\,\!</math> (a ''[[w:Parte inteira|parte inteira]] de <math>\alpha\,\!</math>'').

MasEntão <math>r_{2t} < \frac{a}{2^{t+1}} < \frac{a}{2^{t}} < 1\,\!</math>, implicae queconsequentemente <math>r_{2t} = 0</math>, pois os restos são números inteiros não-negativos.

Assim, sesabendo que o algoritmo para exatamente quando <math>r_{k+1} = 0\,\!</math>, certamenteconlui-se que tal índice <math>k+1\,\!</math> não pode ser maior que o índice <math>2t\,\!</math>, ouem sejasímbolos:

Logo, <math>k+1 \le 2[\log_2 a] +1< 2(N\cdot\log_2 10) + 1)\,\!</math>, ou numericamente, <math>k \approx 6,6N\,\!</math>.

Embora muito útil, esta ainda não éseja a melhor aproximação para <math>k\,\!</math>, já é bastante útil, pois mostra que podeo sernúmero obtidade algebricamenteetapas cresce linearmente com o número de dígitos de <math>a\,\!</math>.