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.2: Modular Arithmetic

  • Page ID
    7321
  •  
    \( \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}}\)

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

    Theorem 5 :

    Let \( a, b, c,d, \in \mathbb{Z}\) such that \(a \equiv b (mod\,n) \) and \(c \equiv d (mod\, n). \) Then \((a+c) \equiv (b+d)(mod\, n).\)

    Proof:

    Let \(a, b, c, d \in\mathbb{Z}\), such that \(a \equiv b (mod\, n) \) and \(c \equiv d (mod \,n). \)

    We shall show that \( (a+c) \equiv (b+d) (mod\, n).\)

    Since \(a \equiv b (mod\, n) \) and \(c \equiv d (mod\, n), n \mid (a-b)\) and \(n \mid (c-d)\)

    Thus \( a= b+nk, \) and \(c= d+nl,\) for \(k \) and \( l \in \mathbb{Z}\).

    Consider\( (a+c) -( b+d)= a-b+c-d=n(k+l), k+l \in \mathbb{Z}\).

    Hence \((a+c)\equiv (b+d) (mod \,n).\Box\)

    Theorem 6:

    Edit section

    Let \( a, b, c,d, \in \mathbb{Z}\) such that \(a \equiv b (mod \, n) \) and \(c \equiv d (mod \,n). \) Then \((ac) \equiv (bd) (mod \,n).\)

    Proof:

    Let \(a, b, c, d \in \mathbb{Z}\), such that \(a \equiv b (mod\, n) \) and \(c \equiv d (mod \, n). \)

    We shall show that \( (ac) \equiv (bd) (mod\, n).\)

    Since \(a \equiv b (mod \,n) \) and \(c \equiv d (mod\, n), n \mid (a-b)\) and \(n \mid (c-d)\)

    Thus \( a= b+nk, \) and \(c= d+nl,\) for \(k\) and \( l \in \mathbb{Z}\).

    Consider \( (ac) -( bd)= ( b+nk) ( d+nl)-bd= bnl+dnk+n^2lk=n (bl+dk+nlk), \) where \((bl+dk+nlk) \in \mathbb{Z}\).

    Hence \((ac) \equiv (bd) (mod \,n).\Box\)

    Theorem 7:

    Let  \(a, b \in\) \(\mathbb{Z}\) such that \(a \equiv b (mod \, n) \). Then \(a^2 \equiv b^2 (mod \, n).\)

    Proof:

    Let \(a, b \in\) \(\mathbb{Z}\), and n \(\in\) \(\mathbb{Z_+}\), such that \(a \equiv b (mod \, n).\)

    We shall show that \(a^2  \equiv b^2 (mod \, n).\)

    Since \( a \equiv b (mod \, n), n\mid (a-b).\)

    Thus \( (a-b)= nx,\)  where \(x \in\) \(\mathbb{Z}\).

    Consider \((a^2 - b^2) = (a+b)(a-b)=(a+b)(nx), = n(ax+bx), ax+bx \in \mathbb{Z}\).

    Hence \(n \mid a^2 - b^2,\)  therefore \(a^2 \equiv b^2 (mod \, n).\) \(\Box\)

    Theorem 8:

    Let \(a, b \in\) \(\mathbb{Z}\) such that \(a \equiv b (mod \, n)\). Then \(a^m \equiv b^m (mod \, n)\), \(\forall \in\) \(\mathbb{Z}\).

    Proof:

    Exercise.

    Example \(\PageIndex{1}\): \( mod\, 3\) Arithmetic

    Let \(n = 3\).

    Addition

    + [0] [1] [2]
    [0] [0] [1] [2]
    [1] [1] [2] [0]
    [2] [2] [0] [1]

    Multiplication

    x [0] [1] [2]
    [0] [0] [0] [0]
    [1] [0] [1] [2]
    [2] [0] [2] [1]

    Example \(\PageIndex{2}\):  \( mod\, 4\) Arithmetic

    Let \(n=4\).

    x [0] [1] [2] [3]
    [0] [0] [0] [0] [0]
    [1] [0] [1] [2] [3]
    [2] [0] [2] [0] [2]
    [3] [0] [3] [2] [1]

     

    Example \(\PageIndex{3}\):

    Find the remainder when \((101)(103)(107)(109)\) is divided by \( 11.\)

    Answer:

    \(101 \equiv 2 (mod \, 11)\)

    \(103 \equiv 4 (mod \, 11)\)

    \(107 \equiv 8 (mod \, 11)\)

    \(109 \equiv 10 (mod \,11)\).

    Therefore,

    \((101)(103)(107)(109) \equiv (2)(4)(8)(10) (mod \,11) \equiv 2 (mod \,11)\).

    Example \(\PageIndex{4}\):

    Find the remainder when\( 7^{1453}\) is divided by \( 8.\)

    Answer:

    \(7^0 \equiv 1 (mod \, 8)\)

    \(7^1 \equiv 7 (mod \, 8)\)

    \(7^2 \equiv 1 (mod \, 8)\)

    \(7^3 \equiv 7 (mod \, 8)\),

    As there is a consistent pattern emerging and we know that \(1453\) is odd, then \(7^{1453} \equiv 7 (mod \, 8)\) . Thus the remainder will be \(7.\)

     

    Example \(\PageIndex{5}\):

    Find the remainder when \(7^{2020}\) is divided by \(18.\)

    Example \(\PageIndex{6}\):

    Find the remainder when \( 26^{1453} \) is divided by \( 3.\)

    Odd and Even integers:

    An integer \( n\) is even iff \( n\equiv 0(mod \, 2).\)

    An integer \( n\)  is odd iff  \(n\equiv 1(mod \, 2).\)

    Two integers a and b are said to have some parity if they are both even or both odd otherwise a and b are said to have different parity.

    Example \(\PageIndex{6}\):

    Show that the sum of an odd integer and an even integer is odd.

    Answer:

    Proof: Let \(a\) be an odd integer and let \( b \) be an even integer. We shall show that \( a+b\) is odd by using the language of congruency.

    Since \(a\) is odd, \(a \equiv 1 (mod \, 2).\)

    Since \(b \) is even, \( b \equiv 0 (mod \, 2).\)

    Then \((a+b) \equiv (1+0)(mod \, 2),\)

    \((a+b) \equiv 1 (mod \, 2).\)

    Hence  \(a+b\) is odd.\(\Box\)

     

    Example \(\PageIndex{7}\):

    Show that the product of an odd integer and an even integer is even.

    Answer:

    Proof: Let \(a\) be an odd integer and let \(b\) be an even integer. We shall show that \(ab\) is even by using the language of congruency.

    Since \(a\) is odd, \(a \equiv 1 (mod \, 2).\)

    Since \(b \) is even, \( b \equiv 0 (mod \, 2).\)

    Then \((ab) \equiv (1)(0)(mod \, 2),\)

    \((ab) \equiv 0 (mod \, 2).\)

    Hence  \(ab\) is even.\(\Box\)

    Example \(\PageIndex{8}\):

    Show that \( n^2+1 \) is not divisible by \(3\) for any integer \( n.\)

    Answer:

    Proof: Let  \(n \in \mathbb{Z} \). We shall show that \( (n^2+1) \) is not divisible by \(3 \) using the language of congruency.

    We shall show that \( (n^2+1)(mod \,3) \not \equiv 0 \) by examining the possible cases.

    Case 1: \(n \equiv 0 (mod \, 3).\)

    \(n^2 \equiv 0^2 (mod \,3).\)

    \((n^2+1) \equiv 1 (mod \,3).\)

     Hence \(n^2+1\) is not divisible by \(3.\)

    Case 2: \(n \equiv 1 (mod \, 3).\)

    \(n^2 \equiv 1^2 (mod \,3).\)

    \((n^2+1) \equiv 1 (mod \,3).\)

     Hence \(n^2+1\) is not divisible by \(3.\)

    Case 3: \(n \equiv 2 (mod \, 3).\)

    \(n^2 \equiv 2^2 (mod \,3) \equiv 1 (mod \,3).\)

    \((n^2+1) \equiv 2 (mod \,3).\)

     Hence \(n^2+1\) is not divisible by \(3.\)

    Since none of the possible cases is congruent to \(0 (mod \, 3), n^2+1  \) is not divisible by \(3.\) \(\Box\)

     

    Example \(\PageIndex{9}\):

    Show that \(5 \mid a^2+4a\) for any integer \(a.\)

    Answer:

    Let  .

    We shall show that  

    Then   and

    We will proceed by examining the  5 possible cases of \( . \)  Specifically,  .

    Case  : If   then   

        .  

    Thus .

    Case : If then  

        .

    Thus .

    Case :  If then  

        

       .

    Thus .

    Case : If then

        

        .

    Thus .

    Case : If then

         

        .

    Thus .

    Having examined all possible cases, .◻

     

    Answer:

    Let where and .

    Then .

    Thus .  Rearranging, we obtain .

    Consider

                     

            

            .

    Let

    Since , then .

    Thus .

    Clearly, .  We shall examine the possible cases of .

    Case b=0: If then .  Thus .

    Case b=1: If then and where q .

    Thus .

    Case b=2:  If then and .  

    Thus .

    Case b=3: If then and .

    Thus .

    Case b=4: If then and .

    Thus .

     

    Having examined all possible cases, .◻

    Example \(\PageIndex{10}\)

    For every positive integer , prove that is divisible by .

    Answer:

    Proof:

    Let be the statement .

    says that .

    says that .  Since and , is true.

    Assume is true for some .

    We will show that is true.

    Specifically, we will show that .

    Consider that

           

           

           

           .

    Since , .

    Let .

    Thus .

    Having shown the inductive step, for every positive integer , is divisible by .

     

    ISBN Check Digit

    ISBN is the abbreviation for the International Standard Book Number. ISBN numbers are 10 digits in length. In an ISBN of the form X-XX-XXXXXX-X:

    • The first block of digits on the left represents the language of the book (0 is used to represent English).
    • The second block of digits represents the publisher.
    • The third block of digits represents is the number assigned to the book by the publishing company.
    • The fourth block consists of the check digit.

    Consider the ISBN 0-13-190190-?

    To determine the check digit for this Book Number, follow the below steps.

    Step 1: Multiply all nine assigned digits by weighted values. The weighted values are 1 for the first digit from the left, 2 for the second digit, three for the third digit, etc.

    \(1*0 + 2*1 + 3*3 + 4*1 + 5*9 + 6*0 + 7*1 + 8*9 + 9*0 = 139\).

    Step 2: ISBN uses \( (mod \, 11)\)  to determine the check digit. So  \(139 = 11(11) +  7 \) so  \(139 \equiv 7 (mod \,11)\). Hence the check digit is \(7\). Note that \(X\) is used for \(10\).

    If someone orders a book by the ISBN number then the check digit is a way of ensuring that the number was reported and recorded correctly so that the correct book is obtained.