reminder
These PowerPoinT slides are
only To be used by Xu Teachers
and sTudenTs for educaTional
PurPoses. They musT noT be
uTilized or shared ouTside of Xu.
Mathematical
Systems
Module 7
Section 7.1 (Part 1)
Modular
arithmetic
Learning Outcomes
At the end of this section, the students are expected to:
1. perform addition, subtraction, multiplication modulo n;
2. apply modular arithmetic in predicting a specific time or
day;
3. identify congruent/incongruent integers modulo n;
4. solve linear congruence in one variable; and
5. determine the additive/multiplicative inverse of
an integer modulo n.
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 7 hours after 3 o’clock,
we add 3 and 7. Because we did not pass
12 o’clock, the time is 10 o’clock.
+ 7 hours
However, to determine
the time 10 hours after
7 o’clock, we must take
into consideration that
once we have passed
12 o’clock, we begin
again with 1. Therefore,
10 hours after 7 o’clock is
5 o’clock.
We will use the symbol to denote addition
on a 12-hour clock. Using this notation,
3
and
7
on a 12-hour clock.
We can also perform
subtraction on a 12-hour
clock. If the time now is
8 o’clock, then 7 hours ago
the time was 1 o’clock, which
is the difference between 8
and 7.
8−7=1
However, if the time
now is 3 o’clock, then
we see that 4 hours
ago it was 11 o’clock.
If we use the symbol to denote subtraction
on a 12-hour clock, we can write
8
and
3
on a 12-hour clock.
Example 5.1.1 Evaluate each of the following,
where and indicate addition and subtraction,
respectively, on a 12-hour clock.
a. 9
b. 6
c. 3
d. 7
Solution.
a. 9
b. 6
c. 3 =6
d. 7
A similar example involves days-of-the-week
arithmetic. If we associate each day of the week
with a number, as shown below, then 5 days after
Friday is Wednesday and 20 days after Tuesday is
Monday.
Monday = 1
Tuesday = 2
Wednesday = 3
Thursday = 4
Friday = 5
Saturday = 6
Sunday = 0
We will use the symbol for days-of-the-
week arithmetic to differentiate from the
symbol for clock arithmetic.
Thus,
5
Situations such as these that repeat in cycles
are represented mathematically by using
modular arithmetic, or arithmetic modulo n.
Definition 5.1.1 Two integers and are
said to be congruent modulo , where is a
natural number if is an integer.
In symbols,
.
The number is called the modulus.
The statement is called a congruence.
NOTE. We write (mod ) to indicate
that is not congruent to modulo that is,
is not an integer.
Example 5.1.2 Based on the above definition, the
following statements are true.
a. 8 ≡ 13 (mod 5)
b. 47 ≡ −1 (mod 12)
c. −9 ≡ 17 (mod 13)
d. 14 5(mod 4)
e. −67 2 (mod 10)
Example 5.1.3 Determine whether the
congruence is true.
a. 24 3 mod 7 b. 10 4 mod 5
Solution.
a. Because is an integer, 24 3 mod 7 is a
true congruence.
b. Because is not an integer, 4 mod 5
is not a true congruence.
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, or, using modular notation, 16 2 mod 7.
The 2 signifies 2 days after Friday, which is
Sunday.
Example 5.1.4 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.
Because 1826 ÷ 7 = 260 remainder 6,
1826 6 mod 7. Any multiple of 7 days past a
given day will be the same day of the week.
So, the day of the week 1826 days after July 4,
2017, will be the same as the day 6 days after
July 4, 2017. Thus July 4, 2022, will be a Monday.
