3.1: Modulo Operation (2024)

  1. Last updated
  2. 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 3.1: Modulo Operation (2). The relation \( \equiv \) on 3.1: Modulo Operation (3) by \( a \equiv b \) if and only if 3.1: Modulo Operation (4), is an equivalence relation. The Classes of 3.1: Modulo Operation (5) have the following equivalence classes:

    3.1: Modulo Operation (6).

    Example of writing equivalence classes:

    Example \(\PageIndex{3}\):

    The equivalence classes for \(( mod \, 3 )\) are (need to show steps):

    3.1: Modulo Operation (7) 3.1: Modulo Operation (8)3.1: Modulo Operation (9)3.1: Modulo Operation (10) 3.1: Modulo Operation (11) 3.1: Modulo Operation (12).

    3.1: Modulo Operation (13) 3.1: Modulo Operation (14) 3.1: Modulo Operation (15) 3.1: Modulo Operation (16) 3.1: Modulo Operation (17) 3.1: Modulo Operation (18).

    3.1: Modulo Operation (19)3.1: Modulo Operation (20) 3.1: Modulo Operation (21) 3.1: Modulo Operation (22)3.1: Modulo Operation (23) 3.1: Modulo Operation (24).

    Computational aspects:

    Finding "mod 5"

    %%python3print( "integer integer mod 5")for i in range(30): print(i, " ", i%5)

    Code \(\PageIndex{1}\) (Python):

    %%python3
    3.1: Modulo Operation (2024)
    Top Articles
    Latest Posts
    Recommended Articles
    Article information

    Author: Mrs. Angelic Larkin

    Last Updated:

    Views: 5838

    Rating: 4.7 / 5 (67 voted)

    Reviews: 90% of readers found this page helpful

    Author information

    Name: Mrs. Angelic Larkin

    Birthday: 1992-06-28

    Address: Apt. 413 8275 Mueller Overpass, South Magnolia, IA 99527-6023

    Phone: +6824704719725

    Job: District Real-Estate Facilitator

    Hobby: Letterboxing, Vacation, Poi, Homebrewing, Mountain biking, Slacklining, Cabaret

    Introduction: My name is Mrs. Angelic Larkin, I am a cute, charming, funny, determined, inexpensive, joyous, cheerful person who loves writing and wants to share my knowledge and understanding with you.