Cancellation Laws for Congruences

less than 1 minute read

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$

Prove 2