
# 3.2 Modular Arithmetic

[ "article:topic", "authorname:thangarajahp", "Modular Arithmetic", "Modulus", "remainder", "Reflexive Property", "Symmetric Property", "license:ccbyncsa", "showtoc:yes" ]

$$\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:

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

 + [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.