Diferencia entre revisiones de «Algoritmo de Euclides»
Contenido eliminado Contenido añadido
Sin resumen de edición Etiquetas: posible problema posibles pruebas |
m Revertidos los cambios de 88.4.188.69 (disc.) a la última edición de 217.126.203.110 Etiqueta: Reversión |
||
Línea 125:
{{Ecuación | <math>\begin{bmatrix}s_i&t_i\\s_{i+1}&t_{i+1}\end{bmatrix}=\begin{bmatrix}0&1\\1&-q_i\end{bmatrix}\times \begin{bmatrix}0&1\\1&-q_{i-1}\end{bmatrix}\times\cdots\times \begin{bmatrix}0&1\\1&-q_1\end{bmatrix}</math>}}
▲i</math> y <math>t_i</math> tienen la propiedad de que <math>r_i=a s_i+b t_i</math>, es decir, expresan a <math>r_i</math> como una combinación lineal de <math>a</math> y <math>b</math>. Particularmente, como <math>\mathrm{mcd}(a,b)=r_{n+1}</math> entonces se tiene <math>\mathrm{mcd}(a,b)=a s_{n+1}+b t_{n+1}</math>, lo cual es la solución del problema. Esta propiedad no debería ser sorprendente, pues esta multiplicación de matrices equivale al método antes descrito donde se substituye cada ecuación en la anterior.<!--Pero no colocaré la demostración en una enciclopedia--> Es importante calcular <math>Q_i\times\cdots\times Q_3\times Q_2\times Q_1</math> en ese mismo orden. La matriz <math>Q_1</math> aparece en el extremo derecho y la matriz <math>Q_i</math> en el izquierdo.
Regresando al primer ejemplo, la sucesión de cocientes es <math>q_1=8</math>, <math>q_2=1</math> y <math>q_3=2</math>. Entonces se puede calcular
| |||