Call Us 07766496223
Theorem (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)\]