# 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$

Tags: