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á consideradoconsiderada oa problemaseguinte nos seguintes termosquestão:
 
:''SeQual é o algoritmomenor levavalor de <math>na\,\!</math> passos,para qualo équal o tamanhoalgoritmo mínimo deleva <math>an\,\!</math> passos?''
 
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>, poiscada entrada aparecemda polinômiosmatriz emé um polinômio nas variáveis <math>q_j\,\!</math> (que são positivas), e cujos coeficiêntes são <math>1\,\!</math> (se puder, acrescente uma justificativa mais formal).
 
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>
}}
 
Com umalguns exemploexemplos numériconuméricos ficará mais claro:
* <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>
 
{{Tarefa|Colocar um exemplo de n igual a 3, q_j sendo 1 e fazer o produto das matrizes}}
 
=== Fórmula de Binet ===