¿Cuál es la mejor manera de resolver ecuaciones como la siguiente:
$9x \equiv 33 \pmod{43}$
La única forma que conozco sería probar todos los múltiplos de$43$ y$9$ y comparar hasta obtener$33$ para el resto.
¿Hay alguna forma más eficiente?
¡La ayuda sería muy apreciada!
¿Cómo podemos resolverlo en $\mathbb{R}$? Dividir ambos lados por $9$ de curso, o en otras palabras, se multiplican ambos lados por el inverso multiplicativo de a $9$. Esta configuración no es diferente.
El reto aquí es saber el inverso multiplicativo de a$9$$\mathbb{Z}_{43}$. ¿Cuál es la clave de$^\dagger$ es que el $\gcd(9,43)=1$, lo que garantiza enteros $n$ $m$ tal que $9n + 43m = 1$. Modding por $43$, podemos ver que $9n \equiv 1 \pmod{43}$. Por lo tanto, multiplicando ambos lados de $9x \equiv 33 \pmod{43}$ $n$ nos da $x$.
Los enteros $n$ $m$ se pueden encontrar usando el algoritmo de Euclides extendido.
$^\dagger$ Este coprimality condición es si-y sólo si. Un entero $x$ no tiene un inverso multiplicativo $(\text{mod} \ n)$ si $\gcd(x,n) \neq 1$.
Generalmente, no hay una "mejor" manera. El algoritmo de Euclides extendido es una manera eficiente de algoritmos para calcular modular fracciones y inversos, pero a menudo no son más rápidos métodos para números pequeños.
A continuación se abigarrado métodos para calcular los $\ x\equiv \dfrac{33}9\equiv\dfrac{-10}9\:\pmod{\!43}$
Cancelar una unidad de $3$ entonces gire (= pruebe agregando $\,\pm 43\,$ al numerador para hacer la división exacta)
$$\dfrac{33}9\equiv \dfrac{11}3 \equiv \dfrac{54}3\equiv 18$$
Factor, a continuación, gire
$$\dfrac{-10}9\equiv \dfrac{-2}9\ \dfrac{5}1\equiv\dfrac{-45}9\ \dfrac{5}1\equiv -5\cdot 5\equiv 18$$
El algoritmo de Gauss con con
$$\dfrac{-10}9\equiv \dfrac{-50}{45}\equiv\dfrac{-7}2\equiv \dfrac{36}2\equiv 18$$
Algoritmo de Euclides extendido en forma fraccionada
$$\dfrac{0}{43}\ \desbordado{\large\ceño}\equiv \underbrace{\color{#c00}{\dfrac{-10}{9}}\ \desbordado{\large\ceño}\equiv \ \color{#90f}{\dfrac{7}{-2}}\ \desbordado{\large\ceño}\equiv\ \color{#0a0}{\dfrac{18}{1}}} _{\!\!\Grande \begin{align}\color{#c00}{-10}\ \ + \ \ &4(\color{#90f}{\ \ 7\ \ }) \ \ \ \equiv \ \ \color{#0a0}{18}\\ \color{#c00}{9}\ \ +\ \ &4(\color{#90f}{-2} )\ \ \ \ \equiv\ \ \ \color{#0a0}{1}\end{align}} $$
Cuidado con $\ $ Modulares de la fracción aritmética está bien definido sólo para las fracciones con denominador coprime para el módulo. Ver aquí para más discusión.
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.
