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}}\)
[ "stage:draft", "article:topic", "calcplot:yes", "license:ccbyncsa", "showtoc:yes", "transcluded:yes" ]
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}}} \)

    Definition

    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.

    Example \(\PageIndex{1}\):

    Add text here. For the automatic number to work, you need to add the "AutoNum" template (preferably at the end) to the page.