# de soluciones a congruencias lineales

Question

En todas las pruebas que he visto que la ecuación $$ax\equiv b\pmod{m}$$ tiene $\gcd(a, m$ ) si $\gcd(a,m)\mid b$ el autor demuestra que existe una solución $r$ suponiendo que exista otra solución $s$ y luego demuestra que, para cualquier $t\in \{0,1,\dots, m-1\}$ , $s+t\cdot\frac{m}{\gcd(a,m)}$ es otra solución.

Con lo que tengo problemas es con la suposición de que existe otra solución $s$ ¿No tenemos que demostrarlo también?

Answer 1

Empecemos por $ax \equiv b \bmod m$ .

Sea $g=\gcd{(a,m)}$ . Supongamos que $g \mid b$ . Entonces $\dfrac ag x \equiv \dfrac bg \, \bmod{\dfrac mg}$ .

Tenga en cuenta que $\bigg(\dfrac ag \bigg)^{-1}$ e $\operatorname{gcd}\bigg(\dfrac ag, \dfrac mg \bigg)=1$ .

Entonces $x \equiv \dfrac bg\bigg(\dfrac ag \bigg)^{-1} \operatorname{mod}\bigg(\dfrac mg \bigg)$

Sea $s$ es el único número entero tal que $0 \le s \lt \dfrac mg$ y $s \equiv \dfrac bg\bigg(\dfrac ag \bigg)^{-1} \operatorname{mod}\bigg(\dfrac mg \bigg)$

Entonces tenemos $x \equiv s \operatorname{mod}\bigg(\dfrac mg \bigg)$ lo que equivale a $x = s + t\bigg(\dfrac mg \bigg)$ .

Si deseamos $0 \le s \lt m$ entonces tenemos que exigir $t = 0,1,\dots,g-1$ no, como dijiste, $m-1$ .