Skip to main content
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}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    In this section, we will explore arithmetic operations in a modulo world.

    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.

    By using the above result we can solve many problems. Some of them are discussed below: 

    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 is \(7.\)

    Example \(\PageIndex{5}\):

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

    Answer

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

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

    \(7^2 \equiv 13 (mod \, 18)\)

    \(7^3 \equiv 1 (mod \, 18)\),

    As there is a consistent pattern emerging and we know that \(2020=(673)3+1\), \(7^{2020}= 7^{(673)3+1}=\left( 7^3\right)^{673}7^1 \equiv 7 (mod \, 18).\) Thus the remainder is \(7.\)

    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^5+4a\) for any integer \(a.\)

    Answer

    Notice that \(4 \equiv -1 (mod \, 5). \) Therefore, \(5 \mid a^5+4a \) iff \(5 \mid a^5-a\) for all integer \(a\).

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

    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.


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