Properties of Congruence

Theorem
Let  
\[n\]
  be a fixed positive integer and let  
\[a, \; b, \; c, \; d\]
  be any integers. Then
a)  
\[a \equiv a \; (mod \; n)\]

b)  
\[a \equiv b \; (mod \; n) \rightarrow b \equiv a \; (mod \; n)\]

c)  
\[a \equiv b \; (mod \; n), \; b \equiv c \; (mod \; n) \rightarrow a \equiv c \; (mod \; n)\]

d)  
\[a \equiv b \; (mod \; n), \; c \equiv d \; (mod \; n) \rightarrow a+c \equiv b+d \; (mod \; n)\]

e)  
\[a \equiv b \; (mod \; n), \; c \equiv d \; (mod \; n) \rightarrow a+c \equiv ac=bd \; (mod \; n)\]

f)  
\[a \equiv b \; (mod \; n), \; r \in \mathbb{Z}^{{}+{}} \rightarrow a^r \equiv b^r \; (mod \; n)\]

Proof
a)  
\[a-a= 0 \times n \rightarrow a \equiv a \; (mod \; n)\]

b)  
\[a \equiv b \; (mod \; n) \rightarrow a=b+kn \rightarrow b=a-kn \rightarrow b \equiv a \; (mod \; n)\]

c)  
\[a \equiv b \; (mod \; n) \rightarrow a=b+rn\]

\[b \equiv c \; (mod \; n) \rightarrow b=c+sn\]

Then  
\[a=c+rn+sn=c+(r+s)n \rightarrow a \equiv c \; (mod \; n)\]

d)  
\[a \equiv b \; (mod \; n) \rightarrow a=b+rn\]

\[c \equiv d \; (mod \; n) \rightarrow c=d+sn\]

\[a+c=b+d+rn+sn=b+d+(r+s)n \rightarrow a+b=c+d \; (mod \; n)\]

e)  
\[a \equiv b \; (mod \; n) \rightarrow a=b+rn\]

\[c \equiv d \; (mod \; n) \rightarrow c=d+sn\]

\[ac=(b+rn(d+sn)=bd+(dr+bs+rsn)n \rightarrow ac=bd \; (mod \; n)\]

f) The case  
\[r=1\]
  is trivial. Suppose the result is true for  
\[r=k\]
  so that  
\[a^k=b^k \; (mod \; n)\]
  then  
\[a^{k+1}=aa^k \equiv bb^k \; (mod \; n)* \equiv b^{k+1} \; (mod \; n)\]
  *by e) Hence proved by induction.

Add comment

Security code
Refresh