Demostrar si $\gcd(c,m)=1$ entonces $\{x\in \Bbb Z \mid ax\equiv b \pmod m\} =\{x\in \Bbb Z \mid cax\equiv cb \pmod m\}$

Question

Bien, estoy confundido sobre cómo enfocar esta pregunta.

Si $\gcd(c,m)=1$ entonces $S=T$ donde $S=\{x\in \Bbb Z \mid ax\equiv b \pmod m\}$ y $T=\{x\in \Bbb Z \mid cax\equiv cb \pmod m\}$ .

Sé que desde $c$ y $m$ son coprimos, entonces existen dos enteros $y$ y $z$ tal que $cy+mz=1$ . Además, sé que para probar $S = T$ Necesito demostrar que $S\subseteq T$ y $T\subseteq S$ .

Pero estoy atascado aquí y no sé cómo proceder. Cualquier ayuda sería muy apreciada. Gracias.

Answer 1

Sugerencia $\ {\rm mod}\ m\!:\,\ ax\equiv b\,\overset{\large {\rm times}\ c}\Rightarrow\,cax\equiv cb.\,$ Por el contrario, por Bezout, $\,\gcd(c,m) = 1\,\Rightarrow\, c^{-1}\,$ existe, por lo que la dirección opuesta se sigue multiplicando $\ cax\equiv cb\,$ por $\,c^{-1}$ para cancelar $\,c.$

Nota: $\ $ Generalmente, al escalar una ecuación por una unidad (invertible) se obtiene una ecuación equivalente.

Answer 2

Una pista: Por la mencionada identidad de Bezout, $y$ es un inverso multiplicativo de $c$ , modulo $m$ .

Answer 3

Puede ser que valga la pena afirmar y probar Bezut aquí. El lema de Bezut dice que si $(a,b)=1$ entonces $\exists x,y$ st $ax+by=1$ . Para demostrarlo, consideremos el conjunto $S:=\{d>0|\exists x,y,ax+by=d\}$ . Dejemos que $d_0$ sea el elemento mínimo de este conjunto y utilizar el algoritmo de división en $a$ y $d_0$ para descubrir que $d_0|a$ (En concreto, el resto es de la forma de elementos de $S$ pero es menor que el menor elemento de $S$ por lo que el resto es cero). A continuación, repite con $b$ y concluye $d_0=1$