Prueba sencilla: si $ax\equiv ay \pmod{m}$ y $\gcd(a,m)=1$ entonces $x\equiv y$

Question

Estoy trabajando en una prueba de: "si $ax\equiv ay \pmod{m}$ y $\gcd(a,m)=1$ entonces $x\equiv y\pmod{m}$ ". Esto es lo que tengo hasta ahora:

Supongamos que $ax\equiv ay\pmod{m}$ y $\gcd(a,m)=1$

Por definición, $ax = ay + mp$ para algunos $p\in\mathbb{Z}$

Por definición, $ay = ax + mr$ para algunos $r\in\mathbb{Z}$

Por la identidad de Bezout, debe ser que $\gcd(a,m) = ax$

Del mismo modo, debe ser que $\gcd(a,m) = ay$

Por lo tanto, $ax = ay$

Obviamente, $x=y$

Q.E.D.

¿Esto está bien?

Answer 1

La prueba que has dado puede tener un fallo: si $1=gcd(a,m)=ax=ay$ entonces $|a|=|x|=|y|=1$ lo que no es el caso. Por la identidad de Bezout, de $ ax=ay+mp$ y $ay=ax+mr$ sólo podemos implicar $ax$ y $ay$ son multiplicadores de $gcd(a,m)$

La proposición que has enunciado es un caso especial de una proposición general:

si $ax\equiv ay (mod$ $m)$ entonces $x\equiv y(mod$ $\frac{m}{gcd(a,m)})$

Prueba:

Con la hipótesis podemos tener $m|a(y-x)$ Por lo tanto $\frac{m}{gcd(a,m)}|\frac{a}{gcd(a,m)}(y-x)$ lo que implica $\frac{m}{gcd(a,m)}|(y-x)$ . es decir $x\equiv y(mod$ $\frac{m}{gcd(a,m)})$

Esto se debe básicamente al lema de Euclides (que puede demostrarse con la identidad de Bezout):

si $a|bc$ y $gcd(a,b)=1$ entonces $a|c$

Answer 2

Todas las pruebas rápidas utilizan que $ax \equiv ay \pmod m$ es equivalente a $m | (ax - ay) = a(x - y)$ .

Si $m$ divide $a(x - y)$ y $m$ no tiene factores en común con $a$ (por hipótesis $\gcd(a, m) = 1$ ), entonces debe ser que $m | (x - y)$ .

Pero eso equivale a $x \equiv y \pmod m$ . QED.

Answer 3

No entendí muy bien el intento de prueba de nuestro OP K_M; yo lo hago así:

dado que

$ax \equiv ay \pmod m, \tag 1$

tenemos

$m \mid ax - ay = a(x - y) ; \tag 2$

y dado que

$\gcd(a, m) = 1 \tag 3$

también tenemos

$\exists u, v \in \Bbb Z, \; au + mv = 1, \tag 4$

que es básicamente la identidad de Bezout; luego multiplicando esto por $x - y$ produce

$a(x - y)u + m(x - y)v = x - y; \tag 5$

por (2),

$m \mid a(x - y)u, \tag 6$

y obviamente

$m \mid m(x - y)v; \tag 7$

así vía (5),

$m \mid x - y, \tag 9$

que por definición significa

$x \equiv y \pmod m. \tag{10}$