- Congruence
- Let \(a,b,n \in \mathbb{Z}\) and \(n>0\). \(a\) and \(b\) are congruent modulo \(n\) if and only if \(n \vert \left(a-b \right)\) and it is written
$$a \equiv b\; (\text{mod }n) $$
- Algebraic Properties
-
- I. Reflexive: \( n \vert 0 \Rightarrow a \equiv a\; ( \text{mod }n) \)
- Proof: By definition \(n \vert 0 \) iff \( \exists k \in \mathbb{Z} \ni 0=nk\) and since \( 0=a-a=nk\) then by definition \(a \equiv a \; ( \text{mod }n) \)
- II. Symmetric: \( a \equiv b\; ( \text{mod }n)\ \Rightarrow b \equiv a \; ( \text{mod }n) \)
- Proof: By definition \( \left(a-b \right)=nk \) and \( -\left(b-a \right)=n \left(-k\right) \) which implies \(b \equiv a \; ( \text{mod }n) \)
- III. Transitive: If \( a \equiv b\; ( \text{mod }n) \) and \( b \equiv c \; ( \text{mod }n) \) then \( a \equiv c \; ( \text{mod }n) \)
- Proof: By definition \( \left(a-b \right)=nk\) and \( -\left(b-c \right)=nl\). Also, \(a=nk+b\) and \(c=b-nl\) and \(a-c=nk+b-b+nl=nk+nl=n \left(k+l \right)\) which implies \(a \equiv c\; ( \text{mod }n) \)
- IV. If \(a \equiv b\; ( \text{mod }n) \) and \(c \equiv d\; ( \text{mod }n) \) then \(a+c \equiv b+d\; ( \text{mod }n) \)
- Proof: By definition \( \left(a-b \right)=nk\) and \( \left(c-d \right)=nl\). Also, \(a=nk+b\) and \(c=d+nl\) and \(a+c=nk+b+d+nl=b+d+nk+nl=\left(b+d \right) + n\left(k+l\right)\) which implies \(a + c \equiv b + d \; ( \text{mod }n) \) since \(\left(a+c \right) – \left(b+d \right) = n\left(k+l\right).\)
- V. If \(a \equiv b\; ( \text{mod }n) \) and \(c \equiv d\; ( \text{mod }n) \) then \(a-c \equiv b-d\; ( \text{mod }n) \)
- Proof: By definition \( \left(a-b \right)=nk\) and \( \left(c-d \right)=nl\). Also, \(a=nk+b\) and \(c=d+nl\) and \(a-c=nk+b-d-nl=b-d+nk-nl=\left(b-d \right) + n\left(k-l\right)\) which implies \(a – c \equiv b – d\; ( \text{mod }n) \) since \( \left(a-c \right) – \left(b-d \right) = n\left(k-l\right).\)
- VI. If \(a \equiv b\; ( \text{mod }n) \) and \(c \equiv d\; ( \text{mod }n) \) then \(ac \equiv bd\; ( \text{mod }n) \)
- Proof: By definition \( \left(a-b \right)=nk\) and \( \left(c-d \right)=nl\). Also, \(a=nk+b\) and \(c=d+nl\) and \(ac=\left(nk+b\right)\left(d+nl\right)=dnk+n^2kl+bd+nbl=bd+n\left(dk+nkl+bl\right)\) which implies \(ac \equiv bd \; ( \text{mod }n) \) since \(ac – bd =n \left(dk+nk+bl\right)\)
- VII. If \(a \equiv b\; ( \text{mod }n) \) then \(a^k \equiv b^k\; ( \text{mod }n) \)
- Proof: By mathematical induction note that \( a^1 \equiv b^1\; ( \text{mod }n) \) is true by definition therefore, by the inductive hypothesis we assume \(a^t \equiv b^t \; ( \text{mod }n) \) to be true for all \(t\) contained in the natural numbers. It must be shown that \(a^{t+1} \equiv b^{t+1}\; ( \text{mod }n) \) is true. Notice \( aa^t=a^{t+1}\) and \( bb^t=b^{t+1}\). Since \( a \equiv b \; ( \text{mod }n)\ \) is true by definition and \(a^t \equiv b^t \; ( \text{mod }n) \) is true by the inductive hypothesis then by theorem VI \(a^{t+1} \equiv b^{t+1}\; ( \text{mod }n) \) is true.
- VIII. If \(n\) is a natural number expressed in base \(10\) as \( n= a_k a_{k-1} \cdots a_1 a_0 \) and \( m= a_k + a_{k-1} + \ldots + a_1 + a_0 \) then \( n \equiv m\; ( \text{mod }3) \)
- Proof: By definition \( n – m = 10^k a_k + 10^{k-1} a_{k-1} + \ldots + 10 a_1 + a_0 – a_k – a_{k-1} – \ldots – a_1 – a_0\). Simplifying and collecting like terms \(n – m = a_k \left( 10^k – 1 \right) + a_{k-1} \left( 10^{k-1} – 1 \right) + \ldots + a_1 \left ( 10 -1 \right)\) If \( 10^k \equiv 1^k \; (\text{mod }3) \) then \(n – m = a_k \left( 3t_k \right) + a_{k-1} \left( 3t_{k-1} \right) + \ldots + a_1 \left( 3t_1 \right)=3t \) where \( t = \left( a_kt_k + a_{k-1} t_{k-1} + \ldots + a_1 t_1 \right) \in \mathbb{Z}\) therefore, by definition \( n \equiv m \; ( \text{mod }3)\ \)
- IX. If \(n\) is a natural number expressed in base \(10\) as \( n= a_k a_{k-1} \cdots a_1 a_0 \) and \( m= a_k + a_{k-1} + \ldots + a_1 + a_0 \) then \( n \equiv m \; ( \text{mod }9) \)
- Proof: By definition \( n – m = 10^k a_k + 10^{k-1} a_{k-1} + \ldots + 10 a_1 + a_0 – a_k – a_{k-1} – \ldots – a_1 – a_0\). Simplifying and collecting like terms \(n – m = a_k \left( 10^k – 1 \right) + a_{k-1} \left( 10^{k-1} – 1 \right) + \ldots + a_1 \left ( 10 -1 \right)\) If \( 10^k \equiv 1^k \; ( \text{mod }9) \) then \(n – m = a_k \left( 9t_k \right) + a_{k-1} \left( 9t_{k-1} \right) + \ldots + a_1 \left ( 9t_1 \right)=9t\) where \( t = \left( a_kt_k + a_{k-1} t_{k-1} + \ldots + a_1 t_1 \right) \in \mathbb{Z}\) therefore, by definition \( n \equiv m \; ( \text{mod }9) \)