Teoria de números/Máximo divisor comum: diferenças entre revisões
[edição não verificada] | [edição não verificada] |
Conteúdo apagado Conteúdo adicionado
+exercício e cat. |
+exemplos e seq. de fibonacci |
||
Linha 427:
* <math>r_{2j+1}<a/2^{j+1}\,\!</math>
-->
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á
:''
Veja alguns exemplos utilizando a representação matricial do algoritmo:
Linha 441 ⟶ 442:
:<math>\begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} q_0q_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_0q_1q_2+q_0+q_2 & q_0q_1+1\\ q_1 & 1 \end{bmatrix} \begin{bmatrix} d \\ 0 \end{bmatrix}\,\!</math>
É fácil perceber que <math>a\,\!</math> é mínimo quando cada <math>q_j = 1\,\!</math>,
Aplicando <math>q_j = 1\,\!</math> na fórmula de recorrência, tem-se:
Linha 448 ⟶ 449:
Isso lembra a fórmula que define a [[w:Sequência de Fibonacci|sequência de Fibonacci]], embora esteja "ao contrário".
{{CaixaMsg|tipo=revisão|texto=
Com um exemplo numérico ficará mais claro:▼
;Recordando:
A sequência de fibonacci é definida pelas seguintes equações:
* <math>F_0 = F_1 = 1\,\!</math>
* <math>F_k = F_{k-1} + F_{k-2}\,\!</math>
Assim, seus primeiros termos são: <math>1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots\,\!</math>
}}
* <math>\begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 2 & 1\\ 1 & 0 \end{bmatrix}\,\!</math>
* <math>\begin{bmatrix} 2 & 1\\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 3 & 2\\ 2 & 1 \end{bmatrix}\,\!</math>
* <math>\begin{bmatrix} 3 & 2\\ 2 & 1 \end{bmatrix} \cdot \begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 5 & 3\\ 3 & 2 \end{bmatrix}\,\!</math>
Segue, por um simples uso do princípio de indução, que:
:<math>\begin{bmatrix} \mathbf{1} & 1\\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_{n}\\ F_{n} & F_{n-1} \end{bmatrix}\,\!</math>
=== Fórmula de Binet ===
|