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

     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/(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/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\) m \(\in\) \(\mathbb{Z}\).

    Example \(\PageIndex{1}\):

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

    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.

    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 71453  is divided by \( 8.\)

    70 = 1 (mod 8)

    71 = 7 (mod 8)

    72= 1 (mod 8)

    73 = 7 (mod 8)

    74 = 1 (mod 8),

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

    Example \(\PageIndex{4}\):

    Find the remainder when 72018  is divided by \(18.\)

    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 a different parity.

     

    Example \(\PageIndex{2}\):

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

    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{3}\):

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

    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 be 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{4}\):

    Show that n2+1 is not divisible by 3 for any integer n.

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

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

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

    n2\(\equiv\) 02 (mod 3).

    n2+1\(\equiv\) 1 (mod 3).

    Therefore n2+1 \(\equiv\) 1 (mod 3), hence n2+1 is not divisible by 3.

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

    n2\(\equiv\) 12 (mod 3)

    n2+1\(\equiv\) 2 (mod 3)

    Therefore n2+1 \(\equiv\) 2 (mod 3), hence n2+1 is not divisible by 3.

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

    n2\(\equiv\) 22 (mod 3)

    n2+1\(\equiv\) 5 \(\equiv\) 2 (mod 3), hence n2+ 1 is not divisible by 3.

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

     

    Example \(\PageIndex{4}\):

    Show that  \(5\mid n2+4n\)  for any integer n.