Cancellation law of congruence and gcd.

Question

How $$ax ≡ ay\ (mod\ n)$$

==> $$x ≡ y\ (mod\ \frac{\ n}{gcd(a,n)})$$

How we got gcd here? Please assume I know nothing about ring theory.

Answer 1

You can write $ax\equiv ay\pmod n$ as $ax-ay=kn$ with integer $k$. Thus $a(x-y)=kn$. Now divide by $\gcd(a,n)$ to obtain

$$ \frac a{\gcd(a,n)}(x-y)=k\frac n{\gcd(a,n)}\;. $$

Since $\frac a{\gcd(a,n)}$ has no factors in common with $\frac n{\gcd(a,n)}$, it must divide $k$, so

$$ x-y=\frac{k\gcd(a,n)}a\frac n{\gcd(a,n)}\;. $$

This is

$$ x-y=k'\frac n{\gcd(a,n)} $$

with integer $k'$, so

$$ x\equiv y\,\left(\operatorname{mod}{\frac n{\gcd(a,n)}}\right)\;. $$