Skip to main content
\(\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}}\)
Mathematics LibreTexts

3.1 Modulo Operation

  • Page ID
    7454
  • [ "stage:draft", "article:topic", "license:ccbyncsa", "showtoc:yes" ]

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    Definition

    Modular Arithmetic begins with a modulus "\(n\)", \(n\) must be a member of  \(\mathbb{Z_+}\) . 

    Modulus "\(n\)" divides all the integers into congruent or residue classes. These classes are determined by the remainder after division. 

    The modulus must always be set in advance; for example n=2, n=5, n=15.

    Remainders are always \(0,\cdots, n-1.\)

    Let \(n \) \(\in\)   \(\mathbb{Z_+}\).

    Define a relation " \(\equiv\) "on  \(\mathbb{Z}\) by \( a \equiv  b \) (mod n)  iff (if and only if) \(m \mid  a-b \)  for all  \(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 will be 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).

     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.