Congruences and Modular Arithmetic

Steven T. Dougherty, André Leroy and Esengül Saltürk

“But in my opinion, all things in nature occur mathematically.” –
René Descartes

1 Introduction

The notion of congruence appeared very early in the history of humanity. This
is due to the fact that there are many cyclic events observed in nature. In
astronomy, nearly all objects are turning over themselves and around one an-
other, so that it is natural to divide time accordingly: a year corresponds to
one cycle of the earth around the sun, a month is derived from a cycle of the
moon, a day from the time it takes for the sun to rise or set in the same place.
We count days or months in a year, but when a year is over, the counting of
days or months starts over. Congruences and modular arithmetic will make the
process of “starting over” or “wrapping around” formal. On top of examples
that appear in nature, they have numerous applications in computer science, in
communications, and of course, in mathematics.
People are often aware of the concept of modular arithmetic without knowing
it. For example, the hours in a day are read modulo 12 (or 24 in certain
instances). If it is 9:00 P.M. and someone asks you what time it will be in 4
hours, you will likely say 1:00 A.M. This is because 9 + 3 = 12 and at 12 the
clock resets to 0. That is, one hour after 12:00 is 1:00. This is the essence of
modular arithmetic. If it is 7:00 and someone asks you what time it will be in
56 hours, you could notice that after 48 hours it will be 7:00, so it is the same
as asking what time it will be in 8 hours. Then taking 7 + 8 = 15 you realize
that this is 3 hours after 12:00, namely 3:00. This is exactly modular arithmetic
modulo 12.
Another example is the days of the week. Take Sunday as day 1, Monday as
day 2, Tuesday as day 3, Wednesday as day 4, Thursday as day 5, Friday as day
6 and Saturday as day 7. If it were Tuesday and you are asked what day it will
be in 10 days, you will say Friday. This is because adding 7 is essentially adding
0. Therefore, it is like adding 3 days to Tuesday (which is day 3), so that you
get day 6 which is Friday. This is modular arithmetic modulo 7. Likewise, the
months can be thought of as modular arithmetic modulo 12. For example, if it
is February and someone asks you what month it will be in 14 months, you will
say April, because in 12 months it will be February again so you are really just
adding 2.
For the musical reader, a scale would be yet another example. Say you are
playing in the key of C. Then the notes are written as C D E F G A B C. In
other words, your return to the first note on the eighth note. Similarly, if you are
playing in the key of D the notes are written as D E F] G A B C] D. In any key,
you have the notes very much arranged like the hours on a clock. Specifically,
if you move 24 hours ahead you are at the same time but in a different day.
Likewise, if you move 8 notes higher, you are on the same note but in a different
octave.

1
2 Computing modulo n ∈ N
We can now make these ideas rigorous. Let Z be the set of integers and let
n ∈ N+ = N \ {0}. We introduce the following relation on Z denoted by ≡
which equates two integers if their difference is a multiple of n.

Definition 1 Let n ∈ N and a, b ∈ Z,

a ≡ b (mod n) if and only if n divides b − a. (1)

For instance we may be interested only by the parity of an integer. In this

case we can take n = 2. Two integers are then in relation if and only if their
difference is an even number. In other words all even integers are related and
all odd integers are related. This gives that the integers are divided into two
classes: the odd and even numbers, that is every integer a either satisfies a ≡ 0
(mod 2) or a ≡ 1 (mod 2).

Example 1 We have the following instances where two numbers are equivalent
under this relation.
1. We have that 20 ≡ 6 (mod 7) since 6 − 20 = −14 = −2 · 7, giving that 7
divides 6 − 20.
2. We have that 24 ≡ 112 (mod 11) since 112 − 24 = 88 = 8 · 11, giving that
11 divides 112 − 24.
3. We have that 99 ≡ 13 (mod 43) since 13 − 99 = −86 = −2 · 43, giving
that 43 divides 13 − 99.

Example 2 1. We have 10 ≡ 1 (mod 3), 100 ≡ 1 (mod 3) and 1000 ≡ 1

(mod 3). In fact, for any n, 10n ≡ 1 (mod 3). This fact is the basis for
the divisibility criteria that everyone learns in primary schools. We will
come back to these criteria in the section on applications.

2. It is not too difficult to check that 25 ≡ 2 (mod 5). Now can you check
37 ≡ 3 (mod 7)? And 1219 ≡ 12 (mod 19)? The answer will be given by
the so-called “Fermat’s Little Theorem”.

The modulo relation defined above is a special kind of relation that was
discussed in Chapter ??. Namely, it is an equivalence relation. We shall prove
this now. Throughout, we use the fact that if n divides b − a then b − a = kn
for some k ∈ Z.

Theorem 1 The relation defined in Equation (1) is an equivalence relation on

the set of all integers Z.

Proof: We need to prove that the relation is reflexive, symmetric, and

transitive.

2
 1. (Reflexive Property): Let a ∈ Z. Then a − a = 0 · n. This gives that
a ≡ a (mod n) and the relation is reflexive.
2. (Symmetric Property): If a ≡ b, then b − a = kn which gives that
a − b = (−k)n. Therefore, b ≡ a (mod n).
3. (Transitive Property): If a ≡ b and b ≡ c, then b − a = kn and
c − b = gn. Then c − a = b − a + c − b = kn + gn = (k + g)n which gives
that a ≡ c (mod n).
Therefore, we have that this is an equivalence relation. 

As we know, an equivalence relation defined on a set E, leads to a partition

of E, see Chapter ??. In our case, we have a partition of Z given by this
equivalence relation. To describe it, we introduce the set nZ = {nk | k ∈ Z},
which contains all multiples of n.

Example 3 We have the following:

1. 5Z = {. . . , −15, −10, −5, 0, 5, 10, 15, . . . }.
2. 7Z = {. . . , −21, −14, −7, 0, 7, 14, 21, . . . }.
3. 10Z = {. . . , −30, −20, −10, 0, 10, 20, 30, . . . }.

Then we define the set a + nZ = {a + nk | k ∈ Z}.

Example 4 We have the following:

1. 1 + 5Z = {. . . , −14, −9, −4, 1, 6, 11, 16, . . . }.
2. 2 + 7Z = {. . . , −19, −12, −5, 2, 9, 16, 23, . . . }.
3. 6 + 10Z = {. . . , −24, −14, −4, 6, 16, 26, 36, . . . }.

We see that each number in Z when divided by n must be in a unique set

of the form a + nZ, where a is the remainder when the number is divided by n.
Then we have the following.

Z = nZ ∪ (1 + nZ) ∪ (2 + nZ) · · · ∪ ((n − 1) + nZ).

Note that not only is the union of the sets (a + nZ) equal to the integers,
but also that they are disjoint – that is there is no element in the intersection
of any two distinct sets. Therefore, these sets form a partition of the integers.

Example 5 Consider the relation modulo 5. Every integer must be in one of

the following boxes:

... −15 −10 ... −14 −9 ... −13 −8

−5 0 5 −4 1 6 −3 2 7
10 15 ... 11 16 . . . 12 17 . . .

3
 ... −12 −7 ... −11 −6
−2 3 8 −1 4 9
13 18 . . . 14 19 . . .

We need to give a name to each of the boxes. It seems natural to give them
the name that is the number in the center of each box. Namely, if a number
can be written as 5k + s, 0 ≤ s < 5, (that is the remainder of the number
when divided by 5 is s) then we can associate the number with s. Since it is an
equivalence relation, it makes sense to call these boxes:

0, 1, 2, 3, 4.

We note that

Z = 5Z ∪ (1 + 5Z) ∪ (2 + 5Z) ∪ (3 + 5Z) ∪ (4 + 5Z).

Being a partition of Z, the intersection of any two distinct sets of the form
a + nZ and b + ZZn is empty. These subsets are the equivalence classes, there
are n of them.

Definition 2 We let the set Zn = {0 + nZ, 1 + nZ, 2 + nZ, . . . , (n − 1) + nZ}.

From this point on, when describing the elements of the set Zn we shall drop
the notation nZ. We write {0, 1, . . . , n − 1} for the set Zn when no confusion
will arise. Coming back to our example, for n = 2 we have two classes: the odd
integers and the even integers. In other words Z2 = {0, 1}.
We note that we can really take any element in a + nZ as its representative,
but we shall always take the smallest non-negative element in a + nZ to be its
representative. This set is the set of elements which are equivalent to a modulo
n and it is called the remainder class of a modulo n or congruence class of a
modulo n.

Example 6 We have the following:

1. In Z5 , 1 = {x ∈ Z | x ≡ 1 (mod 5)} = 1 + 5Z.

2. In Z7 , 2 = {x ∈ Z | x ≡ 2 (mod 7)} = 2 + 7Z.

3. In Z10 , 6 = {x ∈ Z | x ≡ 6 (mod 10)} = 6 + 10Z.

Corollary 1 Let a, b ∈ Z. We have the following properties for the remainder

classes.
1. We have a + nZ = b + nZ if and only if a ≡ b (mod n).

2. We have a + nZ 6= b + nZ if and only if a + nZ ∩ b + nZ = ∅.

3. The number of remainder classes modulo n is exactly n.

Proof:

4
 1. Let a + nZ = b + nZ. We know that a ∈ a since a ≡ a (mod n). Since
a + nZ = b + nZ, we have a ∈ b + nZ, which gives that a ≡ b (mod n).
For the converse we have a ≡ b (mod n). Take x ∈ a + nZ. This means
that x ≡ a (mod n). By the transitive property, we have x ≡ b (mod n)
which means that x ∈ b + nZ. Hence, a + nZ ⊂ b + nZ. Similarly take an
element y ∈ b + nZ. This means that y ≡ b (mod n). By the transitive
property we have y ≡ a (mod n) which means that y ∈ a + nZ. Hence
b + nZ ⊂ a + nZ. Finally we have that a + nZ = b + nZ.

2. If a + nZ ∩ b + nZ = ∅ then it is obvious that a + nZ 6= b + nZ. For

the converse, assume a + nZ ∩ b + nZ 6= ∅. Then there exists an element
x ∈ a + nZ ∩ b + nZ. If x ∈ a + nZ, we have that x ≡ a (mod n) and
if x ∈ b + nZ, we have that x ≡ b (mod n). Hence, we have that a ≡ b
(mod n) which means that a + nZ = b + nZ from the first property of the
corollary.

3. As we know the following set denotes the remainder classes modulo n:

Zn = {0, 1, . . . , n − 1}. We show that the elements of Zn are disjoint. If
x + nZ = y + nZ where x + nZ, y + nZ ∈ Zn , then x ≡ y (mod n) which
means that n | (y − x). On the other hand if x + nZ = y + nZ, then
0 ≤ x < y ≤ n − 1 which means that y − x < n. The last two results,
n | (y − x) and y − x < n give a contradiction. Therefore, the remainder
classes are disjoint. We need to also show that there are n elements in Zn .
Take x ∈ Zn . Divide n by x, by the Division Lemma given in Chapter ??,
we get x = nq + r, 0 ≤ r < n. We have that x ≡ r (mod n) which means
that x + nZ = r + nZ where 0 ≤ r < n. This completes the proof.

From this point on, we shall dispense with the notation a + nZ for elements
in Zn , and we shall simply write the elements as the set {0, 1, 2, . . . , n − 1}.
Moreover, we shall indicate multiplication in the standard ways, in other words
ab = a(b) = a · b. We only use the a · b notation when we want to stress that
the operation is multiplication.
Let us mention another point of view on congruence classes modulo n ∈ N.
Let ρn : Z → {0, 1, . . . , n − 1} be the function such that ρn (a) is the remainder
of a while divided by n. The different classes modulo n are given by the different
pre-images of ρn . In other words, we can write the different classes of congruence
modulo n as the equivalence class of a, that is {i | ρn (i) = a}. It is easy to see
that what we have defined is the following.

Let n ∈ N, a ∈ Z, then
ρn (a) = a (mod n),
where a is the smallest non-negative representative of that class in Zn .
Alternatively, we can consider ρn (a) to be the remainder when a is divided
by n.

Example 7 We illustrate this function:

5
 1. ρ7 (23) = 2.
2. ρ11 (58) = 3.

3. ρ9 (25) = 7.
4. ρ7 (74) = 4.
5. ρ12 (116) = 8.

6. ρ5 (44) = 4.
7. ρ10 (55) = 5.
8. ρ21 (48) = 6.
9. ρ2 (131) = 1.

10. ρ17 (39) = 5.

1. ρ−1
5 (0) = {. . . , −20, −15, −10, −5, 0, 5, 10, 15, 20, . . . }.

2. ρ−1
4 (1) = {. . . , −23, −19, −15, −11, −7, −3, 1, 5, 9, 13, 17, 21, . . . }.

3. ρ−1
7 (5) = {. . . , −37, −30, −23, −16, −9, −2, 5, 12, 19, 26, 33, 40, . . . }.

4. ρ−1
9 (8) = {. . . , −46, −37, −28, −19, −10, −1, 8, 17, 26, 35, 44, 53, . . . }.

We can now do arithmetic with the classes as we do arithmetic with the

integers. This means it is possible to add and multiply these classes in a very
reasonable way.

For a, b ∈ Z:

a (mod n) + b (mod n) ≡ (a + b) (mod n)

and
a (mod n) · b (mod n) ≡ ab (mod n).

These definitions lead to a question: are they well defined? In other words
are these definitions independent of the elements used to represent the classes?
This means if a ≡ a0 (mod n) and b ≡ b0 (mod n), do we have a + b ≡ a0 + b0
(mod n) and ab ≡ a0 b0 (mod n)? We can now prove this result.

Theorem 2 Addition and multiplication modulo n are well defined. That is, if
a ≡ a0 (mod n) and b ≡ b0 (mod n) then

a+b ≡ a0 + b0 (mod n)
and
ab ≡ a0 b0 (mod n).

6
 Proof: If a ≡ a0 (mod n), then a = kn + s and a0 = k 0 n + s for some
integers k and k 0 . If b ≡ b0 (mod n), then b = gn + t and b0 = g 0 n + t for some
integers g and g 0 .
Then a + b = kn + s + gn + t = (k + g)n + s + t which gives a + b ≡ a0 + b0
(mod n).
For multiplication, we have ab = (kn + s)(gn + t) = kgnn + sgn + ktn + st =
(kgn + sg + kt)n + st which gives ab ≡ a0 b0 (mod n). 

Example 8 We illustrate this theorem with the addition and multiplication ta-
bles modulo 2 and modulo 3.
+ 0 1 · 0 1
0 0 1 0 0 0
1 1 0 1 0 1

+ 0 1 2 · 0 1 2
0 0 1 2 0 0 0 0
1 1 2 0 1 0 1 2
2 2 0 1 2 0 2 1

Example 9 We now give the addition and multiplication tables modulo 4.

+ 0 1 2 3 · 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 1 2 3 0 1 0 1 2 3
2 2 3 0 1 2 0 2 0 2
3 3 0 1 2 3 0 3 2 1

We note that there are significant differences between these and the previous
two. For example, look at the row for multiplication by 2. We have 2(2) ≡ 0
(mod 4). In the previous examples there were no instances where two non-zero
numbers were multiplied to get 0. Moreover, we have 2(3) ≡ 2(1) (mod 4). In
the previous examples, each equation of the form ax ≡ b (mod n) had a unique
solution, whereas here 2x ≡ 2 (mod 4) has two solutions. This is quite different
from arithmetic in the integers, rational or reals.

Lemma 1 Let n ∈ N be a positive integer. Addition and multiplication in Zn

have the following properties.
1. (Associativity of addition and multiplication) For every a, b, c ∈ Z we have

(a + b) + c (mod n) ≡ a + (b + c) (mod n)

and
(a · b) · c (mod n) ≡ a · (b · c) (mod n).

2. (Additive and multiplicative identities) For every a ∈ Z we have

a+0 (mod n) ≡ a (mod n)

and
a · 1 ≡ a (mod n).

7
 3. (Additive inverses) For every a ∈ Zn there exists b ∈ Zn such that a + b ≡
b + a ≡ 0 (mod n).

4. (Commutativity of addition and multiplication) For every a, b ∈ Z, we

have
a + b ≡ b + a (mod n)
and
a·b≡b·a (mod n).

5. (Distributive Law) For all a, b, c ∈ Z a · (b + c) ≡ a · b + a · c (mod n).

Proof:
1. For any a, b, c ∈ Z we have (a+b)+c = a+(b+c) and (ab)c = a(bc). Then
simply take each side (mod n) to get (a + b) + c (mod n) ≡ a + (b + c)
(mod n) and (a · b) · c (mod n) ≡ a(b · c) (mod n).

2. Let a ∈ Z. Then in the integers we have a + 0 = a and a(1) = a. Taking

both sides (mod n) we have a + 0 ≡ a (mod n) and a(1) ≡ a (mod n).
3. Let a ∈ Z/nZ, then perform the following operation in the integers, b =
n − a. Then a + (n − a) ≡ n ≡ 0 (mod n).
4. For any a, b, c ∈ Z we have a + b = b + a and a · b = b · a. Then simply take
each side (mod n) to get a + b ≡ b + a (mod n) and a · b ≡ b · a (mod n).
5. For any a, b, c ∈ Z we have a · (b + c) = a · b + a · c. Then simply take each
side (mod n) to get a · (b + c) ≡ a · b + a · c (mod n).


In fact, what the lemma says is that Zn is an algebraic structure called a

ring. We shall describe these structures more deeply later in the text.

Example 10 Let us give the tables of addition and multiplication for n = 6

+ 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 1 2
5 5 0 1 2 3 4 5 0 5 4 3 2 1

We can easily verify all of the properties given in Lemma 1. We can see that
both operations are commutative since both tables are symmetric. Moreover,
we note that Z6 is much more like Z4 than it is like Z2 or Z3 . Namely, we
have 2(3) = 3(2) ≡ 0 (mod 6). That is, there exists non-zero elements that can
multiply together to get 0.

8
 Since we can multiple these elements we can also doing other arithmetic
operations associated with multiplication. For example, we can take an element
a and square it, since a2 = a(a). This is actually a very important operation in
modular arithmetic and has numerous uses. In the next examples, we can see
how different this operation is in modular arithmetic than it is in the integers.

Example 11 As an example of the difference between arithmetic in the integers

and modular arithmetic, consider the squares modulo 8.

x 0 1 2 3 4 5 6 7
2
x (mod 8) 0 1 4 1 0 1 4 1

We note first of all that there are 4 solutions to the equation x2 = 1, namely
1, 3, 5, and 7. We also note that 42 = 0, so there is a non-zero element that
when squared is 0. These types of things do not occur in the integers. To further
illustrate the differences with Z, consider the cubes in Z8 . We can compute this
table simply by multiplying the elements in the table for x2 by the element x.

x 0 1 2 3 4 5 6 7
x3 (mod 8) 0 1 0 3 0 5 0 7

Notice that there are 5 solutions to x3 = x which cannot happen in the integers,
since the polynomial x3 −x = 0 can have at most 3 solutions in the real numbers.
Moreover, we have 3 non-zero elements that satisfy x3 = 0, this also does not
happen in the integers.
If we take it further, to x4 , it looks even more unusual.

x 0 1 2 3 4 5 6 7
x4 (mod 8) 0 1 0 1 0 1 0 1

Here the fourth power of any number is either 1 or 0 depending on whether it

is even or odd.

We notice that we had examples of elements such that xk ≡ 0 (mod n) for

some k and examples of elements such that x2 ≡ x (mod n). These elements
are important enough to merit their own definition.

Definition 3 An element a ∈ Zn is idempotent if a2 ≡ a (mod n). An element

a ∈ Zn is nilpotent if ak ≡ 0 (mod n) for some k.

Example 12 We contrast the previous example with the squares modulo a prime
number, for example 11.

x 0 1 2 3 4 5 6 7 8 9 10
x2 (mod 11) 0 1 4 9 5 3 3 5 9 4 1

Here the behavior is much more similar to the way squares behave in the integers.
We note that there are no non-zero elements whose square is 0 and no equation
of the form x2 ≡ a (mod 11) has more than 2 solutions. We note as well, that
precisely half of the non-zero elements are squares, namely 1, 3, 4, 5, and 9.

9
Example 13 We can take a look at another set of squares modulo a prime.
Consider the prime 5.

x 0 1 2 3 4
x2 (mod 5) 0 1 4 4 1

One of the most interesting aspects here is that 4 ≡ −1 (mod 5). This means
that in Z5 , the equation x2 + 1 = 0 has two solutions. In other words, there
are x such that x2 = −1, or in the notation that we have been using x2 ≡ −1
(mod 5). This means that −1 is a square, which certainly does not happen in
the integers or the real numbers. This algebraic fact can be exploited in many
ways in number theory and abstract algebra.

Exercises for Section 2

A Exercises

Exercise 1 Find the element in Zn for each of the following:

1. 33 (mod 7).
2. 42 (mod 12).
3. 51 (mod 11).

4. 36 (mod 6).
5. 113 (mod 8).
6. 233 (mod 21).

7. 178 (mod 24).

8. 19 (mod 8).
9. 1000 (mod 9).
10. 1024 (mod 32).

Exercise 2 Perform the following calculations:

1. 5(3 + 4 + 5) + 7(3 + 1 + 9) (mod 11).

2. 3(1 + 4 + 3 + 2) + 2(2 + 3 + 2 + 1) (mod 5).

3. 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 (mod 10).
4. 3(2) + 3(4) + 5(2) + 3(6) (mod 9).

5. 2(7) + 8(2) + 3(7) + 5(6) (mod 13).

6. 2(3)(4)(5)(6)(7) (mod 11).
7. 6(5)(4)(3)(2) (mod 7).
8. 210 (mod 11).

10
 9. 36 (mod 7).
10. 424 (mod 8).

Exercise 3 Find the remainder of the following numbers modulo 10.

1. 322 .
2. 4162 .

3. 510598 .
4. 65679 .
5. 11321 .
6. 25! + 7351 .

7. 402! + 835 .

Exercise 4 Show that 93 | (25n+6 + 53n · 29) where n ∈ N.

Exercise 5 Find x2 for each x ∈ Z13 .

Exercise 6 Find x2 for each x ∈ Z16 .

Exercise 7 Find x3 for each x ∈ Z9 .

Exercise 8 Find x4 for each x ∈ Z10 .

Exercise 9 Find all solutions to x3 ≡ x (mod 16) by examining all the possi-
bilities.

Exercise 10 Find all solutions to x3 ≡ −x (mod 13) by examining all the

possibilities.

Exercise 11 Prove that if n = k 2 , k ≥ 2, then there is always a non-zero

element x in Zn with x2 ≡ 0 (mod n).

B Exercises

Exercise 12 Give the addition and multiplication tables for Z5 .

Exercise 13 Determine how many times 0 appears in the multiplication table

for Z16 .

Exercise 14 Determine how many times 0 appears in the multiplication table

for Zp , when p is a prime.

Exercise 15 Determine how many times 1 appears in the multiplication table

for Z10 .

Exercise 16 Determine how many times 1 appears in the multiplication table

for Zp , when p is a prime.

11
Exercise 17 Determine how many times 3 appears in the multiplication table
for Z7 . Determine how many times 3 appears in the multiplication table for Zp ,
when p > 3 is a prime.
Exercise 18 Let ac ≡ bc (mod n) and gcd(c, n) = 1. Show that a ≡ b (mod n).
Exercise 19 Let ab ≡ cd (mod n), b ≡ d (mod n) and gcd(b, n) = 1. Prove
that a ≡ c (mod n).
C Exercises
Exercise 20 Write a computer program to do modular arithmetic modulo n,
for a chosen n, without using any built in modulo functions. Begin by writing a
function that takes a number modulo n, then a function that performs addition
and finally one that performs multiplication.
Exercise 21 Determine how many times 0 appears in the multiplication table
for Zn . Do this by taking several examples for small n. Then try and develop
a conjecture (You can split up the conjecture for different forms of n. You
might try numbers of the form pe and then for numbers of the form ab where
gcd(a, b) = 1.) Prove whichever of these conjectures you can.

3 Invertible elements and zero divisors

We ended the previous section with some examples that might look a bit strange.
In this section, we will try to feed the curiosity of the reader by giving some
characterization of these elements.
The next theorem offers characterizations of invertible elements of Zn , namely
those elements for which a multiplicative inverse exists.

Definition 4 An element a ∈ Zn is invertible if there exists an element b ∈ Zn

such that ab ≡ ba ≡ 1 (mod n).

The first thing we notice is that 0 can never be an invertible element.

Example 14 Consider the elements in Z5 . Here 1(1) ≡ 1 (mod 5), 2(3) ≡
1 (mod 5) and 4(4) ≡ 1 (mod 5). Therefore, 1, 2, 3, and 4 are all invertible
elements in Z5 .
Example 15 Consider the element 2 in Z6 . We have
2(0) ≡ 0 (mod 6)
2(1) ≡ 2 (mod 6)
2(2) ≡ 4 (mod 6)
2(3) ≡ 0 (mod 6)
2(4) ≡ 2 (mod 6)
2(5) ≡ 4 (mod 6).

12
We note that there is no b with 2b ≡ 1 (mod 6). Therefore, 2 is not invertible in
Z6 . However, 1(1) ≡ 1 (mod 6) and 5(5) ≡ 1 (mod 6) are invertible elements.
It is easy to verify that 3 and 4 are also not invertible. Therefore, in Z6 , the
only invertible elements are 1 and 5.

Theorem 3 The multiplicative inverse of an element in Zn is unique.

Proof: Let a be an invertible element in Zn . Assume b and c are inverses

of a. Then

ab = ac
bab = bac
1b = 1c
b = c.

Therefore, the inverse is unique. 

We illustrate an elementary idea brought out in these examples in the fol-

lowing theorem.

Theorem 4 In Zn , the elements 1 and n − 1 are always invertible.

Proof: We have 1(1) = 1 ≡ 1 (mod n) and (n−1)(n−1) = n2 −2n+1 ≡ 1

(mod n). Therefore, 1 and n − 1 are both invertible elements in Zn . 

The intuitive way to think about the previous theorem is to say that both 1
and −1 are invertible elements in Zn .
We can now define one of the unusual things that happened in the previous
examples.

Definition 5 An element a ∈ Zn a 6= 0, is a zero divisor if there exists an

element b ∈ Zn , b 6= 0, such that ab ≡ 0 (mod n).

Example 16 Consider the element 8 in Z12 . Here 8(3) ≡ 0 (mod 12). There-
fore, both 8 and 3 are zero divisors in Z12 . Note also that 4(3) ≡ 0 (mod 12)
and so 4 is also a zero divisor. We note that both 4(3) and 8(3) are equivalent
to 0 (mod 12). This shows that, given a = 3, there is not a unique zero divisor
b in the above definition.

13
Example 17 We can look at all the non-zero elements in Z12 .
element invertible zero divisor
1 1(1) ≡ 1 (mod 12) No
2 No 2(6) ≡ 0 (mod 12)
3 No 3(4) ≡ 0 (mod 12)
4 No 4(3) ≡ 0 (mod 12)
5 5(5) ≡ 1 (mod 12) No
6 No 6(2) ≡ 0 (mod 12)
7 7(7) ≡ 1 (mod 12) No
8 No 8(3) ≡ 0 (mod 12)
9 No 9(4) ≡ 0 (mod 12)
10 No 10(6) ≡ 0 (mod 12)
11 11(11) ≡ 1 (mod 12) No
We note a few interesting things in this table. The first is that no element is
both invertible and a zero divisor. We shall prove this in the next few theorems.
Secondly the equation x2 ≡ 1 (mod 12) has 4 solutions, namely 1, 5, 7, and 11.
Notice also that the equation 4x ≡ 0 (mod 12) has 4 solutions, namely 0, 3, 6,
and 9. Later in the chapter, we shall determine precisely how many solutions
every linear equation has.
We continue with an easy result which shows that being invertible prohibits
an element from being a zero divisor, as we have seen in the previous example.
Theorem 5 If an element in Zn is invertible then it is not a zero divisor.

Proof: Let a ∈ Zn , a invertible. Then there exists an element a−1 with

aa ≡ a a ≡ 1 (mod n). If ab ≡ 0 (mod n) then a−1 ab ≡ a−1 0 ≡ 0 (mod n).
−1 −1

This gives that b ≡ 0 (mod n) and so a cannot be a zero divisor. 

The next result shows how to use the Euclidean algorithm to not only prove
that an element is invertible but also to find its inverse.
Theorem 6 If gcd(a, n) = 1 then a is invertible in Zn .

Proof: If gcd(a, n) = 1 then there exist integers b and c with ab+cn = 1 by

Theorem Integer:Theorem:EuclideanAlgorithm. Reading this equation modulo
n we get ab ≡ 1 (mod n). 

Example 18 We can find the inverse of 5 in Z12 . We begin by taking the Eu-
clidean Algorithm:
12 5 2 1 0
This gives the following:
5 − 2(2) = 1
5 − 2(12 − 2(5)) = 1
5(5) − 2(12) = 1.

Then reading this equation modulo 12 gives 5(5) ≡ 1 (mod 12). Therefore, 5 is
the multiplicative inverse of 5 in Z12 .

14
 Since it is fairly easy to find the inverse of 5 in Z12 by guessing, our next
example will show the technique in a more difficult situation.

Example 19 We can find the inverse of 17 in Z43 . We begin by taking the

Euclidean Algorithm:
43 17 9 8 1 0
This gives the following:

9−8 = 1
9 − (17 − 9) = 1
2(9) − 17 = 1
2(43 − 2(17)) − 17 = 1
2(43) − 5(17) = 1.

We note that −5 ≡ 38 (mod 43). Therefore, reading the equation modulo 43 we

have 38(17) ≡ 1 (mod 43). This gives that the multiplicative inverse of 17 is 38
in Z43 . Certainly this is a harder inverse to find by guessing than the previous
example.

Example 20 We can find the inverse of 13 in Z100 . We begin by taking the

Euclidean Algorithm:
100 13 9 4 1 0
This gives the following:

9 − 2(4) = 1
9 − 2(13 − 9) = 1
3(9) − 2(13) = 1
3(100 − 7(13)) − 2(13) = 1
3(100) − 23(13) = 1.

We note that −23 ≡ 77 (mod 100). Therefore, reading the equation modulo 100
we have 77(13) ≡ 1 (mod 100). This gives that the multiplicative inverse of 13
is 77 in Z100 . We can verify this by noting that 77(13) = 1001 ≡ 1 (mod 100).

Example 21 We can give an intuitive example of how to find an inverse. Sup-

pose we wanted to find the multiplicative inverse of 6 in Z13 . It may not be
obvious to see a number that you can multiply by 6 to get a number that is one
more than a multiple of 13. However, it is easy to see that 6(2) = 12 giving
6(2) ≡ −1 (mod 13). Therefore, 6(−2) ≡ 1 (mod 13). Then, the multiplicative
inverse of 6 is 11 which is congruent to −2 (mod 13).

We can now give a theorem which determines when a number is a zero divisor
in Zn .

Theorem 7 If gcd(a, n) 6= 1, a 6= 0, then a is a zero divisor in Zn .

15
 Proof: Let d = gcd(a, n) > 1. Then a = da0 and n = dn0 , for some
a0 , n0 ∈ Z. Note that n0 6≡ 0 (mod n). Then an0 = da0 n0 = a0 dn0 = a0 n ≡ 0
(mod n). Therefore, a is a zero divisor. 

Example 22 Consider the element 22 in Z40 . We have that the gcd(22, 40) = 2.
Then 22( 40
2 ) = 22(20) = 440 ≡ 0 (mod 40).
Example 23 Consider the element 10 in Z55 . We have that the gcd(10, 55) = 5.
Then 10( 55
5 ) = 10(11) = 110 ≡ 0 (mod 55).
The invertible elements of Zn are called its units and we will denote the set
of units by U (Zn ). In modular arithmetic, the set of units of Zn is also very
often denoted by Z∗n . Let us extract from the above theorem the most important
of these characterizations:

U (Zn ) = {a ∈ Zn | gcd(a, n) = 1}

Example 24 We illustrate this definition with a few examples.

1. U (Z2 ) = {1}
2. U (Z3 ) = {1, 2}
3. U (Z4 ) = {1, 3}
4. U (Z5 ) = {1, 2, 3, 4}
5. U (Z6 ) = {1, 5}
6. U (Z7 ) = {1, 2, 3, 4, 5, 6}
7. U (Z8 ) = {1, 3, 5, 7}
8. U (Z9 ) = {1, 2, 4, 5, 7, 8}
9. U (Z10 ) = {1, 3, 7, 9}
In Chapter ??, we shall discuss in detail the Euler ϕ function which gives the
cardinality of U (Zn ). This function will be very useful in numerous applications
of modular arithmetic.
Let us end this section by looking at some particular facts that occur in Zn
and have no counterparts in Z. We first collect the relevant definitions.

Definition 6 For n ∈ N, we say that a ∈ Zn is

• an invertible element if there exists b ∈ Zn such that ab ≡ 1 (mod n);

• a zero divisor if there exists b ∈ Zn \ {0} such that ab ≡ 0 (mod n);
• an idempotent element if a2 ≡ a (mod n);

• a nilpotent element if there exists k ∈ N such that ak ≡ 0 (mod n).

16
Theorem 8 If a is a nilpotent or idempotent element that is neither 0 nor 1,
then a is a zero-divisor.

Proof: If a is a nilpotent element that is neither 0 nor 1, then for some

k, ak ≡ 0 (mod n). Let k be the minimal such k. This gives that a(ak−1 ) ≡ 0
(mod n), and ak−1 6≡ 0 (mod n). Then we have that a is a zero divisor.
If a is idempotent, a 6= 0, 1, then a2 ≡ a (mod n). Then, we have a2 − a ≡ 0
(mod n) and a(a − 1) ≡ 0. Since neither a nor a − 1 can be 0, we have that a
is a zero divisor. 

The next theorem is sometimes known as Wilson’s theorem (at least the
third part of it is).

Theorem 9 Let n be a positive integer greater than 1.

1. If n = 4 then (n − 1)! ≡ 2 (mod n).

2. If n > 4 is composite then (n − 1)! ≡ 0 (mod n).
3. If n is prime then (n − 1)! ≡ (n − 1) (mod n).

Proof:

1. If n = 4 then (n − 1)! = 3(2)(1) ≡ 2 (mod 4).

2. If n is composite, then n = ab where 1 < a, b < n. We note also that
since n > 4 so we know that we are not in the situation where a = b = 2,
that is 2a < n, so a and 2a are distinct factors of (n − 1)!. If a and b are
distinct, then a and b both appear as one of the factors of (n − 1)! giving
that (n − 1)! ≡ 0 (mod n) since ab ≡ 0 (mod n). If a = b, then a and 2a
are distinct and are both in the factors of (n − 1)! giving that (n − 1)! ≡ 0
(mod n) since 2a(a) ≡ 0 (mod n).
3. Assume n is prime. Consider the equation x2 ≡ 1 (mod n). This gives
x2 − 1 = 0 and then (x − 1)(x + 1) = 0. If this had solutions other than 1
and −1 then there would be zero divisors modulo n which cannot happen.
Therefore, the only elements that are their own multiplicative inverses are
1 and −1. Then, for every factor a of (n − 1)! which is not 1 nor n − 1,
there is an element b that is a factor in (n − 1)! that satisfies ab ≡ 1
(mod n) since each element in Zn is a unit when n is a prime. Therefore,
(n − 1)! ≡ 1(1)(n − 1) ≡ −1 (mod n).

Exercises for Section 3

A Exercises

Exercise 22 1. Find all invertible elements (mod 12).

17
 2. Find all invertible elements (mod 18).
3. Find all invertible elements (mod 11).
4. Find all invertible elements (mod 8).
5. Find all invertible elements (mod 16).

Exercise 23 1. Find all zero divisors (mod 12).

2. Find all zero divisors (mod 18).
3. Find all zero divisors (mod 11).
4. Find all zero divisors (mod 8).
5. Find all zero divisors (mod 16).

Exercise 24 Find the inverses of the following elements:

1. 5 in Z11 .
2. 7 in Z13 .
3. 9 in Z22 .
4. 2 in Z15 .
5. 3 in Z1601 .
6. 11 in Z15 .
7. 32 in Z77 .
8. 15 in Z64 .
9. 51 in Z71 .
10. 101 in Z1024 .

Exercise 25 For the given element a, find the smallest non-zero element b such
that ab ≡ 0 (mod n).
1. 6 in Z32 .
2. 14 in Z52 .
3. 15 in Z50 .
4. 18 in Z27 .
5. 8 in Z520 .
6. 22 in Z77 .
7. 26 in Z39 .
8. 100 in Z844 .
9. 123 in Z777 .

18
 10. 432 in Z900 .
Exercise 26 Find all idempotent and nilpotent elements in Z8 , Z10 and Z16 .
B Exercises
Exercise 27 Prove that a number a in Z2k is a unit if and only if a is odd.
Exercise 28 Show that if an element a, a 6= 0, is not a zero divisor in Zn then
it is invertible.
Exercise 29 Prove that if a2 ≡ 1 (mod n) a 6= ±1, then a + 1 is a zero divisor
in Zn .
Exercise 30 Prove that every non-zero element in Zn is either a zero divisor
or a unit. Show that this is not the case in Z.
C Exercises
Exercise 31 Write a program to find the multiplicative inverse of an element
a ∈ Zn , when Igcd(a, n) = 1, using the Euclidean algorithm.

4 Solving equations in modular arithmetic

At the heart of arithmetic are the techniques for solving equations. In this
section, we will learn how to solve linear equations in modular arithmetic. We
begin with a lemma which deals with the case most similar to the case over the
rational numbers.
Lemma 2 The equation ax ≡ b (mod n) has a unique solution in Zn , if gcd(a, n) =
1.

Proof: If gcd(a, n) = 1, by Theorem 6 the element a is a unit modulo n.

Therefore, there exists c with ac ≡ ca ≡ 1 (mod n). Then we have:
ax ≡ b (mod n)
cax ≡ cb (mod n)
x ≡ cb (mod n).

This gives that cb is the unique solution to the modular equation. 

Example 25 Consider the equation 3x ≡ 7 (mod 11). Here 3 and 11 are rela-
tively prime. The number 4 is the multiplicative inverse of 3, that is 3(4) ≡ 1
(mod 11). Then we have:
3x ≡ 7 (mod 11)
4(3)x ≡ 4(7) (mod 11)
x ≡ 6 (mod 11).

We can verify this by noting that 3(6) ≡ 7 (mod 11).

19
Example 26 Consider the equation 5x ≡ 2 (mod 16). Here 5 and 16 are rela-
tively prime. The number 13 is the multiplicative inverse of 5, that is 5(13) ≡ 1
(mod 16). Then we have:

5x ≡ 2 (mod 16)
13(3)x ≡ 13(2) (mod 16)
x ≡ 10 (mod 16).

We can verify this by noting that 5(10) ≡ 2 (mod 16).

Example 27 Consider the equation 11x ≡ 17 (mod 23). Here 11 and 23 are
relatively prime. The number 21 is the multiplicative inverse of 11, that is
21(11) ≡ 1 (mod 23). Then we have:

11x ≡ 17 (mod 23)

21(11)x ≡ 21(17) (mod 23)
x ≡ 12 (mod 23).

We can verify this by noting that 11(12) ≡ 17 (mod 23).

The next lemma will examine the case when no solution exists.

Lemma 3 The equation ax ≡ b (mod n) has no solution if gcd(a, n) = d and

d does not divide b.

Proof: Assume d = gcd(a, n). Let a = da0 , n = dn0 . If ax ≡ b (mod n)

then b − ax = kn for some k. This gives:

b = ax + kn
b = da0 x + dkn0
b = d(a0 x + kn0 ).

This implies that d must divide b if there is a solution. Therefore, if d does not
divide b then there is not solution. 

Example 28 Consider the equation 3x ≡ 5 (mod 9). Here, the greatest com-
mon divisor of 3 and 9 is 3, but 3 does not divide 5. This means that if
5 − 3x = 9k then 5 = 3(x + 3k). This is not possible since 3 does not di-
vide 3. To illustrate this point consider the possible elements modulo 9 and their
multiple by 3.

x (mod 9) 0 1 2 3 4 5 6 7 8
3x (mod 9) 0 3 6 0 3 6 0 3 6

The only results are 0, 3 and 6 which are the numbers in Z9 that are multiple of
3.

20
Lemma 4 The equation ax ≡ b (mod n) has d solutions if gcd(a, n) = d and
d does divide b.

Proof: Assume d = gcd(a, n). Let a = da0 , n = dn0 . Since d divides b we

0
have b = db . If ax ≡ b (mod n) then b − ax = kn for some k. This gives:

b = ax + kn
b = da0 x + dkn0
db0 = d(a0 x + kn0 )
0
b = (a0 x + kn0 )
b0 − a0 x = kn0 .

This gives that a0 x ≡ b0 (mod n0 ). We know from Lemma 2, that there is a

unique solution to this equation. Call it c. Then there are precisely d numbers
in Zn that are congruent to c (mod n0 ), that is

c, c + n0 , c + 2n0 , c + 3n0 , . . . , c + (d − 1)n0 .

All we have to do now is to show that these are all solutions to the original
equation. Recall that a0 c = b0 + hn0 for some h ∈ Z since c was a solution to
the earlier modular equation.

a(c + sn0 ) = ac + asn0

= da0 c + a0 sdn0
= d(b0 + hn0 ) + a0 sn
= db0 + hdn0 + a0 sn
= b + (h + a0 s)n
≡ b (mod n).

Therefore, they are all solutions to the original modular equation. 

Example 29 Consider the equation 6x ≡ 9 (mod 21). The greatest common

divisor of 6 and 21 is 3. We reduce the equation to 2x ≡ 3 (mod 7) by dividing
everything by 3. The multiplicative inverse of 2 modulo 7 is 4. Then 4(2x) ≡
4(3) (mod 7) which gives x ≡ 5 (mod 7). Then the solutions are 5, 5+7, 5+2(7)
which are 5, 12, and 19. We note that

6(5) = 30 ≡ 9 (mod 21)

6(12) = 72 ≡ 9 (mod 21)
6(19) = 114 ≡ 9 (mod 21).

Example 30 Consider the modular equation 15x − 3 ≡ 12 (mod 35). The first
thing we do is to add 3 to both sides to get 15x ≡ 15 (mod 35). Our first thought
when looking at this equation is to realize that x = 1 is a solution. We may be
tempted to stop there, but we would be wrong as there are other solutions to
this equation. We have that gcd(15, 35) = 5 and 5 divides 15 so we should have

21
5 solutions. We reduce this equation by dividing by 5 to get: 3x ≡ 3 (mod 7)
which has a unique solution of 1. Then the solutions are 1, 8, 15, 22 and 29. We
have

15(1) = 15 ≡ 15 (mod 35)

15(8) = 120 ≡ 15 (mod 35)
15(15) = 225 ≡ 15 (mod 35)
15(22) = 330 ≡ 15 (mod 35)
15(29) = 435 ≡ 15 (mod 35).

We summarize the previous results in the following theorem.

Theorem 10 Given the equation ax ≡ b (mod n), we have:

1. If gcd(a, n) = d and d divides b then there are exactly d solutions to the
modular equation.
2. If gcd(a, n) = d and d does not divide b then there are no solutions to the
modular equation.

Proof: Follows from Lemma 2, Lemma 3, and Lemma 4. 

We note that when d = 1 this theorem gives that there is a unique solution.

Example 31 Consider the modular equation 4x − 3 ≡ 7 (mod 14). The first

thing we do is to add 3 to both sides to get 4x ≡ 10 (mod 14). Then we have
gcd(4, 14) = 2 and 2 divides 10 so we should have 2 solutions. We reduce this
equation by dividing by 2 to get: 2x ≡ 5 (mod 7) which has a unique solution
of 6. Then the solutions are 6 and 13. We have

4(6) − 3 = 21 ≡ 7 (mod 14)

4(13) − 3 = 49 ≡ 7 (mod 14).

Definition 7 Let a, b, c 6= 0 be integers. The equation ax + by = c over the

integers is called a linear Diophantine equation in two variables.

If we take the equation modulo b on both sides of the equation, the Diophan-
tine equation above can be written as ax ≡ c (mod b). We know from previous
results that this equation has solutions if gcd(a, b) | c.

Theorem 11 Let gcd(a, b) = 1. If one of the solutions of the Diophantine equa-

tion ax + by = c is (x0 , y0 ), then the other solutions are in the form x = x0 + bk
and y = y0 − ak where k ∈ Z.

22
 Proof: If (x0 , y0 ) is a solution for the Diophantine equation ax + by = c,
then we can write ax0 + by0 = c. Subtracting both equations we get a(x − x0 ) +
b(y − y0 ) = 0. By taking modulo b, we get a(x − x0 ) ≡ 0 (mod b). This gives
that b | a(x − x0 ). As we are given that gcd(a, b) = 1, we have that b | x − x0 .
So x − x0 = bk, k ∈ Z, which means that x = x0 + bk.
On the other hand, a(x−x0 )+b(y−y0 ) = 0 means that ax−ax0 +by−by0 = 0.
In the last equation, writing x0 + bk instead of x, we get a(x0 + bk) − ax0 +
by − by0 = 0 which means that ax0 + abk − ax0 + by − by0 = 0. We have
abk + by − by0 = 0 and so by = by0 − abk. Dividing both sides by b 6= 0, we have
that y = y0 − ak. 

Example 32 Consider the equation 5x + 3y = 23. We see that gcd(5, 3) = 1

and 1 divides 23. Therefore, the equation does have a solution. We apply the
Euclidean Algorithm:
5 3 2 1 0
The computations are as follows:

5 = 3·1+2
3 = 2·1+1
2 = 1 · 2 + 0.

We have

1 = 3 + 2 · (−1)
= 3 + (5 + 3 · (−1)) · (−1)
= 5 · (−1) + 3 · 2.

Multiplying both sides of the last equation 5 · (−1) + 3 · 2 = 1 by 23, we get

5 · (−23) + 3 · 2 · 23 = 1 · 23

and then
5 · (−23) + 3 · 46 = 23.
Hence x0 = −23 and y0 = 46. We write all the solutions as x = x0 + bk =
−23 + 3k and y = y0 − ak = 46 − 5k, k ∈ Z.

We understand from the above example that the solution set is infinite. For
k = 0, we have x = −23 and y = 46 and so (x, y) = (−23, 46). For k = 1, we
have (x, y) = (−20, 41). For k = 2, we have (x, y) = (−17, 36) and so on. It
is obvious that if we apply one of the solutions, say (x, y) = (−23, 46), it will
satisfy the Diophantine equation as 5 · (−23) + 3 · 46 = 23.

Example 33 Consider the equation 21x + 12y = 66. We have gcd(21, 12) = 3
and 3 divides 66 so this equation does have a solution. We simply write the
equation as 7x + 4y = 22 by dividing both sides by 3. For the last equation,
gcd(7, 4) = 1 and 1 | 22. We apply the Euclidean Algorithm:

7 4 3 1 0

23
The computations are as follows:
7 = 4·1+3
4 = 3·1+1
3 = 1 · 3 + 0.
We have
1 = 4 + 3 · (−1)
= 4 + (7 + 4 · (−1)) · (−1)
= 7 · (−1) + 4 · 2.
Multiplying both sides of the last equation by 66, we get
1 · 66 = 7 · (−1) · (3 · (−22)) + 4 · 2 · 3 · 22
and then
66 = 21 · 22 + 12 · 44.
Hence, x0 = −22 and y0 = 44. We write all the solutions as x = x0 + bk =
−22 + 12k and y = y0 − ak = 44 − 21k, k ∈ Z.
Example 34 Consider the equation 119x + 95y = 143. We have gcd(119, 95) =
1 and 1 divides 143 so the equation does have a solution. We apply the Euclidean
Algorithm:
119 95 24 23 1 0
The computations are as follows:
119 = 95 · 1 + 24
95 = 24 · 3 + 23
24 = 23 · 1 + 1
23 = 1 · 23 + 0.
We have
1 = 24 + 23 · (−1)
= 24 + (95 + 24 · (−3)) · (−1)
= 24 · 4 + 95 · (−1)
= (119 + 95 · (−1)) · 4 + 95 · (−1)
= 119 · 4 + 95 · (−5).
Multiplying both sides of the last equation by 143, we get
119 · 4 · 143 + 95 · (−5) · 143 = 1 · 143
and then
119 · 572 + 95 · (−715) = 143.
Hence x0 = 572 and y0 = −715. We write all the solutions as x = x0 + bk =
572 + 95k and y = y0 − ak = −715 − 119k, k ∈ Z.
Example 35 Consider the equation 119x+133y = 143. We have gcd(119, 133) =
7 but 7 does not divide 143 as 143 = 11 · 13. So the equation does not have a
solution.

24
Exercises for Section 4

A Exercises

Exercise 32 Solve the following equations:

1. 3x ≡ 5 (mod 7).

2. 5x ≡ 9 (mod 11).
3. 4x ≡ 5 (mod 9).
4. 2x ≡ 5 (mod 13).
5. 7x ≡ 12 (mod 15).

6. 1600x ≡ 1 (mod 1601).

7. 11x ≡ 5 (mod 32).
8. 13x ≡ 3 (mod 16).

Exercise 33 Solve the following equations:

1. 4x ≡ 8 (mod 12).

2. 3x ≡ 6 (mod 9).
3. 2x ≡ 5 (mod 10).
4. 8x ≡ 12 (mod 20).
5. 9x ≡ 3 (mod 12).

6. 5x ≡ 9 (mod 15).
7. 6x ≡ 12 (mod 18).
8. 10x ≡ 5 (mod 15).

Exercise 34 Solve the following equations:

1. 5x + 3 ≡ 7 (mod 11).

2. 4x + 5 ≡ 11 (mod 13).
3. 9x − 4 ≡ 2 (mod 10).
4. 2x + 8 ≡ 10 (mod 17).
5. 11x − 4 ≡ 2 (mod 24).

6. 72x − 10 ≡ 64 (mod 73).

7. 13x + 3 ≡ 12 (mod 15).
8. 11x − 1 ≡ 13 (mod 14).

25
Exercise 35 Solve the following equations:
1. 2x + 5y = 83.
2. 17x + 83y = 135.
3. 20x + 38y = 56.
4. 35x + 20y − 84 = 0.
5. 20x − 33y = 9.
6. 105x + 5y − 10 = 0.
7. 41x − 12y + 7 = 0.
8. 405x + 804y = 3.
9. 286x + 230y − 6531 = 0.

B Exercises
Exercise 36 Prove that x2 ≡ a (mod p) has either no solutions or 2 solutions
when p is a prime and a is not 0.
Exercise 37 Find an n where x2 ≡ −1 (mod n) has a solution and an n where
x2 ≡ −1 (mod n) has no solution.

C Exercises
Exercise 38 Write a computer program to find all solutions to x2 ≡ 1 (mod n).
Run this for various n and determine some conjectures about the number of so-
lutions to this equation for various n.
Exercise 39 Develop a conjecture for when x2 ≡ −1 (mod n) has a solution
and prove it.

5 The Chinese remainder theorem

The Chinese remainder theorem (CRT, for short) is a fundamental tool in com-
puting with congruences. In particular, it will be an indispensable tool for
solving system of congruences.
The first known statement is from the third century and is by the Chinese
mathematician Sun-tzu in the Sun-tzu Suan-ching. The phrasing of the theorem
in ancient texts would be different than our present terminology. They would
have said something like: Find a number such that when you divide by 2 you get
a remainder of 1, when you divide by 3 you get a remainder of 2 and when you
divide by 5 you get a remainder of 3. We would write this problem as follows:
x ≡ 1 (mod 2)
x ≡ 2 (mod 3)
x ≡ 3 (mod 5).

26
They would have given an answer of 23 as the smallest such number. We would
specify all numbers satisfying the equations as x ≡ 23 (mod 30).
Example 36 We shall begin with an example. Assume we wanted to solve the
system of equations:
x ≡ 2 (mod 4)
x ≡ 3 (mod 7).
We can see that the number 6 satisfies the first equation but does not satisfy
the second, whereas the number 3 satisfies the second but not the first.
We shall show how to solve this system of equations. Any number satisfying
the first equation must be of the form 4k + 2 for some k ∈ Z. Then we put this
in the second equation to get 4k + 2 ≡ 3 (mod 7). Then we get 4k ≡ 1 (mod 7).
At this point we realize that gcd(4, 7) = 1 so we know that there is a unique
solution to this equation. We see that this solution is k ≡ 2 (mod 7). This
means that k is of the form k = 7g + 2. Then we apply this to the first equation
to get
x = 4k + 2 = 4(7g + 2) + 2 = 10 + 28g.
This means any number of this form will be a solution to both equations. The
solution can then be written as x ≡ 10 (mod 28). Consider the number 66 which
is 10 (mod 28). We have 66 (mod 4) = 2 and 66 (mod 7) = 3. The key to
solving this system was the fact that 4 and 7 were relatively prime. If they were
not there would not have been a unique solution to 4k ≡ 1 (mod 7).
We can now state the first theorem.
Theorem 12 If gcd(n, m) = 1, then there is a unique solution modulo nm to
the system:
x ≡ a (mod n)
x ≡ b (mod m).

Proof: For x to satisfy the first modular equation, we have that x must
be of the form x = kn + a for some k ∈ Z. Then we have:
kn + a ≡ b (mod m)
kn ≡ b−a (mod m).

Since gcd(n, m) = 1, there is a unique solution for k (mod m). Call this solution
α. That is αn ≡ b − a (mod m). This means that k is of the form α + gm for
some g ∈ Z. Then we have
x = kn + a
x = (α + gm)n + a
x = αn + gma + gmn
x ≡ αn + gma (mod mn).

Therefore, there is a unique solution modulo mn. 

27
Example 37 We shall solve the following system:

x ≡ 5 (mod 7)
x ≡ 4 (mod 8).

Let x = 7k + 5. Then 7k + 5 ≡ 4 (mod 8) gives 7k ≡ 7 (mod 8). Then we have

k ≡ 1 (mod 8) and k = 8g + 1. Finally,

x = 7k + 5 = 7(8g + 1) + 5 = 56g + 7 + 5 = 56g + 12 ≡ 12 (mod 56).

Example 38 We shall solve the following system:

x ≡ 3 (mod 11)
x ≡ 7 (mod 19).

Let x = 11k +3. Then 11k +3 ≡ 7 (mod 19) gives 11k ≡ 4 (mod 19). Since this
equation is not obvious by inspection we shall describe the solution completely.
Apply the Euclidean algorithm to 19 and 11 and get

19 11 8 3 2 1 0

Then we have

3−2 = 1
3 − (8 − (2)3) = 1
3(3) − 8 = 1
3(11 − 8) − 8 = 1
3(11) − 4(8) = 1
3(11) − 4(19 − 11) = 1
7(11) − 4(19) = 1.

This gives 7(11) ≡ 1 (mod 19). Then we have k ≡ 7(4) ≡ 9 (mod 19) and
k = 19g + 9. Finally,

x = 11k + 3 = 11(19g + 9) + 3 = 209g + 99 + 3 = 209g + 102 ≡ 102 (mod 209).

Example 39 We shall solve the following system with some thought rather than
blindly applying the algorithm. Examine the following system:

x ≡ 25 (mod 27)
x ≡ 1599 (mod 1601).

At first glance, it seems like there will be a lot of computation to solve this
system. But a little bit of thinking makes us realize that we can rewrite the
system as follows:

x ≡ −2 (mod 27)
x ≡ −2 (mod 1601).

The solution then is obvious, namely, x ≡ −2 (mod 27(1601)). Namely, x ≡

43225 (mod 43227).

28
 We can easily generalize this theorem to the main Chinese Remainder The-
orem which handles an arbitrary number of modular congruences.
Theorem 13 (Chinese Remainder Theorem) Let n1 , n2 , . . . , ns be natural
numbers with gcd(ni , nj ) = 1, if i 6= j. Then there is a unique solution modulo
n1 n2 n3 · · · ns to the system:
x ≡ a1 (mod n1 )
x ≡ a2 (mod n2 )
x ≡ a3 (mod n3 )
..
.
x ≡ as (mod ns ).

Proof: First applying Theorem 12 to

x ≡ a1 (mod n1 )
x ≡ a2 (mod n2 )

gives a unique solution modulo n1 n2 , say x ≡ b1 (mod n1 n2 ). Then we have

the system:
x ≡ b1 (mod n1 n2 )
x ≡ a3 (mod n3 )
..
.
x ≡ as (mod ns ).

This system has one fewer modular equation than the previous. We apply this
inductively until we have one remaining modular equation modulo n1 n2 n3 · · · ns .


Example 40 We shall solve the system:

x ≡ 1 (mod 3)
x ≡ 4 (mod 5)
x ≡ 5 (mod 7).

Solving the first two modular equations we get x ≡ 4 (mod 15). Then we solve
the following system:
x ≡ 4 (mod 15)
x ≡ 5 (mod 7).

This gives x ≡ 19 (mod 105).

29
Example 41 Consider the following system:

x ≡ 9 (mod 10)
x ≡ 12 (mod 13)
x ≡ 16 (mod 17).

At first glance it may seem like it will require a great amount of computations
to solve. However, closer inspection allows us to see that we can write the three
equations as follows:

x ≡ −1 (mod 10)
x ≡ −1 (mod 13)
x ≡ −1 (mod 17).

This then has the obvious solution of x ≡ −1 ≡ 2209 (mod 2210).

We shall now take a look at a system where we cannot apply the Chinese
Remainder Theorem. Consider the following system of modular equations:

x ≡ 2 (mod 4)
x ≡ 4 (mod 6).

We note that 4 and 6 are not relatively prime. Here, both 10 and 22 are solutions
modulo 24 to the system.
Next consider the following system of modular equations:

x ≡ 3 (mod 4)
x ≡ 4 (mod 6).

The numbers that are 3 (mod 4) and less than 24 are 3, 7, 11, 15, 19, 23. None of
these numbers are 4 (mod 6). Therefore, in this situation there is no solution.
For both of these cases, the problem lies in the fact that gcd(4, 6) = 2 6= 1.
Consider also the following system:

x ≡ 0 (mod 2)
x ≡ 1 (mod 4).

All numbers satisfying the first modular equation must be even. However, all
numbers satisfying the second modular equation must be odd. Therefore, of
course, there are no solutions to this system of modular equations. It should be
clear now that it is absolutely necessary for the moduli to be relatively prime
to apply the Chinese Remainder Theorem.
We shall now take another look at the Chinese Remainder Theorem and
present a technique for solving systems of modular equations.

30
 Let us present the system we want to solve. Given s ∈ N, n1 , . . . , ns ∈ N,
a1 , . . . , as ∈ Z and assuming that for 1 ≤ i 6= j ≤ s, ni is relatively prime with
nj . We want to solve the system

x ≡ ai (mod ni ).

That is we want to find all the integers x satisfying all of these equations.
To avoid confusion created by indexes, we will just treat the case of a system
with three equations.

x ≡ a1 (mod n1 )
x ≡ a2 (mod n2 )
x ≡ a3 (mod n3 )

where {x, a1 , a2 , a3 , n1 , n2 , n3 } ⊂ Z. We also suppose that the integers n1 , n2 , n3

are relatively prime in pairs. In other words, for every i 6= j the integers i
and j have gcd(ni , nj ) = 1. This technique will be easily generalized to more
equations. We first solve easier systems where Bézout’s theorem can be used.

First step. We look for x1 , x2 , x3 in Z such that

x1 ≡ 1 (mod n1 ) x2 ≡ 0 (mod n1 ) x3 ≡ 0 (mod n1 )
x1 ≡ 0 (mod n2 ) x2 ≡ 1 (mod n2 ) x3 ≡ 0 (mod n2 )
x1 ≡ 0 (mod n3 ) x2 ≡ 0 (mod n3 ) x3 ≡ 1 (mod n3 ).

To find x1 , we compute a solution (u1 , v1 ) ∈ Z2 of the Bézout equation:

n2 n3 u1 + n1 v1 = 1.

Since gcd(n2 n3 , n1 ) = 1 this equation can be solved and a solution is x1 =

n2 n3 u1 . Similarly to find x2 and x3 , we search for solutions of

n 1 n 3 u 2 + n 2 v2 = 1
n 1 n 2 u 3 + n 3 v3 = 1.

Then x2 = n1 n3 u2 and x3 = n1 n2 u3 .

Second step. We now get the general solution of the system

x ≡ a1 x1 + a2 x2 + a3 x3 (n1 n2 n3 ) ,

This can also be written

x≡r (mod n1 n2 n3 )

where r is the remainder of the euclidean division of a1 x1 + a2 x2 + a3 x3 by

n1 n2 n3 .

Example 42 Let us solve the system

x ≡ 1 (mod 7)
x ≡ 4 (mod 9)
x ≡ 3 (mod 5).

31
First step. The particular equations and their solutions are as follows. Note
that we are solving these using the Euclidean algorithm as we have done so many
times before.
45 u1 + 7 v1 = 1; sol. 45 · (−2) + 7 · 13 = 1. Hence x1 = −90.
35 u2 + 9 v2 = 1; sol. 35 · (−1) + 9 · 4 = 1. Hence x2 = −35.
63 u3 + 5 v3 = 1; sol. 63 · 2 − 5 · 25 = 1 Hence x3 = 126.

Second step. We have

a1 x1 + a2 x2 + a3 x3 = 1(−90) + 4(−35) + 3(126) = 148.

So that the general solution is

x ≡ 148 (mod 315).

We note that once we have solved the first step, we have easy solutions for
any ai that we choose.
We shall now show another application of the Chinese Remainder Theorem
using square roots. We begin with an example. The number 4 is a square in
Z5 , specifically, 22 ≡ 32 ≡ 4 (mod 5). It is also a square in Z7 , 22 ≡ 52 ≡ 4
(mod 7). In Z5 , we can say that the square roots of 4 are 2 and 3 and in Z7 , we
can say that the square roots of 4 are 2 and 5.
Apply the Chinese Remainder Theorem to the following 4 systems of mod-
ular equations:

x ≡ 2 (mod 5) x ≡ 2 (mod 5)
x ≡ 2 (mod 7) x ≡ 5 (mod 7)

x ≡ 3 (mod 5) x ≡ 3 (mod 5)
x ≡ 2 (mod 7) x ≡ 5 (mod 7)

The solution to the first system is 2 (mod 35). The solution to the second system
is 12 (mod 35). The solution to the third system is 23 (mod 35). The solution
to the fourth system is 33 (mod 35).
Now we have:

• We have 22 = 4 ≡ 4 (mod 35).

• We have 122 = 144 ≡ 4 (mod 35).
• We have 232 = 529 ≡ 4 (mod 35).

• We have 332 = 1089 ≡ 4 (mod 35).

Therefore, we have used the Chinese Remainder Theorem to find 4 square roots
of 4 in Z35 .

32
Exercises for Section 5
A Exercises
Exercise 40 Solve the following systems of two modular equations with the
Chinese Remainder Theorem.
1.
x ≡ 2 (mod 11)
x ≡ 7 (mod 9).

2.
x ≡ 4 (mod 5)
x ≡ 1 (mod 7).

3.
x ≡ 3 (mod 17)
x ≡ 12 (mod 13).

4.
x ≡ 5 (mod 9)
x ≡ 7 (mod 10).

5.
x ≡ 6 (mod 8)
x ≡ 11 (mod 15).

6.
x ≡ 13 (mod 14)
x ≡ 11 (mod 19).

Exercise 41 Solve the following systems of three modular equations with the
Chinese Remainder Theorem.
1.
x ≡ 2 (mod 3)
x ≡ 1 (mod 5)
x ≡ 6 (mod 8).

33
 2.
x ≡ 3 (mod 5)
x ≡ 4 (mod 6)
x ≡ 2 (mod 11).

3.
x ≡ 1 (mod 3)
x ≡ 2 (mod 7)
x ≡ 11 (mod 13).

4.
x ≡ 5 (mod 6)
x ≡ 1 (mod 7)
x ≡ 6 (mod 11).

5.
x ≡ 12 (mod 13)
x ≡ 14 (mod 15)
x ≡ 16 (mod 17).

6.
x ≡ 4 (mod 7)
x ≡ 5 (mod 9)
x ≡ 2 (mod 10).

B Exercises
Exercise 42 Determine when a system of two modular congruences has more
than one solution.
Exercise 43 Determine when a system of two modular congruences has no
solutions.
Exercise 44 Find 4 square roots of 9 in Z143 .
Exercise 45 Find 4 square roots of 1 in Z299 .
C Exercises
Exercise 46 Write a program to implement the algorithm for solving the Chi-
nese Remainder Theorem.

34
6 Divisibility tests

We can return to the divisibility tests that we found in Chapter ??. Modular
arithmetic makes them all much easier. We begin with an easy lemma.

Lemma 5 A number n is divisible by k if and only if n ≡ 0 (mod k).

Proof: If n = gk then n (mod k) = 0. If n (mod k) = 0 then n = gk +0 =

gk for some g ∈ Z. This gives the result. 

Theorem 14 Let n ∈ N be a natural number. Write n as n = al 10l +

al−1 10l−1 + · · · + a1 10 + a0 .
1. An integer n is divisible by 2 if and only if a0 = 0, 2, 4, 6, 8.
2. An integer n is divisible by 3 if and only if the sum of its digits is divisible
by 3.
3. An integer n is divisible by 4 if and only if a1 10 + a0 is divisible by 4.
4. An integer n is divisible by 5 if and only if a0 = 0, 5.
5. An integer n is divisible by 6 if and only if the sum of its digits is divisible
by 3 and a0 = 0, 2, 4, 6, 8.
6. An integer n = 10a + b is divisible by 7 if and only if a − 2b is divisible by
7.
7. An integer n is divisible by 8 if and only if a2 100 + a1 10 + a0 is divisible
by 8.
8. An integer n is divisible by 9 if and only if the sum of its digits is divisible
by 9.
9. An integer n is divisible by 10 if and only if a0 = 0.
10. An integer n is divisible by 11 if and only if a0 −a1 +a2 −a3 +· · ·+(−1)l al
is divisible by 11.

Proof: Most of the proofs are shown by showing that the two expressions
are congruent modulo the number we are testing for divisibility.
1. We have n = al 10l + al−1 10l−1 + · · · + a1 10 + a0 (mod 2) = a0 since 10 ≡ 0
(mod 2).
2. We have n = al 10l + al−1 10l−1 + · · · + a1 10 + a0 (mod 3) = al + al−1 +
· · · + a1 + a0 since 10 ≡ 1 (mod 3).
3. We have n = al 10l + al−1 10l−1 + · · · + a1 10 + a0 (mod 4) = 10a1 + a0 since
100 ≡ 0 (mod 4).
4. We have n = al 10l + al−1 10l−1 + · · · + a1 10 + a0 (mod 5) = a0 since 10 ≡ 0
(mod 5).

35
 5. For divisibility by 6 we simply apply the rules for divisibility by 2 and 3.
6. For divisibility by 7 a slightly different approach is used. If

10a + b ≡ 0 (mod 7)
3a + b ≡ 0 (mod 7)
b ≡ 4a (mod 7).

Then a − 2b ≡ a − 2(4a) ≡ −7a ≡ 0 (mod 7).

If a − 2b ≡ 0 (mod 7) then a ≡ 2b (mod 7). Then 10a + b ≡ 10(2b) + b ≡
21b ≡ 0 (mod 7).

7. We have n = al 10l +al−1 10l−1 +· · ·+a1 10+a0 (mod 8) = a2 100+a1 10+a0

since 1000 ≡ 0 (mod 8).
8. We have n = al 10l + al−1 10l−1 + · · · + a1 10 + a0 (mod 9) = al + al−1 +
· · · + a1 + a0 since 10 ≡ 1 (mod 9).
9. We have n = al 10l + al−1 10l−1 + · · · + a1 10 + a0 (mod 10) = a0 since
10 ≡ 0 (mod 10).
10. We have n = al 10l + al−1 10l−1 + · · · + a1 10 + a0 (mod 10) = a0 − a1 +
a2 − a3 + · · · + (−1)l al since 10 ≡ −1 (mod 11).


Example 43 We shall show how this theorem can be used to determine if a

number is divisible by 7. Consider the number 1701. This number is 170 · 10 + 1.
Then applying the rule, we get 170 − 2(1) = 168. Then we see 168 as 16 · 10 + 8,
so we take 16 − 2(8) = 0 which is 0 (mod 7). Therefore, 7 divides 1701. In fact,
1701 = 7(243).

The rule for divisibility by 7 is quite different from the other rules as we
exhibit in the following example.

Example 44 Consider the number 111. We have 111 (mod 7) = 6. However,

11−2(1) ≡ 2 (mod 7). We note that 10a+b and a−2b are not congruent modulo
7. It is only true that if one is 0 (mod 7), the other is 0 (mod 7). The other
rules essentially equate modulo n two different numbers to determine divisibility.

Example 45 Consider the number 1452342452. If we want to see if this number

is divisible by 11 we take 2 − 5 + 4 − 2 + 4 − 3 + 2 − 5 + 4 − 1 = 0 ≡ 0 (mod 11).
Therefore, this number is divisible by 11. In fact, 1452342452 = 132031132(11).

We can get many more tests by writing the number n in different bases.

Theorem 15 Let n be a number written in base b, that is n = al bl + al−1 bl−1 +

· · · + a1 b + a0 .
1. An integer n is divisible by b if and only if a0 = 0.

36
 2. An integer n is divisible by b − 1 if and only if a0 + a1 + · · · + al is divisible
by b − 1.

Proof:
1. The first result comes from the fact that
n = al bl + al−1 bl−1 + · · · + a1 b + a0 (mod b) = a0 .

2. For the second result, note that b ≡ 1 (mod b − 1), which gives
n = al bl + al−1 bl−1 + · · · + a1 b + a0 (mod b − 1) = a0 + a1 + a2 + · · · + al .

We shall exhibit some of the power of the modular arithmetic in the following
theorems.
It is well known that there are infinitely many primes, see [?]. It is not
known if there are infinitely many twin primes, meaning primes of the form p,
p + 2 where both are prime. An example, would be 5 and 7. Another would be
41 and 43. We shall show that there is only one triple primes, namely primes
of the form p, p + 2, p + 4, where they are all primes.
Theorem 16 The only set of triple primes are 3, 5, and 7.

Proof: Let p > 3 be a prime. We know p 6≡ 0 (mod 3) since that would

mean that p is divisible by 3 and hence not a prime. If p ≡ 1 (mod 3) then
p + 2 ≡ 0 (mod 3) and hence not a prime. If p ≡ 2 (mod 3) then p + 4 ≡ 0
(mod 3) and hence not a prime. Therefore, the only triple prime is 3, 5 and 7.


Here is another theorem using modular arithmetic to show divisibility.

Theorem 17 Any set of t consecutive integers contains an element divisible by
t.

Proof: If a, a + 1, a + 2, . . . , a + t − 1 are a set of t consecutive integers,

then they are all distinct in Zt . Therefore, one of them must be 0 in Zt and
hence divisible by t. 

Example 46 Consider the 5 following sequences of 5 consecutive integers, each

beginning with a different value modulo 5:
5, 6, 7, 8, 9
11, 12, 13, 14, 15
22, 23, 24, 25, 26
38, 39, 40, 41, 42
54, 55, 56, 57, 58

Notice that each of these contains an element divisible by 5.

37
Theorem 18 There are arbitrarily long sequences of composite integers.

Proof: Let n be a natural number. If 1 < k ≤ n, then n! + k ≡ 0 (mod k)

since k divides n!. Therefore, n! + 2, n! + 3, n! + 4, . . . , n! + n is a sequence of
n − 1 consecutive composite numbers. 

Example 47 Let n = 10. Then n! = 3628800. Then the sequence

3628802, 3628803, 3628804, 3628805, 3628806, 3628807, 3628808, 3628809, 3628810

is a sequence of 9 consecutive composite numbers.

Exercises for Section 6

A Exercises

Exercise 47 Determine which of the integers between 1 and 11 the following

numbers are divisible by:
1. 432.
2. 6532.
3. 3453.
4. 4466.
5. 2222.
6. 9864.
7. 1601.
8. 875.
9. 500.
10. 39916800.

B Exercises

Exercise 48 Determine a rule for divisibility by 12.

Exercise 49 Determine a rule for divisibility by 15.

Exercise 50 Determine a rule for divisibility by 16.

Exercise 51 Determine a rule for divisibility by 20.

C Exercises

Exercise 52 Determine and prove a rule for divisibility by 2k , where k ∈ N+ .

Exercise 53 Write a program to determine if a number is divisible by an integer

under 11. Use this to find all primes less than 120.

38
7 Train ride problem
Two friends, Leonhard and Emmy were traveling on a train. Since the trip was
quite long, Leonhard decided to ask Emmy a series of questions on modular
arithmetic where each answer depends on the previous answer that was given.
Therefore, each question must be answered correctly or the next answer will be
incorrect as well. See if you can determine the correct answer that Emmy gives
her friend at the end.

1. Let a be the multiplicative inverse of 5 in Z11 .

2. Let b be the multiplicative inverse of 4 in Za .
3. Let c be the unique solution in Zab to the system:

X ≡ 2 (mod a)
X ≡ 6 (mod b)

4. Let d be the solution to 7X ≡ 5 (mod c).

5. Let e = d2 (mod 23).
6. Let f be the number of units in Ze .

7. Let g = f 3 (mod 11).

8. Let h be the solution to gX ≡ 5 (mod 20).
9. Let i = a + b + c + d + e + f + g + h (mod 28).

10. Let j be the solution to 2X ≡ 5 (mod i).

11. Let k = j 2 (mod 15).
12. Let ` be the unique solution in Z110 to the following:

X ≡ k (mod 10)
X ≡ k+1 (mod 11)

13. Let m = `2 (mod 111).

14. Let n be the number of non-zero zero divisors in Zm .
15. Let o = 3n2 + 1 (mod 13).

16. Let p = 315 (mod o).

17. Let q = p2 + p + 1 (mod 30).
18. Let r be the number of units in Zq .
19. Let s be the solution to 5X ≡ 3 (mod r).

39
 20. Let t be the number of non-zero zero divisors in Zs .
21. Let u = t3 + 1 (mod 11).
22. Let v = (u + 5)4 (mod 11).
23. Let w be the number of units in Zv .
24. Let x be the unique solution in Z30 to the following system:

X ≡ w (mod 2)
X ≡ w+1 (mod 3)
X ≡ w+2 (mod 5)

25. Let y = x2 − 25 (mod 13).

26. Let z be the solution to 1601X ≡ y (mod 1602)

Solutions to Exercises for Section 2

Solution to Exercise 1
1. 5
2. 6
3. 7
4. 0
5. 1
6. 2
7. 10
8. 3
9. 1
10. 0

Solution to Exercise 2
1. 8
2. 1
3. 5
4. 1
5. 3

40
 6. 2
7. 6
8. 1
9. 1
10. 0

Solution to Exercise 3
1.
31 ≡ 3 (mod 10)
2
3 ≡ 9 (mod 10)
3
3 ≡ 7 (mod 10)
34 ≡ 1 (mod 10)
Hence 322 = (34 )5 32 ≡ 1 · 32 = 9 (mod 10).
2.
41 ≡ 4 (mod 10)
2
4 ≡ 6 (mod 10)
43 ≡ 4 (mod 10)
4
4 ≡ 6 (mod 10)
.. .. ..
. . .
which will continue in the same manner. So we have that odd power give
4 and even powers give 6 modulo 10. Hence 4162 ≡ 6 (mod 10).
3.
51 ≡ 5 (mod 10)
2
5 ≡ 5 (mod 10)
53 ≡ 5 (mod 10)
.. .. ..
. . .
which will continue in the same manner. So we have that all the powers
of 5 give 5 modulo 10. Hence 510598 ≡ 5 (mod 10).
4.
61 ≡ 6 (mod 10)
2
6 ≡ 6 (mod 10)
3
6 ≡ 6 (mod 10)
.. .. ..
. . .
which will continue in the same manner. So we have that all the powers
of 6 give 6 modulo 10. Hence 65679 ≡ 6 (mod 10).

41
 5. We have that 11 ≡ 1 (mod 10) which gives 11k ≡ 1 (mod 10) for any k.
6.

71 ≡ 7 (mod 10)
2
7 ≡ 9 (mod 10)
73 ≡ 3 (mod 10)
4
7 ≡ 1 (mod 10)

Hence 7351 = (74 )87 73 ≡ 1 · 73 = 3 (mod 10).

25! = 1 · 2 · 3 · 4 · 5 · · · ≡ 0 (mod 10) since it has 2 and 5 as factors.
We finally have that 25! + 7351 = · · · 0 + 3 = 3 (mod 10).
7. The number 402! ≡ 0 (mod 10) as we did for the preceding item of the ex-
ercise (note that we are treating 402!) as an integer rather than considering
(402 (mod 10))!. On the other hand

81 ≡ 8 (mod 10)
2
8 ≡ 4 (mod 10)
83 ≡ 2 (mod 10)
4
8 ≡ 6 (mod 10)
5
8 ≡ 8 (mod 10)
6
8 ≡ 4 (mod 10)
.. .. ..
. . .

This means that if the power of 8 is divisible by 4 then the result is 6.

We have 835 = (84 )8 83 ≡ 6 · 83 ≡ 6 · 2 ≡ 2 (mod 10). We finally have
402! + 835 ≡ 2 (mod 10).

Solution to Exercise 4
We have 53 ≡ 25 (mod 93). Hence we have that 53n ≡ 25n (mod 93) for n ∈
N. Multiplying the both sides of the last equation by 24 we have 53n · 24 ≡ 25n+4
(mod 93). Now multiplying both sides of the last equation by 4 we get

53n · 24 · 4 ≡ 25n+4 · 22 (mod 93)

3n
5 · (−29) ≡ 25n+6 (mod 93)

which means that 93 | (25n+6 + 53n · 29).

Solution to Exercise 5

x 0 1 2 3 4 5 6 7 8 9 10 11 12
x2 (mod 13) 0 1 4 9 3 12 10 10 12 3 9 4 1

Solution to Exercise 6

42
 x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
x2 (mod 16) 0 1 4 9 0 9 4 1 0 1 4 9 0 9 4 1

Solution to Exercise 7

x 0 1 2 3 4 5 6 7 8
x3 (mod 9) 0 1 8 0 1 8 0 1 8

Solution to Exercise 8

x 0 1 2 3 4 5 6 7 8 9
x4 (mod 10) 0 1 6 1 6 5 6 1 6 1
Solution to Exercise 9

0, 1, 7, 9, 15

Solution to Exercise 10
0, 5, 8.

Solution to Exercise 11
We have k(k) = n ≡ 0 (mod n).

Solution to Exercise 12

+ 0 1 2 3 4 · 0 1 2 3 4
0 0 1 2 3 4 0 0 0 0 0 0
1 1 2 3 4 0 1 0 1 2 3 4
2 2 3 4 0 1 2 0 2 4 1 3
3 3 4 0 1 2 3 0 3 1 4 2
3 4 0 1 2 3 4 0 4 3 2 1

Solution to Exercise 13
48

Solution to Exercise 14
2p − 1

Solution to Exercise 15
4

Solution to Exercise 16
p−1

Solution to Exercise 17
6, p − 1

Solution to Exercise 18

43
 We have ac ≡ bc (mod n) implies n | (bc − ac) which means that n | (b − a)c.
Therefore, n | (b − a) since gcd(c, n) = 1. Hence b − a ≡ 0 (mod n) which means
that a ≡ b (mod n).

Solution to Exercise 19
Multiply each side of the equivalence b ≡ d (mod n) by c then we have
bc ≡ dc (mod n). We are also given ab ≡ cd (mod n). So we have that ab ≡ bc
(mod n) which implies that n | bc − ab which implies that n | b(c − a). So we
have that n | (c − a) since gcd(b, n) = 1. Hence c − a ≡ 0 (mod n) which means
that a ≡ c (mod n).

Solutions to Exercises for Section 3

Solution to Exercise 22

1. 1, 5, 7, 11

2. 1, 5, 7, 11, 13, 17
3. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
4. 1, 3, 5, 7

5. 1, 3, 5, 7, 9, 11, 13, 15

Solution to Exercise 23
1. 2, 3, 4, 6, 8, 9, 10
2. 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16
3. None.

4. 2, 4, 6
5. 2, 4, 6, 8, 10, 12, 14

Solution to Exercise 24

1. 5−1 ≡ 9 (mod 11)

2. 7−1 ≡ 2 (mod 13)
3. 9−1 ≡ 5 (mod 22)

4. 2−1 ≡ 8 (mod 15)

5. 3−1 ≡ 534 (mod 1601)
6. 11−1 ≡ 11 (mod 15)
7. 32−1 ≡ 65 (mod 77)

44
 8. 15−1 ≡ 47 (mod 64)
9. 51−1 ≡ 39 (mod 71)

10. 101−1 ≡ 365 (mod 1024)

Solution to Exercise 25
1. 16

2. 26
3. 10
4. 3

5. 13
6. 7
7. 3
8. 211

9. 259
10. 25

Solution to Exercise 26
Z8
Nilpotent: 0, 2, 4, 6
Idempotent: 0, 1
Z10
Nilpotent: 0
Idempotent: 0, 1, 5, 6
Z16
Nilpotent: 0, 2, 4, 6, 8, 10, 12, 14
Idempotent: 0, 1

Solution to Exercise 27
If a = 2g then a2k−1 = 2k g ≡ 0 (mod 2k ). Therefore, if a is even, then a is
a zero-divisor and hence not a unit.
If a is odd, then gcd(a, 2k ) = 1 and so a is a unit.

Solution to Exercise 28
If a is not relatively prime to n then it is a zero divisor. Hence, if it is not a
zero divisor then it is relatively prime to n and therefore a unit.

Solution to Exercise 29
If a2 ≡ 1 (mod n), then a2 − 1 ≡ 0 (mod n). Then (a − 1)(a + 1) ≡ 0
(mod n). If a 6≡ ±1 then a − 1 and a + 1 are non-zero numbers whose product
is 0. Therefore, they are zero-divisors.

45
Solution to Exercise 30
Let a ∈ Zn . If gcd(a, n) = 1 then a is a unit. If gcd(a, n) 6= 1 then a is a
zero divisor.
In the integers, the number 2 is neither a unit nor a zero divisor. In fcat,
the only units are 1 and −1 and there are no zero divisors.

Solutions to Exercises for Section 4

Solution to Exercise 32

1. x ≡ 4 (mod 7)
2. x ≡ 4 (mod 11)
3. x ≡ 8 (mod 9)
4. x ≡ 9 (mod 13)
5. x ≡ 6 (mod 15)
6. x ≡ 1600 (mod 1601)
7. x ≡ 15 (mod 32)
8. x ≡ 15 (mod 16)

Solution to Exercise 33

1. 2, 5, 8, 11 (mod 12)
2. 2, 5, 8 (mod 9)
3. No solution.
4. 4, 9, 14, 19 (mod 20)
5. 3, 7, 11 (mod 12)
6. No solution.
7. 2, 5, 8, 11, 14, 17 (mod 18)
8. 2, 5, 8, 11, 14 (mod 15)

Solution to Exercise 34

1. 3 (mod 11)
2. 8 (mod 13)
3. 4 (mod 10)
4. 1 (mod 17)

46
 5. 18 (mod 24)
6. 72 (mod 73)
7. 3 (mod 15)
8. 0 (mod 14)

Solution to Exercise 35
1. Since gcd(2, 5) = 1 and 1 | 83, the equation does have a solution. We
apply the Euclidean Algorithm.
5 2 1 0
The computations are as follows.
5 = 2·2+1
2 = 1·2+0

We have
1 = 5 + 2 · (−2)
We multiply both sides of the equation by 83 and we get
1 · 83 = 5 · 83 + 2 · (−2) · 83
which means

83 = 2 · (−166) + 5 · 83
From the last equation we have that x0 = −166 and y0 = 83 and so that
x = −166 + 5k, y = 83 − 2k, k ∈ Z.
2. Since gcd(17, 83) = 1 and 1 | 135, the equation does have a solution. We
apply the Euclidean Algorithm.
83 17 15 2 1 0
The computations are as follows.
83 = 17 · 4 + 15
17 = 15 · 1 + 2
15 = 2·7+1
2 = 1·2+0

We have
1 = 15 + 2 · (−7)
= 15 + (17 + 15 · (−1)) · (−7)
= 15 · 8 + 17 · (−7)
= (83 + 17 · (−4)) · 8 + 17 · (−7)
= 17 · (−39) + 83 · 8.

47
 We multiply both sides of the equation by 135 :

17 · (−5265) + 83 · 1080 = 135

from which we get x0 = −5265, y0 = 1080 and x = −5265 + 83k, y =

1080 − 17k, k ∈ Z.
3. Since gcd(20, 38) = 2 and 2 | 56, the equation does have a solution. We
apply the Euclidean Algorithm.

38 20 18 2 0

The computations are as follows.

38 = 20 · 1 + 18
20 = 18 · 1 + 2
18 = 2·9+0

We have

2 = 20 + 18 · (−1)
= 20 + (38 + 20 · (−1)) · (−1)
= 20 · 2 + 38 · (−1)

We multiply both sides of the equation by 28 :

20 · 56 + 38 · (−28) = 56

from which we get x0 = 56, y0 = −28 and x = 56 + 38k, y = −28 − 20k,

k ∈ Z.
4. We have the following Diophantine equation 35x+20y = 84. We have that
gcd(35, 20) = 5 but 5 - 84, so the equation does not have a solution.

5. We have the following Diophantine equation 20x + (−33)y = 9. Since

gcd(20, −33) = gcd(20, 33) = 1 and 1 | 9, the equation does have a solu-
tion. We apply the Euclidean Algorithm.

33 20 13 7 6 1 0

The computations are as follows.

33 = 20 · 1 + 13
20 = 13 · 1 + 7
13 = 7·1+6
7 = 6·1+1
6 = 1·6+0

48
 We have

1 = 7 + 6 · (−1)
= 7 + (13 + 7(−1)) · (−1)
= 7 · 2 + 13 · (−1)
= (20 + 13 · (−1)) · 2 + 13 · (−1)
= 20 · 2 + 13 · (−3)
= 20 · 2 + (33 − 20) · −3
= 20(5) − 3(33).

We multiply both sides of the equation by 9 :

20 · 18 + (−13) · 27 = 9

from which we get x0 = 45, y0 = 27 and x = 45 − 33k, y = 27 − 20k,

k ∈ Z.
6. We have the following Diophantine equation 105x + 5y = 10 which is
equivalent to the following equation 21x + y = 2 by dividing both of the
equation by 5. Since gcd(21, 1) = 1 and 1 | 2, the equation does have a
solution. We can simply see that a solution is (x0 , y0 ) = (1, −19). Hence,
all the solutions follows: x = 1 + 5k and y = −19 − 105k, k ∈ Z.
7. We have the following Diophantine equation 41x − 12y = −7. Since
gcd(41, 12) = 1 and 1 | −7, the equation does have a solution. We apply
the Euclidean Algorithm.

41 12 5 2 1 0

The computations are as follows.

41 = 12 · 3 + 5
12 = 5·2+2
5 = 2·2+1
2 = 1·2+0

We have

1 = 5 + 2 · (−2)
= 5 + (12 + 5(−2)) · (−2)
= 5 · 5 + 12 · (−2)
= (41 + 12 · (−3)) · 5 + 12 · (−2)
= 41 · 5 + 12 · (−17)

By multiplying both sides of the equation by −7 :

41 · (−35) + 12 · 119 = −7

from which we get x0 = −35, y0 = −119 and x = −35 − 12k, y =

−119 − 41k, k ∈ Z.

49
 8. Since gcd(405, 804) = 3 and 3 | 3, the equation does have a solution. We
apply the Euclidean Algorithm.

804 405 399 6 3 0

The computations are as follows.

804 = 405 · 1 + 399

405 = 399 · 1 + 6
399 = 6 · 66 + 3
6 = 3·2+0

We have

3 = 399 + 6 · (−66)
= 399 + (405 + 399(−1)) · (−66)
= 399 · 67 + 405 · (−66)
= (804 + 405 · (−1)) · 67 + 405 · (−66)
= 405 · (−133) + 804 · 67

Hence we have
405 · (−133) + 804 · 67 = 3.
So x0 = −133, y0 = 67 and x = −133 + 804k, y = 67 − 405k, k ∈ Z.
9. We have the following Diophantine equation 286x + 230y = 6531. We have
that gcd(286, 230) = 2 but 2 - 6531, the equation does not have a solution.

Solution to Exercise 36
If a is a square, that is a = b2 (mod p), and x2 ≡ b2 (mod p). Then (x −
b)(x+b) ≡ 0 (mod p). There are no zero divisors in Zp , p a prime, so no element
other that b or −b can make this product 0. Therefore, there are at most two
solutions.

Solution to Exercise 37
The equation x2 ≡ −1 (mod 5) has two solutions, 2 and 3.
The equation x2 ≡ −1 (mod 7) has no solution.

Solutions to Exercises for Section 5

Solution to Exercise 40

1. 79 (mod 99)
2. 29 (mod 35)
3. 207 (mod 221)
4. 77 (mod 90)

50
 5. 86 (mod 120)
6. 125 (mod 266)

Solution to Exercise 41

1. 86 (mod 120)
2. 178 (mod 330)

3. 37 (mod 273)
4. 281 (mod 462)
5. 3314 (mod 3315)

6. 32 (mod 630)

Solution to Exercise 42
Consider the following system of equations:

x ≡ a (mod n)
x ≡ b (mod m).

The first equation gives x = a + gn for some g ∈ Z. Then a + gn ≡ b (mod m),

gives gn ≡ b − a (mod m). If gcd(n, m) = d > 1 does divide b − a then there
are multiple solutions to this system.

Solution to Exercise 43
Consider the following system of equations:

x ≡ a (mod n)
x ≡ b (mod m).

The first equation gives x = a + gn for some g ∈ Z. Then a + gn ≡ b (mod m),

gives gn ≡ b − a (mod m). If gcd(n, m) = d does not divide b − a then there are
no solutions to this system.

Solution to Exercise 44
3, 36, 107, 140 (mod 143)

Solution to Exercise 45
1, 116, 183, 298 (mod 299)

51
Solutions to Exercises for Section 6

Solution to Exercise 47
1. 1, 2, 3, 4, 6, 8, 9.

2. 1, 2, 4.
3. 1, 3.
4. 1, 2, 7, 11.

5. 1, 2, 11.
6. 1, 2, 3, 4, 6, 8, 9.
7. 1.
8. 1, 5, 7.

9. 1, 2, 4, 5, 10.
10. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.

Solution to Exercise 48
A number is divisible by 12 if the sum of its digits is divisible by 3 and its
last two digits (as a two digit number) is divisible by 4.

Solution to Exercise 49
A number is divisible by 15 if the sum of its digits is divisible by 3 and its
last digit is either 0 or 5.

Solution to Exercise 50
A number is divisible by 16 if its last 4 digits (as a 4 digit number is divisible
by 16.

Solution to Exercise 51
A number is divisible by 20 if the its last two digits (as a two digit number)
is divisible by 4 and it ends in 0.

Solution to the Train Ride Problem

z = 1601.

52