Resuelva $43x\equiv 12 \pmod{56}$

Question

He leído un método para resolver la congruencia lineal $$43x\equiv 12 \pmod{56}$$ indirectamente de un libro. El método consiste en encontrar un sistema equivalente de congruencias y, a continuación, resolver el sistema para obtener una solución a la congruencia lineal original.

Para resolver $43x\equiv 12 \pmod{56}$ , el libro escribe que es equivalente al sistema $$x\equiv 5 \pmod{7}\qquad \text{and}\qquad 3x\equiv 4\pmod{8}.$$ Dado que cada elemento del grupo $(\mathbb{Z}/8\mathbb{Z})^*$ tiene orden 2, $3x\equiv 4\pmod{8}$ es equivalente a $x\equiv 4 \pmod{8}$ .

Tengo dos preguntas sobre esta equivalencia.

• En primer lugar, ¿cómo obtener un sistema de congruencias que sea equivalente a la congruencia lineal original?

• En segundo lugar, ¿por qué $3x\equiv 4\pmod{8}$ equivalente a $x\equiv 4 \pmod{8}$ porque los elementos de $(\mathbb{Z}/8\mathbb{Z})^*$ ¿tiene el pedido 2?

Agradeceremos cualquier ayuda.

Answer 1

Se puede obtener un sistema equivalente a partir del hecho de que si

$$43x\equiv 12 \pmod{56}$$

entonces

$$56 | 43x-12 \implies 7(8)|43x-12$$

donde $|$ significa divide por igual. Utilizamos $7$ y $8$ ya que $56$ es el mínimo común múltiplo de estos divisores. Así que

$$7|43x-12$$

y

$$8|43x-12$$

Entonces, puesto que $7|43x-12$ tenemos $7|42x+x-7-5$ Así que $7|x-5$ que da $x\equiv 5 \pmod 7$ . También de $8|43x-12$ tenemos $8|40x+3x-8-4$ Así que $8|3x-4$ y luego $3x\equiv 4 \pmod 8$ . No sé mucho de teoría de grupos, pero puedo responder a tu segunda pregunta sin teoría de grupos. Puesto que $8|3x-4$ , $8|3(3x-4)$ Así que $8|9x-12 \implies 8|8x+x-8-4 \implies 8|x-4$ Así que $x\equiv 4 \pmod 8$ .