Encontrar el menor $x$ tal que $ax\equiv b\mod m$

Question

Estoy buscando a resolver para $x$ en la ecuación

$ax\equiv b\mod m$

y quiero encontrar el más pequeño de $x$ que satisface esta. ¿Cómo puedo hacer esto, en el caso general? (Esto es para un problema de programación).

Lo que he hecho hasta ahora es tratar de calcular el inverso multiplicativo de a $a$ en el ring $\mathbb{Z}_m$, luego se multiplica este inversa con $b$ lo que efectivamente hace modular de la división de $b/a$. Pero el problema es que a veces $a$ no tiene un inverso multiplicativo en el anillo, mientras que la ecuación puede todavía ser resuelto. Por ejemplo,

$2x\equiv 2\mod 6$

trivialmente ha $x=1$ como la solución. Pero 2 no tiene inverso multiplicativo en $\mathbb{Z}_6$. Así que estoy un poco atascado. ¿Alguien tiene alguna sugerencia?

Answer 1

$2x\equiv 2\pmod{6}$ Si y sólo si $1x\equiv 1\pmod{3}$, donde dividimos por $gcd(a,m)$ en todo. Entonces habrá soluciones de $2$ (gcd) modulo $6$ (es decir, $1$ y $4$), pero ya que queremos que el más pequeño (probablemente ordenó como enteros positivos) esto no es un problema.