Simple proof of: if $ax\equiv ay \pmod{m}$, and $\gcd(a,m)=1$, then $x\equiv y$ I'm working on a proof of: "if $ax\equiv ay \pmod{m}$, and $\gcd(a,m)=1$, then $x\equiv y\pmod{m}$". Here's what I have so far:
Suppose $ax\equiv ay\pmod{m}$, and $\gcd(a,m)=1$
By definition, $ax = ay + mp$ for some $p\in\mathbb{Z}$
By definition, $ay = ax + mr$ for some $r\in\mathbb{Z}$
By Bezout's identity, it must be that $\gcd(a,m) = ax$
Similarly, it must be that $\gcd(a,m) = ay$
Therefore, $ax = ay$
Obviously, $x=y$
Q.E.D.
Is this ok?
 A: 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 $ax\equiv ay (mod$ $m)$, then $x\equiv 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 $x\equiv 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$

A: 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.
A: 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}$
