Fórmula para calcular el $α$ y $β$ en $\gcd(a, b) = αa + βb$

Question

( $\gcd$ significa el máximo común divisor)

Así, sé que cuando se calcula el máximo común divisor, la respuesta se puede escribir como $\gcd(a, b) = a + b$ para algunos $$ and $$ . Mi pregunta es cuál sería una fórmula específica para calcular ambos valores.

Me dieron $a_k = _k · a + _k · b$ , donde $a_0, a_1, \ldots$ es la secuencia de valores producida por el Algoritmo Euclidiano. Tengo que utilizar de alguna manera $a_{k+1} = _{k+1} · a + _{k+1} · b$ para elaborar fórmulas de $a_{k+1}$ y $_{k+1}$ en términos de $k$ y $k - 1$ . No puedo averiguar cómo separar $a_{k+1}$ y $_{k+1}$ para crear dos fórmulas separadas, y después de trabajar con un problema usando el Algoritmo Euclidiano no vi ningún patrón que me ayudara con esto.

Answer 1

Me gustaría que la explicación de la ejemplo había ido directamente a la descripción de la matriz, que me parece de lo más transparente. Cuando se empieza con $(a,b)$ se obtiene un cociente y un resto $r$ para formar un nuevo par $(r,a)$ donde $r=b-qa$ . En la charla de la matriz, $$ \pmatrix{a\\r}=\pmatrix{0&1\\1&-q}\pmatrix{b\\a}\,. $$ Si intentas $\gcd(102,135)$ las matrices que se obtienen son, en primer lugar $\pmatrix{0&1\\1&-1}$ entonces $\pmatrix{0&1\\1&-3}$ y finalmente $\pmatrix{0&1\\1&-11}$ para terminar con $\pmatrix{3\\0}$ . Combinando, \begin{align} \pmatrix{3\\0}&=\pmatrix{0&1\\1&-11}\pmatrix{0&1\\1&-3}\pmatrix{0&1\\1&-1}\pmatrix{135\\102}\\ &=\pmatrix{-3&4\\34&-45}\pmatrix{135\\102}\,. \end{align} Y así $3=\gcd(102,135)=-3\cdot135+4\cdot102$ . Si se multiplican las matrices de derecha a izquierda, se ve que en realidad se obtiene la $-3$ y $4$ como la fila inferior de la penúltima matriz, pero no importa.

¿El resultado? Escribe tus cocientes, haz matrices antidiagonales con $0$ en el $(1,1)$ y los cocientes cambiados de signo en el $(2,2)$ lugar, pon tus matrices en el orden correcto, y multiplícalas. Y ya está.

Answer 2

Pero hay una fórmula más sencilla, pero utiliza la función totiente de Euler. $$\varphi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)$$

Así que si puedes factorizar x o y, tu tarea está hecha.

Digamos que tenemos (a,b)=d, a=md b=nd, por lo tanto xmd+ynd=d, $$xm+yn=1\space and \space (m,n)=1$$ $$xm=1\mod y$$ $$x^{\phi(y)}=1 \mod y $$ $$m=x^{\phi(y)-1} \mod y$$ $$mx=1\mod y$$ $$mx=1+ky$$ $$k=\frac{mx-1}{y}$$

Así que puedes usar esta fórmula: $$m=x^{\phi(y)-1} \mod y$$ $$k=\frac{mx-1}{y}$$ Pero hay que calcular $\phi(x)$ o cambiar x por y y encontrar $\phi(y)$ .

Answer 3

Echa un vistazo al Algoritmo Euclidiano ampliado.

Puedes probar una versión en vivo en WolframAlpha introduciendo "egcd(a,b)". Este Ejemplo devolverá

{1, {-3, 2}}

lo que significa $$ \gcd(7,11) = 1 = (-3) \cdot 7 + 2 \cdot 11 = s \cdot a + t \cdot b $$

En este ejemplo el Coeficientes de Bézout $s$ , $t$ aparecen en la penúltima fila del $s_i$ y $t_i$ resultados intermedios.