# 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:

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 7^{1453} is divided by \( 8.\)

7^{0 }= 1 (mod 8)

7^{1 }= 7 (mod 8)

7^{2}= 1 (mod 8)

7^{3} = 7 (mod 8)

7^{4} = 1 (mod 8),

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

Example \(\PageIndex{5}\):

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

Example \(\PageIndex{6}\):

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

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.

## 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.**

__ 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.**

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

**Show that n ^{2}+1 is not divisible by 3 for any integer n.**

** 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).

Therefore 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\) 2 (mod 3)

Therefore n^{2}+1 \(\equiv\) 2 (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)

n^{2}+1\(\equiv\) 5 \(\equiv\) 2 (mod 3), hence n^{2}+ 1 is not divisible by 3.

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

Example \(\PageIndex{9}\):

Show that \(5\mid n^{2}+4n\) for any integer n.