¿Cuál es la mejor manera de resolver ecuaciones aritméticas modulares como$9x \equiv 33 \pmod{43}$?

Question

¿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!

Answer 1

¿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$.

Answer 2

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.