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 simplificando |
m atualizando sintaxe usada nas predefinições |
||
Linha 142:
* <math>b\ge F_{k+1}\,\!</math>
{{Teorema
|Dado <math>n\ge 1\,\!</math>, sejam <math>a\,\!</math> e <math>b\,\!</math> os <u>menores números</u> tais que o algoritmo de Euclides aplicado a <math>a\,\!</math> e <math>b\,\!</math> leva exatamente <math>n\,\!</math> passos, então <math>a=F_{n+2}\,\!</math> e <math>b=F_{n+1}\,\!</math>.
}}
Linha 188:
=== Teorema de Lamé ===
{{Teorema
|O número de passos (de divisões) no algoritmo de Euclides com entradas <math>u\,\!</math> e <math>v\,\!</math> é limitado superiormente por <math>5\,\!</math> vezes a quantidade de dígitos decimais em <math>min(u,v)\,\!</math>.
}}
| |||