Modular Arithmetic
Introduction to Modular Arithmetic
Many clocks have the familiar 12-hour design. We designate whether the time is before noon or
after noon by using the abbreviations A.M. and P.M. A reference to 7:00 A.M. means 7 hours after 12:00
midnight; a reference to 7:00 P.M. means 7 hours after 12:00 noon. In both cases, once 12 is reached on
the clock, we begin again with 1.
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. 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.
We use the symbol ⊕ to denote addition on a 12-hour clock. Using this notation,
1. 3 8=11 2. 9 8=5
We can also perform the 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 (10−7=3) . However, if the time
now is 3 o’clock, then we see that 7 hours ago it was 8 o’clock. If we use the symbol ⊝ to denote
subtraction on a 12-hour clock, we can write.
1. 10 ⊝ 7=3 2. 3 ⊝7=8
Try This On You Notebook: Evaluate the following, where ⊕ and ⊝ indicate addition and subtraction,
respectively on a 12-hour clock.
1. 3 ⊕12 6. 8 ⊝11
2. 8 ⊕7 7. 2 ⊝7
3. 5 ⊕9 8. 5 ⊝10
4. 6⊕4 9. 1 ⊝9
5. 9 ⊕11 10. 11⊝ 6
A similar example involves day-of-the-week arithmetic. If we associate each day of the week with a
number shown below, then 6 days after Friday is Thursday and 16 days after Monday is Wednesday. In
symbols, we write
Monday – 1 Wednesday – 3 Friday – 5 Sunday – 7
Tuesday – 2 Thursday – 4 Saturday – 6
a. 5 ⊞6=4 b. 1 ⊞16=3
Note: We are using ⊞ for days-of-the-week arithmetic to differentiate from the ⊕ symbol for clock
arithmetic.
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
1+16=17 is divided by 7, the remainder is 3, associated with Wednesday. This works because the days
of the week repeat every 7 days.
The same method can be applied to 12-hour-clock arithmetic. From 8+7=15 is divided by 12, the
number of hours on a 12-hour clock, the remainder is 3, the time 7 hours after 8 o’clock.
Situations such as these that repeat in cycles are represented mathematically by using modular
arithmetic, or arithmetic modulo n.
Definition: Modulo n
Two integers a andb are said to be congruent modulo n , wheren is a natural number, if
a−b
is an integer. In this case, we write a ≡ b mod n. The number n is called the modulos. The
n
statement a ≡ b mod n is called a congruence.
Example: Determine whether the congruence is true.
a. 29 ≡8 mod 3 b. 15 ≡ 4 mod 6
Solution:
29−8 21
a. Find = =7. Because 7 is an integer, 29 ≡8 mod 3 is a true congruence.
3 3
15−4 11 11
b. Find = . Because is not an integer, 15 ≡ 4 mod 6 is not a true congruence.
6 6 6
For 29 ≡8 mod 3 given in previous example, note that 29 ÷ 3 ( modulus ) =9 remainder 2 and that
11÷ 3 ( modulus )=3 remainder 2. Both 29 and 11 have the same remainder when divided by the
modulus. This leads to an important alternate method to determine a true congruence. If a ≡ b mod n
anda andb are whole numbers, thena and b have the same remainder when divided by n .
Using the alternate method, is 33 ≡ 49 mod 4 a true congruence?
Try this on your Notebook. Determine whether the congruence is true.
1. 7 ≡12 mod 5 6. 49 ≡ 9 mod 8
2. 15 ≡1 mod 8 7. 95 ≡16 mod 10
3. 28 ≡7 mod 7 8. 88 ≡5 mod 12
4. 45 ≡ 18 mod 6 9. 129 ≡5 mod 3
5. 11≡5 mod 4 10. 210 ≡25 mod 7
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: A Day of the Week
1. July 4, 2017, was a Tuesday. What day of the week is July 4,2022?
Solution:
There 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.
Try to Answer This!
In 2016, Abraham Lincoln’s birthday fell on Friday, February 12. On what day of the week does Lincoln’s
birthday fall in 2025?
Arithmetic Operations Modulo n
In previous example, we verified that 29 ≡8 mod 3 . (Both 29 and 8 have remainder 2 when
divided by 3, the modulus.) There are many other numbers congruent to 8 modulo 3, but of all these,
only one is a whole number less than the modulus. This number is the result when evaluating a modulo
expression, and in this case, we use an equal sign. Because 2 ≡8 mod 3 and 2 is less than the modulus,
we can write 8 mod 3=2. In general, m mod nbecomes the remainder when m is divided by n .
Arithmetic modulon (wheren 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 modn is always a whole
number less than n .
1. Addition Modulo n
Evaluate: ( 23+38 ) mod 12
Solution: Add 23+38 to produce 61. To evaluate61 mod 12, divide61 by the modulus, 12. The answer is
the remainder.
61 ÷12=5 remainder 1
( 23+38 ) mod 12=1
∴ The answer is 1.
In modular arithmetic, adding the modulus to a number does not change the equivalent value of the
number. For instance,
a. 13 ≡6 mod 7 b. 10 ≡1 mod 3
20 ≡6 mod 7 Add 7 to 13 13 ≡1 mod 3 Add 3 to 10
27 ≡ 6 mod 7 Add 7 to 20 16 ≡1 mod 3 Add 3 to 13
To understand why the values does not change, consider 7 ≡ 0 mod 7 and 3 ≡0 mod 3 . That is,
in mod 7 arithmetic, 7 is equivalent to 0; in mod 3, 3 is equivalent to 0. Just as adding 0 to a number
does not change the value of the number in regular arithmetic, in modular arithmetic adding the
modulus to a number does not change the value of the number. This property of modular arithmetic is
sometimes used in subtraction.
It is possible to use negative numbers modulo n. for instance,
−2−5 −7
−2 ≡5 mod 7 because = =−1 , an integer.
7 7
Suppose we want to find x so that −15 ≡ x mod 6. Using the definition of modulo n, we need to
−15−x
find x so that is an integer. To do this, rewrite the expression and then try various values of x
6
from 0 to the modulus until the value of the expression is an integer.
−15−x −( 15+ x )
=
6 6
−( 15+0 ) −15
When x=0 , = , not an integer
6 6
−( 15+1 ) −16
When x=1, = , not an integer
6 6
−( 15+2 ) −17
When x=2, = , not an integer
6 6
−( 15+3 ) −18
When x=0 , = =−3, an integer
6 6
−15 ≡3 mod 6
It may be necessary to use this idea when subtracting in modular arithmetic.
2. Subtraction Modulo n
Evaluate:
a. ( 33−16 ) mod 6
Solution:
Subtract 33−6=17 . The result is positive. Divide the difference by the modulus, 6. The answer is the
remainder.
17 ÷ 6=2remainder 5
∴ ( 33−16 ) mod 6=5
b. ( 14−27 ) mod 5
Solution:
Subtract 14−27=−13. Because the answer is negative, we must find x so that −13 ≡ x mod 5. Thus,
−13−x −( 13+ x )
we must find x so that the value of = is an integer. Trying the whole number values
5 5
− (13+ 2 ) −15
of x less than 5, the modulus, we find that when x=2 , = =−3.
5 5
∴ ( 14−27 ) mod 5=2
3. Calculating Times
Disregarding AM or PM, 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
−52−x − (52+ x )
to find x so that = is an integer. Evaluating the expression for whole number values
12 12
−(52+8) −60
of x less than 12, we have, when x=8 , = =−5, an integer. Thus, ( 5−57 ) mod 12=8 .
12 12
Therefore, if it is 5 o’clock now, 57 hours ago it was 8 o’clock.
Try this! If today is Tuesday, what day of the week will it be 93 days from now?
4. 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.
345 ÷ 11=31 remainder 4
∴ ( 15 ∙23 ) mod 11=4
Try this! Evaluate ( 33 ∙ 41 ) mod 17
Solving Congruence Equations
Solving congruent equation means finding all whole number values of the variable for which the
congruence is true.
a. For example, to solve 3 x+ 5≡ 3 mod 4 , we search for whole number values of x for which the
congruence is true.
3 ( 0 ) +5 ≢ 3 mod 4
3 ( 1 ) +5 ≢3 mod 4
3 ( 2 ) +5 ≡3 mod 4 2 is a solution
3 ( 4 ) +5 ≢3 mod 4
3 ( 5 ) +5 ≢3 mod 4
3 ( 6 ) +5 ≡3 mod 4 6 is a solution
If we continued trying values, we would find that 10 and 14 are also solutions. Note that the
solutions 6, 10 and 14 are all congruent to 2 modulo 4. In general, once a solution is determined,
additional solutions can be found by repeatedly adding the modulus to the original solution. Thus, the
solution of 3 x+ 5≡ 3 mod 4 are 2 , 6 ,10 ,14 ,18 , . ..
When solving a congruence equation, it is necessary to check only the whole number less than the
modulus. For the congruence equation 3 x+ 5≡ 3 mod 4 , we needed to check only 0, 1, 2, and 3. Each
time a solution is found, additional solution can be found by repeatedly adding the modulus to it. A
congruence equation can have more than one solution among the whole numbers less than the
modulus. The next example illustrates that you must check all whole numbers less than the modulus.
b. Solve: 2 x+1 ≡3 mod 10
Solution: Beginning with 0, substitute each whole number less than 10 into the congruence equation.
x=0 2 ( 0 ) +1 ≢3 mod 10 Not a solution
x=1 2 ( 1 )+ 1≡ 3 mod 10 A solution
x=2 2 ( 2 ) +1≢ 3 mod 10 Not a solution
x=3 2 ( 3 ) +1≢ 3 mod 10 Not a solution
x=4 2 ( 4 ) +1≢ 3 mod 10 Not a solution
x=5 2 ( 5 ) +1≢ 3 mod 10 Not a solution
x=6 2 ( 6 ) +1 ≡3 mod 10 A solution
x=7 2 ( 7 ) +1 ≢3 mod 10 Not a solution
x=8 2 ( 8 ) +1 ≢3 mod 10 Not a solution
x=9 2 ( 9 ) +1 ≢3 mod 10 Not a solution
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, . . .
Try this! Solve: 4 x+1 ≡5 mod 12
Not all congruence equations have a solution. For instance, 5 x+ 1≡ 3 mod 5 has no solution, as shown
below.
x=0 5 ( 0 ) +1 ≢3 mod 5 Not a solution
x=1 5 ( 1 ) +1≢ 3 mod 5 Not a solution
x=2 5 ( 2 ) +1≢ 3 mod 5 Not a solution
x=3 5 ( 3 ) +1 ≢3 mod 5 Not a solution
x=4 5 ( 4 ) +1≢ 3 mod 5 Not a solution
Because no whole number value of x less than the modulus is a solution, there is no solution.
Additive and Multiplicative Inverses in Modular Arithmetic
Recall 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, on mod 8
arithmetic, 3 is the additive inverse of 5, and 5 is the additive inverse of 3. Here, we consider only those
numbers smaller than the modulus. Note that 3+5=8; that is, the sum of a number and its additive
inverse equals the modulus. For instance, in mod 11 arithmetic, the additive inverse of 5 is 6 because
5+6=11.
a. Find the additive inverse of 7 in mod 16 arithmetic
Solution: In mod 16 arithmetic, 7+9=16 , so the additive inverse of 7 is 9.
Try This! Find the additive inverse of 6 in mod 12 arithmetic.
If the product of two numbers is 1, then the numbers are Multiplicative inverses of each other.
1 1 1
For instance, 2 ∙ =1, so 2 I the multiplicative inverse of , and is the multiplicative inverse of 2. The
2 2 2
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 ( 5 ∙3 ) ≡ 1mod 7 . (Here, we will concern ourselves only with natural
numbers less than the modulus.) To find the multiplicative inverse ofa mod m, solve for the modular
equation ax ≡1 mod m for x .
b. In mod 7 arithmetic, find the multiplicative inverse of 2.
Solution: To find the multiplicative inverse of 2, solve the equation 2 x ≡1 mod 7 by trying different
natural number values of x less than the modulus.
2 x ≡1 mod 7
2 ( 1 ) ≢ 1 mod 7 Try x=1
2 ( 2 ) ≢ 1 mod 7 Try x=2
2 ( 3 ) ≢1 mod 7 Try x=3
2 ( 4 ) ≡ 1 mod 7 Try x=4
∴ In mod 7 arithmetic, the multiplicative inverse of 2 is 4.
Try This! Find the multiplicative inverse of 5in mod 11.
Computing the Day of the Week
A function that is related to the modulo function is called the floor function. In the modulo
function, we determine the remainder when one number is divided by another. In the floor function, we
determine the quotient (and ignore the remainder) when one number is divided by another. The symbol
for the floor function is ⌊ ⌋ . Here are some examples.
2 10 17 2
⌊ ⌋=0 ⌊ ⌋=5 ⌊ ⌋=8 ⌊ ⌋ =1
3 2 2 √2
Using the floor function, we can write a formula that gives the day of the week for any date on the
Gregorian calendar. The formula, known as Zeller’s congruence, is given by
( 13 m−1
x= ⌊
5
⌋ + ⌊ ⌋ + ⌊ ⌋ + d+ y−2 c ) mod 7
y
4
c
4
Where:
d – day of the month
m – the month using 1 for March, 2 for April, … , 10 for December, January and February are
assigned the values 11 and 12, respectively.
y – the last two digits of the year if the month is March through December, if the month is
January of February, y is the last two digits of the year minus 1
c – the first two digits of the year
x – the day of the week (using 0 for Sunday, 1 for Monday, … , 6 for Saturday)
For example, to determine the day of the week on July 4 ,1776 , we have c=17 , y =76 , m=5 , d=4 .
Usingthese values, we can calculate x .
( 13 ( 55)−1 ⌋ + ⌊ 764 ⌋ + ⌊ 174 ⌋ + 4+76−2 (17 )) mod 7
x= ⌊
¿ ( 12+19+ 4+ 4+76−34 ) mod 7
¿ ( 81 ) mod 7=4
Therefore, July 4 ,1776 , was Thursday.
Exercises:
1. Determine the day of the week on which you were born.
2. Determine the day of the week on which Abraham Lincoln’s birthday (February 12) will
fall in 2155.
3. Determine the day of the week on which January 1, 2050, will fall.
4. Determine the day of the week on which Valentine’s Day (February 14) 1950 fell.
Prepared by:
RENE BOY H. CALCAÑA
Instructor I