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
+ propriedades de \phi
m +exemplo matricial
Linha 156:
|align=right| <math>2 = \mathbf{1}\cdot2 + 0\,\!</math>
|}
Logo, <math>(13,8) = 1\,\!</math>. Aproveitando este exemplo, observe que:
:<math>\begin{bmatrix} 13 \\ 8 \end{bmatrix} = \begin{bmatrix} 13 & 8\\ 8 & 5 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} F_{5+2} & F_{5+1}\\ F_{5+1} & F_5 \end{bmatrix} \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{5+1} \cdot \begin{bmatrix} 1 \\ 0 \end{bmatrix}\,\!</math>
 
No entanto, se qualquer dos números for menor, o algoritmo requer menos etapas. Por exemplo, ao determinar <math>(13, 7)\,\!</math> tem-se: