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?

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$

