CORE
MATHEMATICS
MODULAR ARITHMETIC
OBJECTIVES
By the end of the lesson the student will be able to;
1. Calculate the value of numbers for a given modulo.
2. Add and multiply numbers in a given modulo.
Calculation of a number for a given modulo
• Modular arithmetic is a system of arithmetic where we are only interested in the
remainder after dividing a number by another number.
• The number used to the divide the number is called modulo
• Modulo(mod) is a mathematical operation that find the remainder when one
number is divided by another.
𝑥
• Example, 𝑥 𝑚𝑜𝑑 𝑦 = 𝑟 is the same as = 𝑟, where 𝑥 is the dividend, 𝑦 is the
𝑦
divisor and 𝑟 is the remainder.
The face of a clock
• We have 24 hours within a day but the numbers on the clock in our homes
ranges from 1 to 12.
• This means that is it design in 12 hours which is in mod 12
• When its get to the 14th hour, we have 14 mod 12 = 2. 14pm on the 24 hour
clock is the same as 2pm on the 12 hour clock
The idea of remainder to find the modulus of numbers
• Modular arithmetic is related to the remainder theory in division
• Any number in a given modulo is found by dividing the number by the modulo
and the remainder is the value we are interested in.
• Example, 5 in modulo 2 (5 𝑚𝑜𝑑 2) is 1, since when 5 is divided by 2 the
remainder is 1
Example
1. 2 = 2 in mod 5
2. 25 = 1 in mod 4
3. 13 = 3 in mod 10
4. 5 = 5 in mod 13
Modulo of negative numbers
• The modulo of negative numbers is obtained by adding multiples of the modulo
to the number until we get the first positive number
• Example, -9 mod 5 = -9 + 5 = -4
−4 + 5 = 1
Since we have a positive answer, -9 mod 5 = 1
Example
1. -2 = 3 in mod 5
2. -12 = 0 in mod 6
3. -5 = 1 in mod 2
Addition ⊕ and Multiplication ⊗ table in a given
modulo
The sum or product of two or more numbers in a given modulo is found by first
adding or multiplying the numbers before converting the given modulo.
Example
1. 4 + 5 (mod 5) = 9 (mod 5) = 4
2. -10 + 4 (mod 5) = -6 (mod 5) = 4
3. 5 × 9 (mod 12) = 45 (mod 12) = 9
Note: subtraction is also performed in the same way as addition and multiplication.
Examples
1. Draw an addition and multiplication table for modulo 12 on the set 𝑃 =
{1,4,9,11}.
Use your table to find the truth set of
i. 9⨂𝑛 = 0
ii. 𝑛⨂𝑛 = 1
iii. 4⨁9 = 𝑛
iv. 11⨁(1 ⨂ 4)
addition mod 12 multiplication mod 12
⨁ 1 4 9 11 ⨁ 1 4 9 11
1 2 5 10 0 1 1 4 9 11
4 5 8 1 3 4 4 4 0 8
9 10 1 6 8 9 9 0 9 3
11 0 3 8 10 11 11 8 3 1
From the table, the truth set of
i. 9⨂𝑛 = 0 is {𝑛: 𝑛 = 4}
ii. 𝑛⨂𝑛 = 1 is {𝑛: 𝑛 = 1 𝑜𝑟 11}
iii. 4⨁9 = 𝑛 is {𝑛: 𝑛 = 1}
iv. 11⨁ 1 ⨂ 4 = 11 ⊕ 4 = 3
Examples
2. a. Draw an addition and multiplication table for arithmetic modulo 6
b. Use your table to evaluate
i. (2 ⊕ 3) ⊕ 4 iii. 4 ⊕ (3 ⊗ 5)
ii. 3 ⊗ (4 ⊗ 5) iv. (1 ⊕ 3) ⊗ (2 ⊕ 1)
c. Use your table to find the truth sets of:
i. 𝑛⊗𝑛 =1 iii. 𝑛 ⊕ 4 = 1
ii. 5 ⊕ 2 ⊕ 𝑛 = 4
⨁ 0 1 2 3 4 5 ⊗ 0 1 2 3 4 5
0 0 1 2 3 4 5 0 0 0 0 0 0 0
1 1 2 3 4 5 0 1 0 1 2 3 4 5
2 2 3 4 5 0 1 2 0 2 4 0 2 4
3 3 4 5 0 1 2 3 0 3 0 3 0 3
4 4 5 0 1 2 3 4 0 4 2 0 4 2
5 5 0 1 2 3 4 5 0 5 4 3 2 1
b. From the table
i. 2 ⊕ 3 ⊕ 4 = 5 ⊕ 4 = 3
ii. 3 ⊗ 4 ⊗ 5 = 3 ⨂ 2 = 0
iii. 4 ⊕ 3 ⊗ 5 = 4 ⊕ 3 = 1
iv. 1 ⊕ 3 ⊗ 2 ⊕ 1 = 4 ⊗ 3 = 0
c. From the table the truth set of
i. 𝑛 ⊗ 𝑛 = 1 is {𝑛: 𝑛 = 1 𝑜𝑟 5}
ii. 𝑛 ⊕ 4 = 1 is {𝑛: 𝑛 = 3}
iii. 5 ⊕ 2 ⊕ 𝑛 = 4 is {𝑛: 𝑛 = 3}
Note: if a set of numbers is not given, then we start from 0 and end at the number that
comes before the mod.
Combination of binary operation and modular arithmetic
Example
The operation ∗ is defined by 𝑥 ∗ 𝑦 = 𝑥 + 𝑦 + 𝑥 2 in arithmetic modulo 6. find:
i. 3 ∗ 4 ii. 4 ∗ 3
iii. 3 ∗ (2 ∗ 5) iv. (3 ∗ 2) ∗ 5
Solution
𝑥 ∗ 𝑦 = 𝑥 + 𝑦 + 𝑥2
i. 3 ∗ 4 = 3 + 4 + 32
= 7 + 9 = 16 = 4(𝑚𝑜𝑑 6)
ii. 4 ∗ 3 = 4 + 3 + 42
= 7 + 16 = 23 = 5(𝑚𝑜𝑑 6)
iii. 3 ∗ 2 ∗ 5 = 3 ∗ (2 + 5 + 22 )
= 3 ∗ 11 = 3 + 11 + 32
= 14 + 9 = 23 = 5(𝑚𝑜𝑑 6)
iv. 3 ∗ 2 ∗ 5 = (3 + 2 + 32 ) ∗ 5
= 14 ∗ 5 = 14 + 5 + 142
= 19 + 196 = 215 = 5(𝑚𝑜𝑑 6)
Equations Involving Modulo
Examples
Find the value of 𝑥 in the following
i. 24 = 3 𝑚𝑜𝑑 𝑥
ii. 2𝑥 = 1 𝑚𝑜𝑑 3
Solution
i. 24 = 3 𝑚𝑜𝑑 𝑥 means 3 is the remainder
24 − 3 = 21
We now find the factors of 21, factors of 21 are 1, 3, 7, 21.
From this factors, 7 and 21 satisfies the statement.
∴ 𝑥 = 7 𝑜𝑟 21
ii. 2𝑥 = 1 𝑚𝑜𝑑 3 means 1 is the remainder
And 3 is a factor of 2𝑥 − 1
Therefore the least positive value of 𝑥 for which 3 is a factor of 2𝑥 − 1 is 2
Note: when 𝑥 = 2, 2𝑥 − 1 = 3 which 3 is a factor of 3
∴𝑥=2
Try
1. If it is 12 o’clock now 3. a. Construct multiplication and addition
What time will it be in table for modulo 5
i. 39 hours b. use your table to evaluate
ii. 45 hours i. (4 ⊗ 3) ⊕ 2 ii. (1 ⊗ 4)⨁(3 ⨂ 4)
iii. 17 hours c. use your table to find the truth set of
2. Simplify the following i. 𝑛⨁𝑛 = 1 ii. 𝑛 ⊗ 𝑛 = 1
i. 57 (mod 7) iii. 2 ⊗ 1 ⊕ 𝑛 = 4
ii. 14 (mod 4) 4. find the value of 𝑥 in the following
iii. 13 (mod 23) i. 26 = 2 𝑚𝑜𝑑 𝑥 ii. 5𝑥 = 2 𝑚𝑜𝑑 3