cómo resolver $min\{x \in \mathbb N_0 \quad |x \cdot 714\quad mod \quad 1972 \quad = \quad 1292 \quad mod \quad 1972 \}$ (ecuación del módulo)

Question

Pregunta : Cómo puedo resolver: $min\{x \in \mathbb N_0 \quad |x \cdot 714 \equiv 1292 \mod 1972 \}$ ?

Sólo sé sobre:

$x \cdot a \equiv _m b \Rightarrow m|x \cdot a - b$

una forma diferente de notación:

$min\{x \in \mathbb N_0 \quad | x \cdot 714 \equiv_{1972} 1292\}$

¿Cómo seguir?

Aprecio cada pista.

Answer 1

Como $714=34\cdot21$ , $1292=34\cdot 38$ , $1972=34\cdot 58$ esto equivale a resolver $21 x\equiv 38\mod 58$ .

Tenemos que encontrar la inversa de $21$ modulo $58$ . La herramienta para ello es el Algoritmo euclidiano ampliado : $$\begin{array}{rrrl} \hline r_i&u_i&v_i&q_i\\ \hline 58&0&1\\ 21&1&0&2\\ \hline 16&-2&1&1\\ 5&3&-1&3\\1&-11&4\\ \hline \end{array}$$ Así, la inversa de $21$ mod $58$ es $-11\equiv47$ . La solución es $$x\equiv47\cdot 38\equiv (-11)(-20)\equiv 46\mod 58.$$

Answer 2

Digamos que quiere resolver $ax \equiv b \mod{m}$ . Si $gcd(a,m)=1$ entonces hay una solución única. (Usted debe ser capaz de obtener esta solución)

Ahora bien, si $gcd(a,m) = d$ entonces la solución existe si $b$ divide $d$ . Debe intentar reducir esto a una ecuación entre $\frac{a}{d}, \frac{b}{d}$ y $\frac{m}{d}$ . A partir de esta solución, obtendrás múltiples soluciones para la ecuación inicial. ¿Puedes encontrar fácilmente el mínimo de eso?

Otra pista para la reducción - Resolución $ax \equiv b \mod{m}$ es lo mismo que resolver $ax = b + my$ .