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

Scroll to Continue

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

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