Skip to main content
Mathematics LibreTexts

3.1: Modulo Operation

  • 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}}} \)

    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"

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

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

    %%python3
    
    
    
    

    This page titled 3.1: Modulo Operation is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.