Congruence Different Moduli - The Cancellation Rule
If
\[a \equiv b \; (mod \; m), a \equiv b \; (mod \; n)\]
then \[a \equiv b \; (mod \; lcm(m,n))\]
.Proof
From the definition of congruence there exist integers
\[r, \; s\]
such that\[a=b+rm, \; a=b+sn \rightarrow rm=sn\]
Let
\[d=gcd(m,n)\]
so that \[m=dm', \; n=dn'\]
and \[gcd(m',n')=1\]
.Substitute for
\[r, \; s\]
into \[rm=sn\]
to give \[RD'=sdn' \rightarrow rm'=sn'\]
.Then
\[n' | rm'\]
so from Euclid's Lemma \[n' | r\]
. Let \[r'=kn'\]
we have\[a=n+rm=b+kmn'=b+km (\frac{n}{d})=b+k(\frac{mn}{d})=b+lcm(m,n)\]
If
\[ab \equiv 0 \; (mod \; p)\]
then either \[a \equiv 0 \; (mod \; p), \; b \equiv 0 \; (mod \; p)\]
.The Cancellation Rule has an important corollary.
If
\[ca \equiv cb \; (mod \; n)\]
with \[gcd(c,n)=1\]
then \[a \equiv b \; (mod \; n)\]
.To see this
\[ca \equiv cb \; (mod \; n) \rightarrow ca=cb+kn \rightarrow a=b+ \frac{kn}{c}\]
\[gcd(c,n)=1 \rightarrow c | k \rightarrow a =b+ \frac{k}{c} n \rightarrow a \equiv b \; (mod \; n)\]
