Puede $a \equiv x \cdot b$ (mod $m$ ) para $x$ ?

Question

Supongamos que tengo $a \equiv x \cdot b$ (mod $m$ ) y conozco el valor de $a, b, m$ .
El valor de $m$ es de la forma $2^n$ (No sé si eso ayuda)...

Quiero saber si existe un valor único de $x$ en $[0, m -1)$ que satisfaga la ecuación. Y si es así, ¿cómo la obtengo?

Esto es lo que he hecho hasta ahora:

Primero consideré $a$ y $b$ entre $0$ y $m-1$

$a \equiv x \cdot b$ (mod $m$ )
$$m | (bx - a)$$ $$bx - a = km$$ $$x = \frac{km + a}{b}$$ Desde $x$ oscila entre $0$ a $m-1$ , $k$ debe ser de $0$ a $b-1$

No sé cómo proceder a partir de ahora...

Answer 1

Para resolver $$ a\equiv xb\pmod{m}\tag{1} $$ podemos resolver $$ xb+ym=a\tag{2} $$ que requiere $\gcd(b,m)\mid a$ . Por lo tanto, nos gustaría resolver $$ x\frac{b}{\gcd(b,m)}+y\frac{m}{\gcd(b,m)}=\frac{a}{\gcd(b,m)}\tag{3} $$ Para resolver $(3)$ podemos utilizar Algoritmo euclidiano ampliado . En esta respuesta .

Answer 2

Esta ecuación tiene una solución única si y sólo si $b$ es una unidad módulo $m$ lo que ocurre si y sólo si $b$ y $m$ son coprimos.

Existe un algoritmo rápido para encontrar la solución: Algoritmo de Euclides .