CHAPTER

Mathematical
Systems
Copyright © Cengage Learning. All rights reserved.
 7.1
Section Modular Arithmetic

Copyright © Cengage Learning. All rights reserved.

Introduction to Modular Arithmetic

3
Introduction to Modular Arithmetic
If we want to determine a time in the future or in the past, it
is necessary to consider whether we have passed
12 o’clock. To determine the time 8 hours after 3 o’clock,
we add 3 and 8. Because we did not pass 12 o’clock, the
time is 11 o’clock (Figure 7.1A).

We will use the symbol to denote

addition on a 12-hour clock. Using
this notation

Figure 7.1A

4
Clock Arithmetic
However, to determine the time 8 hours after 9 o’clock, we
must take into consideration that once we have passed
12 o’clock, we begin again with 1. Therefore, 8 hours after
9 o’clock is 5 o’clock, as shown in Figure 7.1B

Figure 7.1B

We will use the symbol to denote addition on a 12-hour

clock. Using this notation,

5
Clock Arithmetic
• Another technique that can be applied to 12-hour-clock
arithmetic:
Example:

When 8+7=15 is divided by 12, the number of hours on a

12-hour clock, the remainder is 3, which is the time 7 hours
after the 8 o’clock.

6
Clock Arithmetic
We can also perform subtraction on a 12-
hour clock. If the time now is 10 o’clock, then
7 hours ago the time was 3 o’clock, which is
the difference between 10 and 7 which is (10
– 7 = 3). If we use the symbol to denote
subtraction on a 12-hour clock, we can write

However, if the time now is 3 o’clock, then,

using Figure 7.2, we see that 7 hours ago
it was 8 o’clock.

Figure 7.2

7
Example 1 – Perform Clock Arithmetic
Evaluate each of the following, where and indicate
addition and subtraction, respectively, on a 12-hour clock.
a. b. b. c. c. d.
Solution:
Calculate using a 12-hour clock.
a.

b.

c.

d.
8
Answers

9
Day-of-the-Week Arithmetic.
A similar example involves day-of-the-week arithmetic. If
we associate each day of the week with a number, as
shown below, then 6 days after Friday is Thursday and 16
days after Monday is Wednesday.

Monday Tuesday Wednes Thursday Friday Saturday Sunday

day
1 2 3 4 5 6 7

Symbolically, we write
and

Note: We are using the symbol for days-of-the-week arithmetic to

differentiate from the symbol for clock arithmetic. 10
 Day-of-the-Week Arithmetic.
Monday Tuesday Wednes Thursday Friday Saturday Sunday
day
Day-of-the-Week
1 2 3 4
Arithmetic.
5 6 7

Another way to determine the day of the week is to note that when the sum
5+6=11 is divided by 7, the number of days in a week, the remainder is 4,
the number associated with Thursday.

When the sum 1+16=17 is divided by 7, the remainder is 3,

the number associated with Wednesday.

This works because the days of the week repeat every 7 days.
11
Introduction to Modular Arithmetic
Situations such as these that repeat in cycles are
represented mathematically by using modular arithmetic,
or arithmetic modulo n.

12
Example 2 – Determine Whether a Congruence Is True

Determine whether the congruence is true.

a. 29  8 mod 3
b. 15  4 mod 6

Solution:
a. Find Because 7 is an integer,
29  8 mod 3 is a true congruence.

b. Find Because is not an integer,

15  4 mod 6 is not a true congruence.

13
Answers

14
 True Congruence
Monday Tuesday Wednes Thursday Friday Saturday Sunday
day

Now suppose today is Friday. To determine the day of the week 16

days from now, we observe that 14 days from now the day will be
Friday, so 16 days from now the day will be Sunday.

Note that the remainder when 16 is divided by 7 is 2. Using modular

notation,
16  2 mod 7

The 2 signifies 2 days after Friday, which is Sunday.

Note:
15
Example 3 – A Day of the Week
July 4, 2017, was a Tuesday. What day of the week is
July 4, 2022?

Solution:
There are 5 years between the two dates. Each year has
365 days except 2020, which has one extra day because it
is a leap year.

So the total number of days between the two dates is

5  365 + 1 = 1826.

16
Example 3 – Solution cont’d

Because 1826 ÷ 7 = 260 remainder 6.

Thus,
1826  6 mod 7.

Monday Tuesday Wednes Thursday Friday Saturday Sunday

day

So the day of the week 1826 days after July 4, 2017

(Tuesday), will be the same as the day 6 days after July 4,
2017.
Thus July 4, 2022, will be a Monday.
17
Answer:
The years 2008, 2012, and 2016 are leap years, so there are
3 years between the two dates with 366 days and 6 years with 365 days.
The total number of days between the dates is (9*365) + 3 = 3288.
So, 3288 / 7 = 469 remainder 5, so 3288  5 mod 7.

The day of the week 3288 days after Tuesday, February 12, 2008, will be
the same as the day 5 days later, a Sunday.

Monday Tuesday Wednes Thursday Friday Saturday Sunday

day

18
Arithmetic Operations Modulo n

19
Arithmetic Operations Modulo n
Arithmetic modulo n (where n is a natural number) requires
us to evaluate a modular expression after using the
standard rules of arithmetic.

Thus we perform the arithmetic operation and then divide

by the modulus. The answer is the remainder.

The result of an arithmetic operation mod n is always a

whole number less than n.

20
Example 4 – Addition Modulo n
Evaluate: (23 + 38) mod 12

Solution:
Add 23 + 38 to produce 61. To evaluate 61 mod 12, divide
61 by the modulus, 12. The answer is the remainder.

The answer is (23 + 38) mod 12 =1.

21
Answer (51+72) mod 3 = 0

22
Example 5 – Subtraction Modulo n
Evaluate each of the following.
a. (33 – 16) mod 6
b. (14 – 27) mod 5

Solution:
a. Subtract The result is positive. Divide the
difference by the modulus, 6. The answer is the
remainder.

(33 – 16) mod 6 = 5

23
Example 5 – Solution cont’d

b. Subtract Because the answer is negative,

we must find x so that –13  x mod 5. Thus we
must find x so that the value of is an
integer.

Trying the whole number values of x less than 5, the

modulus, we find that when x = 2,

(14 – 27) mod 5 = 2

Note: 24
Answer

25
Arithmetic Operations Modulo n
The methods of adding and subtracting in
modular arithmetic can be used for clock
arithmetic and days-of-the-week arithmetic.

26
Example 6 – Calculating Times
Disregarding A.M. or P.M., if it is 5 o’clock now, what time
was it 57 hours ago?

Solution:
The time can be determined by calculating
(5 – 57) mod 12. Because 5 – 57 = –52 is a negative
number, find a whole number x less than the modulus 12,
so that –52  x mod 12.

This means to find x so that is an integer.

27
Example 6 – Solution cont’d

Evaluating the expression for whole number values of x

less than 12, we have, when
an integer.

Thus (5 – 57) mod 12 = 8.

Disregarding A.M. or P.M., if it is 5 o’clock now, what time

was it 57 hours ago?

Therefore, if it is 5 o’clock now, 57 hours ago it was 8

o’clock.
28
Monday Tuesday Wednes Thursday Friday Saturday Sunday
day
1 2 3 4 5 6 7

Answer
Let Tuesday correspond to 2 (see table above). So the day of
the week 93 days from now is represented by (2 + 93) mod 7.
Because ,
Thus
=
which corresponds to Thursday.
29
Arithmetic Operations Modulo n
Problems involving multiplication can also be performed
modulo n.

30
Example 7 – Multiplication Modulo n
Evaluate: (15  23) mod 11

Solution:
Find the product 15  23 and then divide by the modulus,11.
The answer is the remainder.

The answer is (15*23) mod 11 = 4. 31

Answer

32
Solving Congruence Equations

33
Solving Congruence Equations p.297
Solving a congruence equation means finding all whole
number values of the variable for which the congruence is
true.
For example, to solve 3x + 5  3 mod 4, we search for
whole number values of x for which the congruence is true.

Solution:
Beginning with 0, substitute each whole number less than the modulo (4)

Note: 34
In general, once a solution is determined, the additional
solutions can be found by repeatedly adding the modulus
(mod 4) to the original solution.

Thus, the solutions are 2, 6, 10, 14, 18,…

Note: 35
A congruence equation can have more than one solution among
the whole numbers less than the modulus. The next example
Example
illustrates 8 –must
that you Solve a all
check Congruence
whole numbers Equation
less than the
modulus.

Solve: 2x + 1  3 mod 10
Solution:
Beginning with 0, substitute each whole number less than
10 into the congruence equation.

36
Example 8 – Solution cont’d

The solutions between 0 and 9 are 1 and 6; the remaining

solutions are determined by repeatedly adding the
modulus, 10, to these solutions. The solutions are 1, 6, 11,
16, 21, 26, … .
37
• Substitute each whole number from 0 to 11 into the
congruence

The solutions from 0 to 11 are 1, 4, 7, and 10. The remaining solutions are
obtained by repeatedly adding the modulus 12 to these solutions. So the
solutions are 1, 4, 7, 10, 13, 16, 19, 22, ... . 38
Additive and Multiplicative Inverses
in Modular Arithmetic

39
Additive and Multiplicative Inverses in Modular Arithmetic

We have known that if the sum of two numbers is 0, then

the numbers are additive inverses of each other. For
instance, 8 + (–8) = 0, so 8 is the additive inverse of –8,
and –8 is the additive inverse of 8.

The same concept applies in modular arithmetic. For

example, (3 + 5)  0 mod 8. Thus, in mod 8 arithmetic, 3 is
the additive inverse of 5, and 5 is the additive inverse of 3.
Here we consider only those whole numbers smaller
than the modulus.

Note: The sum of a number and its additive inverse

equals the modulus.
40
Example 9 – Find the Additive Inverse
Find the additive inverse of 7 in mod 16 arithmetic.
That is, find: (7+ ?_ )  0 mod 16

Note: The sum of a number and its additive inverse

equals the modulus.

Solution:
In mod 16 arithmetic, 7 + ?__ = 16
7+9 = 16

so the additive inverse of 7 is 9. Thus (7+ 9)  0 mod 16

Note:
41
Answer

• In mod 12 arithmetic, 6 + 6 = 12, so the additive inverse

of 6 is 6.
• Thus, (6 + 6)  0 mod 12

42
Additive and Multiplicative Inverses in Modular Arithmetic

If the product of two numbers is 1, then the numbers are

multiplicative inverses of each other.

For instance, , so 2 is the multiplicative inverse of

, and is the multiplicative inverse of 2. The same
concept applies to modular arithmetic (although the
multiplicative inverses will always be natural numbers).

For example, in mod 7 arithmetic, 5 is the multiplicative

inverse of 3 (and 3 is the multiplicative inverse of 5)
because

Note:
43
Example 10 – Find a Multiplicative Inverse
To find the multiplicative inverse, solve the modular equation
ax  1 mod m

for x less than the modulus

In mod 7 arithmetic, find the multiplicative inverse of 2.

Solution:
To find the multiplicative inverse of 2, solve the equation
2x  1 mod 7 by trying different natural number values of x
less than the modulus.

44
Example 10 – Solution cont’d

In mod 7 arithmetic, the multiplicative inverse of 2 is 4.

Thus, 2*4  1 mod 7

45
Answer
• Solve the congruence equation
5x  1 mod 11 by substituting
whole number values of x less
than the modulus.

In mod 11 arithmetic, the multiplicative inverse of 5 is 9.

Thus, 5*9  1 mod 11

46