Simple proof of: if $axequiv ay pmod{m}$, and $gcd(a,m)=1$, then $xequiv y$

The quick proofs all use that $ax equiv ay pmod m$ is equivalent to $m | (ax - ay) = a(x - y)$.

If $m$ divides $a(x - y)$, and $m$ has no factors in common with $a$ (by hypothesis $gcd(a, m) = 1$), then it must be that $m | (x - y)$.

But that's equivalent to $x equiv y pmod m$. QED.

I didn't really understand our OP K_M's attempted proof; I do it like this:

given that

$ax equiv ay pmod m, tag 1$

we have

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

and given that

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

we also have

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

which is basically Bezout's identity; then multiplying this by $x - y$ yields

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

by (2),

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

and obviously

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

thus via (5),

$m mid x - y, tag 9$

which by definition means

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

The proof you gave may have a flaw: if $1=gcd(a,m)=ax=ay$, then $|a|=|x|=|y|=1$, which is not the case. By Bezout's Identity, from $ ax=ay+mp$ and $ay=ax+mr$, we can only imply $ax$ and $ay$ are multiplier of $gcd(a,m)$

The proposition you stated is a special case of a general proposition:

if $axequiv ay (mod$ $m)$, then $xequiv y(mod$ $frac{m}{gcd(a,m)})$

Proof:

With the assumption we can have $m|a(y-x)$, therefore $frac{m}{gcd(a,m)}|frac{a}{gcd(a,m)}(y-x)$, which implies $frac{m}{gcd(a,m)}|(y-x)$. i.e $xequiv y(mod$ $frac{m}{gcd(a,m)})$

This is basically due to Euclid's Lemma(which can be proven with Bezout's Identity):

if $a|bc$ and $gcd(a,b)=1$, then $a|c$