# Modular Arithmetic

**MODULAR ARITHMETIC**

**INTRODUCTION**:

**Definition : MODULAR CONGRUENCE**

"Let n be an integer greater than 1 . The notation a ≡ b (mod n) (1) will indicate that a and b are integers such that a - b is divisible by n. Statement (1) is called a modular congruence or simply a congruence and is read : ‘a is congruent to b, modulo n.' The integer is called the modulus of the congruence." (Keesee, 1965).

**Illustration:**

13 ≡ 8 mod 5 is a congruence. When 13 is divided by 5 it yields a remainder equal to 3. When 8 is divided by 5, it yields a remainder of 3. When 8 is subtracted from 13 the difference is 5 and 5 mod 5 = 0, which means that if 5 is divided by 5, it yields a zero remainder.

**ADDITION OF MODULAR CONGRUENCES**

Addition: If a1 ≡ a2 (mod n) and b1 ≡ b2 (mod n) then a1 + b1 ≡ a2 + b2 (mod n)

Where a1, a2, b1, b2 are elements of integers and a2 + b2 (mod n) must be reduced to integers between 0 to n - 1 by dividing a2 + b2 by n . The remainder will be the final answer. If a2 +b2 < 0, n must be repeatedly added to it until it became a number whose value = 0 to n -1.

Illustration: Using 5 as the modulus of the congruence:

Example using positive integers:

Given the following congruences:

(Ex. 1)** **13** = **8 mod 5 and 23** = **18 mod 5

Therefore 13 + 23 **= **8 + 18 mod 5 → 36 = 26 mod 5

simplifying the answer furtherly : 36 = 26 mod 5 = 1 mod 5

since when 26 is divided by 5 it yields a remainder of 1..

(Ex. 2) 17 **=** 32 mod 5 and 37 = 47 mod 5 Therefore, 17 + 37 **=** 32 + 47 mod 5 → 54 **≡ 79** mod 5

Simplifying the answer furtherly : 54 = 79 mod 5 = 4 mod 5

since when when 79 is divided by 5 it yields a remainder equal to 4..

Examples: Using Negative Integers:

(Ex. 1) -7 **=**** -12 **mod 5 and -4 = -9 mod 5

Therefore -7 + -4 = -12 + -9 mod 5è -11 = -21 mod 5

simplifying the sum furtherly -11 = - 21 mod 5 = 4 mod 5

since when -21 is divided by 5 it yields a remainder = -1

and -1 mod 5 = 4 since 0 = 1 + 4 because (1+4) divided by

5 gives a 0 remainder. Or -21 +20 = -1 => -1 + 5 = 4.

ex. 2) Given, -92 **≡ **-57 mod 5

-42 **≡ **-67 mod 5

Therefore: -92 + -42 **≡** -57 + -67 mod 5 => -134 = -124 mod 5

## smplifying furtherly : -134 = -124 mod 5 = 1 mod 5 since when -124 is divided by 5 it yields a remainder = -4 and -4 mod 5 = 1 mod 5 since

## 0 = 1 + 4 because (1 + 4 ) divided by 5 gives a 0 remainder.

Or -124 + 120 = -4 =è -4 + 5 = 1

**MULTIPLICATION:**

If a1 **≡ **a2 (mod n) and b1 **≡ **b2 (mod n)

Then a1 b1 **≡ **a2 b2 (mod n) where a1, a2, b1, b2 are elements of integers and a2b2 (mod n) must be reduced to integers between 0 to n - 1 by dividing a2 b2 by n. The remainder will be the final answer.

Illustration: Using positive integers.

(Ex. 1) Given the congruences;

7 **≡ **12 mod 5 and 21 ≡ 26 mod 5

Therefore (7) (21) **≡ **(12) (26) mod 5 147 **≡ **312 mod 5

simlifying furtherly 147 = 312 mod 5 = 2 mod 5 since when

312 is divided by 5 it yields a remainder = 2.

Ex. 2) 18 = 33 mod 5 and 42 = 32 mod 5

Therefore: (18) (42) = (33) (32) mod 5

- 756 ≡ 1056 mod 5

simplifying furtherly: 756 = 1056 mod 5 = 1 mod 5

since when 1056 is divided by 5 it yield a remainder = 1.

Example using Negative Integers

(Ex. 1) Given -19 = -24 mod 5 and -28 = -33 mod 5

Therefore, (-19) (-28) = (-24) (-33) mod 5

- 532 ≡ 792 mod 5

simplifying furtherly: 532 = 792 mod 5 = 2mod 5.

Since when 792 is divided b 5 it yields a remainder = 2.

(Ex. 2) Given: -18 = -17 mod 5 and -23 = -132 mod 5

Therefore, (-18) (-23) ≡ (-17) (-132) mod 5

414 = 2244 mod 5

simplifying furtherly : 414 = 2244 mod 5 = 4 mod 5

since 2244 divided by 5 yields a remainder = 4..

References: Keesee, John W. (1965)

__Elementary Abstract Algebra__. U.S.A:

D.C. Heath and Company