Nuestro profesor dice que hay un teorema tal que $GCD(a,b) = au + bv$ donde $u,v\in \mathbb Z$ Me pregunto cómo resolvería dicha ecuación. Por ejemplo:
¿Cómo podría resolver $GCD(821,123) = 821u + 123v$ o $GCD(231,1820) = 1820u + 231v$ ? El primer paso es, obviamente, utilizar el Algoritmo de Euclides para obtener el $GCD$ pero después de eso ¿cómo lo resuelvo?
Esta es la fórmula tal y como ella la expuso:
Una vez que tienes el GCD usando el algoritmo de Euclides ya has terminado, sólo tienes que "ir hacia atrás". Déjame aclararlo con un ejemplo.
Utilicemos $24$ y $136$ .
Ahora:
$136 = 24(5) + 16$
$24 = 16(1)+8$
$16 = 8(2)$
Así que el $GCD(24,136) = 8$ Yendo "hacia atrás" tenemos: $8 = 24 - 16(1) = 24 - ( 136 - 24(5)) = 24(6) + 136(-1)$ Comprueba la identidad de Bezout.
Utilice el llamado algoritmo euclidiano ampliado . Debo mencionar que una aplicación importante de este algoritmo es el cálculo de las inversiones modulares. Dado un número entero $n$ y un número entero $a$ relativamente primo a $n$ se puede utilizar el algoritmo euclidiano ampliado para encontrar $b$ tal que $ab \equiv 1 \pmod{n}$ (es decir, $n|ab-1$ ) - ¿ves cómo? (Utilice el hecho de que $(a,n)=1$ .)
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Una vez que tienes una solución, tienes todas las soluciones por sustitución. ¿Es esto lo que querías decir?
0 votos
Sobre la fórmula del título. Nos la acaban de dar en clase. Puedo publicar una captura de pantalla de las diapositivas de la conferencia si lo desea.