Congruences and applications

Engelbert Baloloy
ebaloloy@[Link]

Ateneo de Naga University

October 2, 2024

MrB
Intercession 2024 Baloloy 1

Congruence
 Whenever the question of the divisibility of integers by a fixed
integer m occurs, the concept and the notation of "congruence"
(due to Gauss) serves to clarify and simplify the reasoning.

Intercession 2024 Baloloy 2

a mod m
To introduce this concept let us examine the remainders left
when integers are divided by the number 7. We have
 0=0·7+0
1=0·7+1
2=0·7+2
3=0·7+3
4=0·7+4
5=0·7+5
6=0·7+6
7=1·7+0
Intercession 2024 Baloloy 3

a mod 7

8=1·7+1
9=1·7+2
10 = 1 · 7 + 3
 11 = 1 · 7 + 4
12 = 1 · 7 + 5
13 = 1 · 7 + 6
14 = 2 · 7 + 0
15 = 2 · 7 + 1
16 = 2 · 7 + 2
17 = 2 · 7 + 3
···
Intercession 2024 Baloloy 4

Congruent modulo 7

We observe that the remainder left when any integer is divided by

 7 is one of the seven integers 0, 1, 2, 3, 4, 5, 6. We say that two
integers a and b are "congruent mod 7" if they leave the same
remainder on division by 7.

Intercession 2024 Baloloy 5

Calendar method
Intercession 2024 Baloloy 6

Definition
 Let a, b, m ∈ Z with m > 0. Then a is said to be congruent to
b modulo m, denoted a ≡ b mod m, if m|a − b. If a ≡ b mod
m, then m is said to be the modulus of the congruence.

Intercession 2024 Baloloy 7

Equivalent formulation
 a is congruent to b mod m.
m divides a − b.
a = b + mq for some integer m.

Intercession 2024 Baloloy 8

Definition

Given a nonnegative integer a and a positive integer

 m, a mod m = r ←→ a = mq + r

where q and r are integers and 0 ≤ r < m

Intercession 2024 Baloloy 9

Equivalence relation

Congruence mod m is an equivalence relation on Z.

1
a ≡ a mod m
2
If a ≡ b mod m then b ≡ a mod m
3
a ≡ b mod m and b ≡ c mod m then a ≡ c mod m Intercession 2024 Baloloy 10

Residue system

The set {0, 1, 2, 3, ..., m − 1} is a complete residue system modulo

m.

The set {0, 1, 2, 3, ..., m − 1} is said to be the set of

least nonnegative residues modulo m.
 Prove or disprove that {−39, 72, −23, 50, −15, 63,
−52} is a complete residue system modulo 7.

Intercession 2024 Baloloy 11

Equivalence classes

Z is partitioned into equivalence classes under congruence

modulo m. [0] = {x ∈ Z : x ≡ 0 mod 7}
[1] ={x ∈ Z : x ≡ 1 mod 7}
[2] = {x ∈ Z : x ≡ 2 mod 7}
[3] = {x ∈ Z : x ≡ 3 mod 7}
[4] = {x ∈ Z : x ≡ 4 mod 7}
 [5] = {x ∈ Z : x ≡ 5 mod 7}
[6] = {x ∈ Z : x ≡ 6 mod 7}
Consequently, Z is partitioned into the seven congruence
classes under congruence modulo 7, Z/7Z.

Intercession 2024 Baloloy 12

More properties

For a given modulo m ≥ 1, if a′ ≡ a and b′ ≡ b

a′ + b′ ≡ a + b
a′ − b ′ ≡ a − b
a′b′ ≡ ab
a+c≡b+c
 ac ≡ bc
ak ≡ b k

Intercession 2024 Baloloy 13

Exhibit for properties of mod

a. What is the remainder when 100100 is divided by 11? answer

is 1
b. What is remainder when 70210 is divided by 7? answer is
2 c. What is the least residue of 1006 modulo 49? answer is
15 d. What is the least residue of 494 modulo 23? answer is
 12 e. What is the least residue of 5099 modulo 17? answer is
16

Intercession 2024 Baloloy 14

Powers of 10 modulo 7

1 ≡ 1 mod 7
10 ≡ 3 mod 7
102 ≡ 2 mod 7
103 ≡ 6 mod 7
104 ≡ 4 mod 7
 105 ≡ 5 mod 7
106 ≡ 1 mod 7

This means that the smallest power of 10 that will gave a

remainder of 1 is 6.

Intercession 2024 Baloloy 15

Divisibility revisited

Matt finds that he has an extraordinary social security number. Its

nine digits contain all the numbers from 1 through 9. They also
form a number such that, when read from let to right, its first two
digits form a number divisible by 2, its first three digits form a
number divisible by 3, its first four digits form a number divisible by
 4, and so on, until the complete number is divisible by 9. What is
Matt’s social security number?

Intercession 2024 Baloloy 16

Divisibility by 7
Show that 3816547 is divisible by 7.

7·1=7
4 · 3 = 12
5 · 2 = 10
6 · 6 = 36
1·4=4
8 · 5 = 40
3·1=3
The sum of the product is 112. Because 7|112 therefore 7|3816547
Intercession 2024 Baloloy 17

Clock arithmetic
The clock face yields the finite set 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11. One type of enrichment activity involving congruences uses
the arithmetic of a 12- hour clock.
Intercession 2024 Baloloy 18

Check your progress

Evaluate each of the following using a 12-hour and 24-hour

(military time) clock.
1. 6 ⊕ 10 =
2. 5 ⊕ 9 =
3. 7 ⊖ 11 =
4. 5 ⊖ 10 =
5. 0800△2000 =
6. 600△2200 =

Intercession 2024 Baloloy 19

Day-of-week arithmetic

Similar example involves day-of-the-week arithmetic. If we

associate each day of the week with a number, Mon = 1, Tue= 2,
Wed= 3, Thurs= 4, Fri= 5, Sat= 6 and Sun= 7, then 6 days after
Friday is Thursday and 16 days after Monday is Wednesday.
Symbolically, we write

5⊞6=4
1 ⊞ 16 = 3

Intercession 2024 Baloloy 20

Exhibit 1- calculate a day of the week

September 11, 1974 was the 254th day of the year 1974 in the
Gregorian calendar. There were 111 days remaining until the
end of the year. The day of the week was Wednesday.

What day of the week is Sept 11, 2001?

The answer is Tuesday!

Intercession 2024 Baloloy 21

Historical note
The Julian calendar, introduced by Julius Caesar in 46 BC and
named after him, contained 12 months and 365 days. Every fourth
year, an additional day was added to the year to compensate for
the difference between an ordinary year and a solar year.
However, a solar year actually consists of 365.2422 days, not
365.25 days as assumed by Caesar. The difference between
these numbers is 0.0078 days. Although this is a small number,
after a few centuries had passed, the ordinary year and the solar
year no longer matched. If something were not done to rectify the
situation, after a period of time the summer season in the northern
hemisphere would be in December and the winter season would
be in July. To bring the seasons back into phase, Pope Gregory
removed 10 days from October in 1582. The new calendar was
called the Gregorian calendar and is the one we use today. This
calendar did not win general acceptance until 1752.
Intercession 2024 Baloloy 22
A leap year formula
The calculation in exhibit 1 required that we consider whether the
intervening year contained a leap year. There is a formula, based
on modular arithmetic, that can be used to determine which years
are leap years. The calendar we use today is called the Gregorian
calendar. This calendar differs from the Julian calendar in that
leap years do not always occur every fourth year. Here is the rule:
Let Y be the year. If Y ≡ 0 mod 4, then Y is a leap year unless Y
≡ 0 mod 100. In that case, Y is not a leap year unless Y ≡ 0 mod
400 . Then Y is a leap year. Using this rule, 2008 is a leap year
because 2008 ≡ 0 mod 4, and 2013 is not a leap year because
2013 ̸≡ 0 mod 4. The year 1900 was not a leap year because
1900 ≡ 0 mod 100 but 1900 ̸≡ 0 mod 400. The year 2000 was a
leap year because 2000 ≡ 0 mod 100 and 2000 ≡ 0 mod 400.

Intercession 2024 Baloloy 23

Computing the day of the week
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, given by
y c
5⌋ + ⌊ 4⌋ + ⌊ 4⌋ + d + y − 2c}mod7

x = {⌊13m − 1
d is the day of the month.
m is the month using 1 for March, 2 for April,. . . ,12 for
February. y is the last two digits of the year if the month is
March through December; if the month is January or February,
y is the last two digits of the year minus 1.
c is the first two digits of the year.
x is the day of the week (using 0 for Sunday, 1 for Monday, . . . ,6
for Saturday)
Intercession 2024 Baloloy 24

Arithmetic operations mod 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.

Evaluate:
1. (37 + 45) mod 12
2. (48 − 21) mod 6
3. (15 − 32 mod 7
4. (33 · 41) mod 17
5. (26 · 11) mod 15
Intercession 2024 Baloloy 25

More exercise

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

will be 59 hours from now? what time was it 62 hours ago? 2. If
today is Friday, what day of the week will it be 25 days from
now? what day of the week was it 32 days ago?
3. Find the additive inverse and the multiplicative inverse, if it
exist, of the given number 4 mod 9, 7 mod 10, and 6 mod
15.
Intercession 2024 Baloloy 26

Solving congruence equations

When solving a congruence equation, it is necessary to check only

the whole numbers less than the modulus. For the congruence
equation 3x + 5 ≡ 3 mod 4, we needed to check only 0, 1, 2, and
3. Each time a solution is found, additional solutions 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.

Solve: 4x + 1 ≡ 5 mod 12
Intercession 2024 Baloloy 27

Additive inverse

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 that 3 + 5 =
8; that is, the sum of a number and its additive inverse equals the
modulus. Using this fact, we can easily find the additive inverse of
a number for any modulus.

Find the additive inverse of 6 in mod 12 arithmetic.

Intercession 2024 Baloloy 28

Multiplicative inverse

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 5 · 3 ≡ 1 mod 7. (Here we will
concern ourselves only with natural numbers less than the modulus.)
To find the multiplicative inverse of a mod m, solve the modular
equation ax ≡ 1 mod m for x.

Find the multiplicative inverse of 5 in mod 11 arithmetic. Intercession 2024

Baloloy 29

Exhibit: unit fractions with maximal period

 1
7= 0.142857
1
17= 0.0588235294117647

1
19= 0.052631578947368421

1
23= 0.0434782608695652173913
Intercession 2024 Baloloy 30

Primitive roots
 What are the values of p for which this is true?

10e ≡ 1 mod p

where e = p − 1

Intercession 2024 Baloloy 31

Periodic fractions
Table of the prime p with least exponent e
prime least exponent e
 31
76
11 2
13 6
17 16
19 18
23 22
29 28
31 15
37 3
41 5
43 21
Intercession 2024 Baloloy 32

Periodic fractions
Table of the prime p with least exponent e
prime least exponent e
 47 46
53 13
59 58
61 60
67 33
71 35
73 8
79 13
83 41
89 44
97 96
Intercession 2024 Baloloy 33

What exactly is the value of the "baby

monster" 1
97?
 Because 1096 ≡ 1 mod 97, the period of 197 has 96 places.
Starting to calculate these by ordinary division, we have
1 5 5
97 = 0.01030927835 97 . The remainder 97 , expressed decimally,
1
is five times as large as 97 , and the number represented by the
next 11 digits is five times as large as the number represented by
the first 11,
or 05154639175, and 5 597 =2597 is the new remainder. The
numerator is again a convenient multiplier because to multiply 25
we merely multiply by 100 and divide by 4.

Intercession 2024 Baloloy 34

What exactly is the value of the "baby

monster" 1
97?
Doing this to the 22-nd digit already found, we have
1.030927835054639175, which, after dividing by 4, gives the next
22 places: 2577319587628865979375 with a remainder of 25
(25) = 625. But 625
43
97 = 6 97 , so we add 6 to the previous result,
writing 81 instead of 75 in the last two places, and proceeding with
the remainder, 43. The next four digits by actual division of 43 by
97 are 4432, and since, after 48 places or a half period,
corresponding digits add up to 9, we easily obtain the whole period
of 96 digits, having actually divided for only 15 of them. Half of the
period is:

1
97= 0.010309278350515463917525773195876288659793814432
. . . Intercession 2024 Baloloy 35
Order of an integer
 Let a, m ∈ Z with m > 0 and (a, m)=1. The order of a modulo m,
denoted ordma is the least positive integer n for which an ≡ 1
mod m.

Intercession 2024 Baloloy 36

Primitive root

Let r, m ∈ Z with m > 0 and (r, m) = 1. Then r is said to be a

primitive root modulo m if
 ordmr = ϕ(m)

Note: ϕ(m) Euler phi-function is the number of positive integers

less than or equal to n that are relatively prime to n.

Intercession 2024 Baloloy 37

Congruences and applications

Engelbert Baloloy
ebaloloy@[Link]

Ateneo de Naga University

October 2, 2024
Intercession 2024 Baloloy 38