Erm … El libro de texto (?) Es realmente confuso, ya que no te da ejemplos. Creo que la foto que subiste se refiere a lo mismo que a continuación:
El algoritmo euclidiano extendido
Ese es en realidad mi algoritmo favorito, y no sé por qué no mucha gente lo sabe.
Básicamente está resolviendo esta ecuación:
- ¿Para qué valores del entero positivo n es posible dividir los primeros 3n enteros positivos en tres grupos, cada uno de los cuales tiene la misma suma?
- ¿Cómo sería un sistema imaginario modular?
- ¿Para qué enteros [matemática] a [/ matemática], [matemática] b [/ matemática], es [matemática] 4a ^ 2 + 1 = b ^ 2 [/ matemática] ??
- ¿Cuál es el resto cuando 301! está dividido entre 479?
- ¿Cada tentación de 3 además de [matemáticas] {} ^ 03 [/ matemáticas] y [matemáticas] {} ^ 13 [/ matemáticas] termina en un 7?
[matemáticas] am + bn = mcd (a, b) [/ matemáticas]
Si a y b no son números coprimos, los dividimos por su máximo divisor común para que estemos tratando con un caso un poco más simple:
[matemáticas] am + bn = 1 [/ matemáticas]
Estamos resolviendo los valores integrales de myn.
Usamos 113 y 289 como ejemplo. Realice primero el algoritmo euclidiano:
289… ..0
113 …… 2
63 …… .1
50 …… .1
13 …… .3
11 …… ..1
2 ……… 5
1 ……… .2
Ok, estamos seguros de que estos dos números son coprimos, pero nos enfocamos en la columna derecha, ya que el algoritmo Euclidiano Extendido solo se enfoca en la columna “cociente”.
Entonces comencemos.
0 …… 1 …… .0
2 …… 0 …… .1
Configuramos otras dos columnas , y las dos primeras filas son siempre 1,0,0,1 .
Luego calculamos el siguiente conjunto de números de esta manera:
0 ………… .1 ………………… .0
2 ………… .0 ………………… .1
1 …… 1–2 * 0 = 1 ………. 0–1 * 2 = -2
Básicamente tiene la enésima fila y (n + 1) th fila completa, luego para la (n + 2) th fila, tendrá la enésima fila + (n + 1) th fila veces (n + 1) th fila [cociente] . Tal vez esto no esté claro, así que hagámoslos todos (sin mostrar todos los pasos).
0 …… 1 …… 0
2 …… 0 …… 1
1 …… .1 …… -2
1 …….-1… ..3
3 …… 2 …… -5
1 …… -7 … ..18
5… ..9 …… -23
2 …..- 52 … ..133
Si usted consulta conmigo
[matemáticas] 289 \ veces (-52) +113 \ veces 133 = 1 [/ matemáticas]
Para darle una idea de cómo funciona esto (no voy a demostrarlo)
Si también considera la primera columna (la columna restante), entonces
[matemáticas] 289 \ veces 1 + 113 \ veces (-2) = 63 [/ matemáticas]
[matemáticas] 289 \ veces (-1) +113 \ veces 3 = 50 [/ matemáticas]
[matemáticas] 289 \ veces 2 + 113 \ veces (-5) = 13 [/ matemáticas]
y así.
Te dejaré que veas el patrón y demuestres cómo funciona.