Cancellation Laws for Congruences
Published:
$ gcd(a,n)=1 \wedge ax \equiv ay \mod n \Rightarrow x \equiv y \mod n$
Statement
If $gcd(a,n)=1$ and $ax \equiv ay \mod n$, then we can assert that $x \equiv y \mod n$
Prove 1
Prove the existence of inverse element, i.e., $ gcd(a,p)=1 \Leftrightarrow \exists a^(-1), s.t. aa^(-1) \equiv 1 \mod p$