Teoria de números/Eficiência do algoritmo de Euclides: diferenças entre revisões
| [edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
m →Teorema de Lamé: +tarefa pendente |
m +ligação |
||
Linha 24:
O algoritmo fornece <math>(a,b) = r_k\,\!</math>, que é o último resto não nulo, obtido em <math>k\,\!</math> passos (divisões).
Uma observação importante é que o [[Teoria de números/Divisibilidade#Algoritmo da divisão (de Euclides)|resto de uma divisão]] é sempre menor que a metade do dividendo:
:<math>r_0 = r_1q_0+r_2 \ge r_1+r_2 > 2r_2\,\!</math>
Sendo a primeira desigualdade válida porque <math>q_0\ge 1\,\!</math> e a segunda porque <math>r_1>r_2\,\!</math>. Deste modo, tem-se
Linha 187:
=== Teorema de Lamé ===
{{Teorema|texto=
O número de passos (de
}}
| |||