- Last updated
- Save as PDF
- Page ID
- 7454
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vectorC}[1]{\textbf{#1}}\)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}}\)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}\)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}}}\)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)
Definition: Modulo
Let \(m\) \(\in\) \(\mathbb{Z_+}\).
\(a\) is congruent to \(b\) modulo \(m\)denoted as \( a \equiv b (mod \, n) \), if \(a\) and \(b\)have the remainder when they are divided by \(n\), for \(a, b \in \mathbb{Z}\).
Example \(\PageIndex{1}\):
Suppose \(n= 5, \) then the possible remainders are \( 0,1, 2, 3,\) and \(4,\) when we divide any integer by \(5\).
Is \(6 \, \equiv 11 (mod \, 5)\)? Yes, because \(6\) and \(11 \) both belong to the same congruent/residue class \(1\). That is to say when \(6\) and \(11\) are divided by \(5\) the remainder is \(1.\)
Is \(7 \equiv 15(mod \, 5)\)? No, because \(7\) and \(15\) do not belong to the same congruent/residue class. Seven has a remainder of \(2,\) while \(15\) has a remainder of \( 0, \) therefore \(7 \) is not congruent to \( 15 (mod \, 5)\). That is \(7 \not \equiv 15(mod \, 5)\).
Example \(\PageIndex{2}\): Clock arithmetic
Find \(18:00\), that is find \(18 (mod \, 12)\).
Solution
\(18 mod(12) \equiv 6\). 6 pm.
Properties
Let \(n \in \mathbb{Z_+}\). Then
Theorem 1 :
Two integers \(a \) and \(b\) are said to be congruent modulo \( n\), \(a \equiv b (mod \, n)\), if all of the following are true:
a) \(m\mid (a-b).\)
b) both \(a\) and \(b \) have the same remainder when divided by \(n.\)
c) \(a-b= kn\), for some \(k \in \mathbb{Z}\).
NOTE: Possible remainders of \( n\) are \(0, ..., n-1.\)
Reflexive Property
Theorem 2:
The relation " \(\equiv\) " over \(\mathbb{Z}\) is reflexive.
Proof: Let \(a \in \mathbb{Z} \).
Then \(a-a=0(n)\), and \( 0 \in \mathbb{Z}\).
Hence \(a \equiv a (mod \, n)\).
Thus congruence modulo n is Reflexive.
Symmetric Property
Theorem 3:
The relation " \(\equiv\) " over \(\mathbb{Z}\) is symmetric.
Proof: Let \(a, b \in \mathbb{Z} \) such that \(a \equiv b\) (mod n).
Then \(a-b=kn, \) for some \(k \in \mathbb{Z}\).
Now \( b-a= (-k)n \) and \(-k \in \mathbb{Z}\).
Hence \(b \equiv a(mod \, n)\).
Thus the relation is symmetric.
Antisymmetric Property
Is the relation " \(\equiv\) " over \(\mathbb{Z}\) antisymmetric?
Counter Example: \(n\) is fixed
choose: \(a= n+1, b= 2n+1\), then
\(a \equiv b(mod \, n)\) and \( b \equiv a (mod \, n)\)
but \( a \ne b.\)
Thus the relation " \(\equiv\) "on \(\mathbb{Z}\) is not antisymmetric.
Transitive Property
Theorem 4 :
The relation " \(\equiv\) " over \(\mathbb{Z}\) is transitive.
Proof: Let \(a, b, c \in\) \(\mathbb{Z}\), such that \(a \equiv b (mod n)\) and \(b \equiv c (mod n).\)
Then \(a=b+kn, k \in\) \(\mathbb{Z}\) and \(b=c+hn, h \in\) \(\mathbb{Z}\).
We shall show that \(a \equiv c (mod \, n)\).
Consider \(a=b+kn=(c+hn)+kn=c+(hn+kn)=c+(h+k)n, h+k \in\) \(\mathbb{Z}\).
Hence \(a \equiv c (mod \, n)\).
Thus congruence modulo \(n\) is transitive.
Theorem 5:
The relation " \(\equiv\) " over \(\mathbb{Z}\) is an equivalence relation.
Modulo classes
Let 
. The relation \( \equiv \) on 
by \( a \equiv b \) if and only if 
, is an equivalence relation. The Classes of 
have the following equivalence classes:
.
Example of writing equivalence classes:
Example \(\PageIndex{3}\):
The equivalence classes for \(( mod \, 3 )\) are (need to show steps):
|
|
|
|
Computational aspects:
Finding "mod 5"
%%python3print( "integer integer mod 5")for i in range(30): print(i, " ", i%5)
Code \(\PageIndex{1}\) (Python):
%%python3
