Divisibility

a supplement to
Number Systems
by Sergei Ovchinnikov
AMS 2015
ISBN 978-1-4704-2018-5

Contents
0 About the Supplement 2

1 Basic Definitions and Properties 3

2 The Division Algorithm 4

3 The Greatest Common Divisor 5

4 The Euclidean Algorithm 7

5 The Least Common Multiple 9

6 Prime Factorization 10

7 Congruences 12

1
0 About the Supplement
The first two chapters of the textbook “Number Systems” [1] are
devoted to the rigorous development of the theory of integers (in-
cluding natural numbers in Chapter 1). To keep the volume of the
book down to acceptable limits, some properties of integers are not
included in the text. Most notably, the notion of divisibility of inte-
gers is absent from the book.
Divisibility is one of the basic concepts of arithmetic and number
theory, associated with the division operation. From the point of
view of set theory, the divisibility of integers is a relation defined on
the set of integers.
Only very basic properties of the divisibility relation are estab-
lished in the Supplement. The highlights of the presentation include
the Euclidean Algorithm for finding the Greatest Common Divisor
of two integers and the Fundamental Theorem of Arithmetic also
known as the Unique Factorization Theorem.
I hope that the material of this Supplement can serve as a launch-
ing pad for reader’s studies of other topics in number theory.

Sergei Ovchinnikov
sergei@[Link]
July 2022

2
1 Basic Definitions and Properties
Definition 1.1 Let a and b be integers. We say that a divides b, and write
a | b, if there is an integer q such that b = a · q. In this case, we also say that b
is divisible by a and call a and q divisors or factors of b.
If a does not divide b, we write a - b.

The following are trivial instances of these concepts:

(a) Every integer divides 0. (0 = a · 0, a ∈ Z.)
(b) Numbers 1 and −1 divide every integer. (b = 1 · b and b = (−1)(−b), b ∈ Z.)
(c) Every integer is divisible by itself. (b = b · 1, b ∈ Z.)

Theorem 1.1 If a | b and b 6= 0, then |a| ≤ |b|.

In words: a number cannot divide a smaller nonzero number.

Proof. Because b = a · q for some q ∈ Z, we have |b| = |a| · |q|. If |q| = 1, then
|b| = |a|. Otherwise, because |q| > 1, we have |b| = |a| · |q| > |a| · 1 = |a|, by
Theorem 2.21 b) in [1]. 
It follows immediately that, if a | b and b | a, then |a| = |b|.

Theorem 1.2 Let a, b, c, m, n ∈ Z. Then

(a) If a | b and b | c, then a | c.
(b) If a | b, then a | bc.
(c) If a | b, then ac | bc.
(d) If ac | bc and c 6= 0, then a | b.
(e) If a | b and a | c, then a | mb + nc.

Proof. (a) There are p, q ∈ Z such that b = ap and c = bq. It follows that
c = bq = (ap)q = a(pq), so a | c.
(b) There is q ∈ Z such that b = aq. Hence, bc = (aq)c = a(qc), so a | bc.
(c) There is q ∈ Z such that b = aq. Therefore, bc = (aq)c = (ac)q. Hence,
ac | bc.
(d) There is q ∈ Z such that bc = (ac)q. Hence, c(b − aq) = bc − (ac)q = 0.
Because c 6= 0, b = aq, by Theorem 2.32 in [1]. Therefore, a | b.
(e) There are p, q ∈ Z such that b = ap and c = aq. We have

mb + nc = map + naq = a(mp + nq).

Hence, a | mb + nc. 

3
2 The Division Algorithm
We recall the definition of the signum function (cf. [1, p. 118]):

1,
 if x > 0,
sgn x = 0, if x = 0, x ∈ R.

−1, if x < 0,


Clearly, for any real number x, |x| = x sgn x.

Theorem 2.1 (The Division Algorithm). Let a and b be integers with b 6= 0.

Then there exist unique integers q and r such that

a = bq + r, and 0 ≤ r < |b|.

The integers q and r in Theorem 2.1 are called the quotient and remainder,
respectively, upon dividing a by b.
Proof. (Existence.) If b | a, then there is an integer q such that a = bq + 0,
so r = 0.
Suppose that b - a and let

S = {a − bn : n ∈ Z and a − bn > 0}.

We show that S is a nonempty set.

There are three mutually exclusive cases:
1) a = 0. For n = −b we have a − bn = b2 > 0.
2) a > 0. For n = − sgn b we have a − bn = a + |b| > 0.
3) a < 0. For n = 2a(sgn b) we have

a − bn = a − b(2a(sgn b)) = −a(2|b| − 1) > 0.

Hence, S 6= ∅. By the Well-Ordering Principle (cf. Theorem 1.25 in [1]), the

set S contains a least element that we denote by r. Thus there is an integer q
such that a = bq + r. Clearly, r > 0. Suppose that r ≥ |b|. Note that r 6= |b|,
because b - a. We have

a − b(q + sgn b) = a − bq − b sgn b = r − |b| > 0,

so r − |b| ∈ S. This contradicts our assumption that r is the least element of S,

because r − |b| < r. It follows that r < |b|.
(Uniqueness.) Suppose that

a = bq1 + r1 = bq2 + r2 .

If r1 = r2 , then b(q1 − q2 ) = 0, so q1 = q2 (cf. Theorem 2.16 in [1]). Otherwise,

|r1 − r2 | = |b| · |q2 − q1 |,

so |b| divides |r1 − r2 | =

6 0. This contradicts Theorem 1.1, because |r1 − r2 | < |b|
(cf. Exercise 25 on p. 82 in [1]). 

4
Example 2.1 a) By dividing 33 by 5, we obtain 33 = 5 · 6 + 3. The quotient is
6, the remainder is 3.
b) By dividing −33 by 5, we obtain −33 = 5(−7) + 2. The quotient is −7,
the remainder is 2.

Example 2.2 (Even and odd integers.) For any integer a we have a = 2b + r,
r = 0 or 1, for some integer b. If r = 0, then a is an even integer. Otherwise, it
is an odd integer (cf. Exercise 11 on p. 30 in [1]).

The drawing in Figure 1 illustrates the Division Algorithm.

0 b 2b b(q-1) bq a b(q+1)

Figure 1: a = bq + r on the number line for 0 < b < a.

3 The Greatest Common Divisor

A common divisor of two integers is an integer that divides each of the integers.
The set C of all common divisors of two nonzero integers is not empty, because
1 ∈ C. By Theorem 1.1, this set is bounded and therefore finite. This argument
justifies the following definition.

Definition 3.1 The greatest common divisor (GCD) of two nonzero integers a
and b is the largest of all common divisors of a and b. It is denoted by gcd(a, b).
If gcd(a, b) = 1, then the integers a and b are said to be coprime (or relatively
prime).

If d is a divisor of an integer, so is −d. Therefore, gcd(a, b) is a positive

integer.

Theorem 3.1 If d is the greatest common divisors of a and b, then there exist
integers m and n such that
d = am + bn.

Proof. Let
S = {ax + by : x, y ∈ Z and ax + by > 0}.
Because a · a + b · 0 = a2 > 0, the set S is a nonempty set of positive integers.
By the Well-Ordering Principle (cf. Theorem 1.25 in [1]), the set S contains a
least element l = ax0 + by0 > 0. Below, we show that d = l.
First, we show that l | a and l | b. Suppose to the contrary that l - a. By
Theorem 2.1, there are integers q and r such that

a = lq + r, 0 < r < l.

5
Then
r = a − lq = a − (ax0 + by0 )q = a(1 − x0 q) + b(−y0 q),
so r ∈ S. Because r < l, this contradicts the fact that l is the least element in
the set S. Hence, l | a. A similar argument shows that l | b. It follows that l is
a common divisor of a and b.
Now, because d is the GCD of a and b, we have a = da0 and b = db0 for
some a0 , b0 ∈ Z. Therefore,

l = ax0 + by0 = d(a0 x0 + b0 y0 ),

so d | l. By Theorem 1.1, d ≤ l. Because d is the GCD of a and b, l ≤ d. Hence,

d = l. 
In the case of coprime integers we have a stronger result

Theorem 3.2 Two integers a and b are coprime if and only if there exist inte-
gers m and n such that
am + bn = 1.

Proof. (Necessity.) Follows immediately from the previous theorem (Theo-

rem 3.1).
(Sufficiency.) Suppose that there are m, n ∈ Z such that am+bn = 1. Then,
by Theorem 1.2(e), any common divisor of a and b is a divisor of 1. Clearly,
gcd(a, b) = 1. 
The result of the next theorem is often used as a definition of the GCD of
two integers.

Theorem 3.3 A positive integer d is the GCD of nonzero integers a and b if

and only if it is a positive common divisor of a and b which is divisible by every
common divisor of these integers.

Proof. (Necessity.) Let d = gcd(a, b) and c be a common divisor of a and b.

By Theorem 3.1, there are m, n ∈ Z such that d = am + bn. By Theorem 1.2(e),
c divides d.
(Sufficiency.) Let c and d > 0 be common divisors of a and b. If c | d, then,
by Theorem 1.1, c ≤ d. Hence, d is the GCD of a and b. 
We conclude this section by establishing three properties of coprime integers.
Note that two integers are coprime if and only if they have no common divisors
different from 1 and −1.

Theorem 3.4 If an integer a is coprime with integers b and c, it is coprime

with their product bc.

Proof. By Theorem 3.2, there are integers a1 , b1 , a2 and c1 such that

aa1 + bb1 = 1 and aa2 + cc1 = 1.

6
By multiplying these identities, we obtain

(aa1 + bb1 )(aa2 + cc1 ) = aa1 aa2 + aa1 cc1 + bb1 aa2 + bb1 cc1
= a(a1 aa2 + a1 cc1 + bb1 a2 ) + (bc)(b1 c1 ) = 1.

By the same theorem, a is coprime with bc. 

Theorem 3.5 If integers a and b are coprime and a | bc, then a | c.

Proof. Because a | bc, there is an integer d such that bc = ad. By Theo-

rem 3.2, there are integers a1 and b1 such that aa1 + bb1 = 1. Hence,

c = c(aa1 + bb1 ) = aca1 + bcb1 = aca1 + adb1 = a(ca1 + db1 ).

It follows that a | c. 

Theorem 3.6 If integers a and b are coprime, a | c, and b | c, then ab | c.

Proof. Because b | c, there is an integer d such that c = bd. Hence, a | bd

and gcd(a, b) = 1. By Theorem 3.5, a | d, so there is an integer r such that
d = ar. Hence, c = bd = (ab)r, so ab | c. 

4 The Euclidean Algorithm

The result of Theorem 2.1 is not a practical method for calculating the GCD
of two integers a and b. Below we describe a recursive procedure for finding
gcd(a, b), which is known as the Euclidean Algorithm. Arguably, it first appeared
as Proposition 2 in Book VII of Euclid’s Elements [2].
It is not difficult to see that

gcd(a, −b) = gcd(−a, b) = gcd(a, b)

for nonzero integers a and b. Hence to compute gcd(a, b) it suffices to consider

only positive integers a and b. Moreover, by symmetry, we may assume that
0 < b ≤ a. Clearly, gcd(a, a) = a, so below we assume that 0 < b < a.
The key element of the Euclidean Algorithm is the Division Algorithm
(cf. Theorem 2.1) augmented with the result of the following theorem.

Theorem 4.1 If a = bq + r, then gcd(a, b) = gcd(b, r).

Proof. Let d be a common divisor of a and b, that is, d | a and d | b. By

Theorem 1.2(e), d is a divisor of r = a − bq and therefore a common divisor of
b and r.
On the other hand, if d is a common divisor of b and r, it is also a common
divisor of a and b, by the same theorem.
It follows that the sets of common divisors of a and b and common divisors
of b and r are identical. Therefore, gcd(a, b) = gcd(b, r). 

7
Example 4.1 (a) Two consecutive integers, n and n + 1, are coprime, because
n + 1 = n · 1 + 1, so
gcd(n + 1, n) = gcd(n, 1) = 1.
(b) Similarly, two consecutive odd integers, 2n + 1 and 2n + 3, are coprime,
because
gcd(2n + 3, 2n + 1) = gcd(2n + 1, 2) = 1.

In the next paragraph, we present the Euclidean Algorithm.

For integers a > b > 0, we make a repeated application of the Division
Algorithm to obtain a chain of equations

a = bq1 + r1 , 0 < r1 < b,

b = r1 q 2 + r2 , 0 < r2 < r1 ,
r1 = r2 q 3 + r3 , 0 < r3 < r2 ,
···
rn−2 = rn−1 qn + rn , 0 < rn < rn−1 ,
rn−1 = rn qn+1 + 0.

Thus this chain of equations is derived by dividing a by b, b by r1 , r1 by r2 , . . . ,

rn−1 by rn . Because r1 > r2 > r3 > · · · > 0, the process stops, by the Well-
Ordering Principle, when the division is exact. Clearly, gcd(rn−1 , rn ) = rn .
Hence, by Theorem 4.1,

rn = gcd(rn−1 , rn ) = gcd(rn−2 , rn−1 ) = · · ·

= gcd(r2 , r1 ) = gcd(r1 , b) = gcd(a, b).

Clearly, gcd(a, b) = b, so we assume in the above chain of equations that

r1 > 0.

Example 4.2 Find the GCD of 48 and 18. We have

48 = 18 · 2 + 12,
18 = 12 · 1 + 6,
12 = 6 · 2 + 0.

Hence, gcd(48, 18) = 6.

The above equations can be used to represent 6 = gcd(48, 18) as a linear
combination of 48 and 18 (cf. Theorem 3.1):

12 = 48 + 18 · (−2),
6 = 18 + 12 · (−1)
= 18 + (48 + 18 · (−2))(−1)
= 48 · (−1) + 18 · 3.

8
5 The Least Common Multiple
Definition 5.1 The least common multiple (LCM) of two nonzero integers a
and b is the smallest positive integer that is divisible by both a and b. It is
denoted by lcm(a, b).

Because |a||b| = (sgn a · sgn b)ab > 0, the set of positive common multiples
of a and b is not empty and therefore, by the Well-Ordering Principle, has the
least element. Hence, lcm(a, b) exists and unique.
As we noted in the previous section,

gcd(a, −b) = gcd(−a, b) = gcd(a, b).

Clearly, also
lcm(a, −b) = lcm(−a, b) = lcm(a, b).
For this reason, we assume in this section that the integers a and b in gcd(a, b)
and lcm(a, b) are positive numbers.

Theorem 5.1 The LCM of two integers a and b divides every common multiple
of these integers.

Proof. Let k = lcm(a, b) and k1 be a common multiple of a and b. Suppose

to the contrary that k1 = kq + r, 0 < r < k for some integer q (cf. Theorem 2.1).
Then r = k1 − kq is divisible by a and b (cf. Theorem 1.2(e)), a contradiction,
because r < k = lcm(a, b). 

Theorem 5.2 For any two nonzero integers a and b,

gcd(a, b) · lcm(a, b) = ab.

Proof. Let k = lcm(a, b). By Theorem 5.1, ab = dk for some integer d. We

need to show that d = gcd(a, b).
Let k = aa1 and k = bb1 . Because ab = dk, we have ab = daa1 , so b = da1 .
Similarly, a = db1 . Hence, d is a common divisor of a and b.
Let d1 be a common divisor of a and b. Then ab = k1 d1 for some integer k1
and a = d1 a2 , b = d1 b2 for some integers a2 , b2 . Therefore,

d1 a2 d1 b2 = k1 d1 ,

so
k1 = d1 a2 b2 = ab2 = ba2 .
Hence, k1 is a common multiple of a and b. By Theorem 5.1, there is an integer
q such that k1 = kq. Because ab = dk = k1 d1 and k1 = kq, d1 divides d. By
Theorem 3.3, d = gcd(a, b). 
It is easy to see that gcd(a, b) · lcm(a, b) = |a||b|, if nonzero integers a and b
are not necessarily both positive.

9
6 Prime Factorization
Recall that a prime is a natural number greater than 1 whose only positive
divisors are 1 and the number itself. The numbers greater than 1 that are not
prime are called composite numbers.
It follows immediately from the definition that, if a prime p does not divide
a nonzero integer a, then gcd(p, a) = 1, that is, p and a are coprime.
The statement of the following theorem is known as Euclid’s Lemma
(Proposition 30, Book VII in [2]).

Theorem 6.1 Let p be a prime and a and b integers. If p | ab, then p | a or

p | b.

Proof. If p | a, we are done. Suppose that p - a, so p and a are coprime. By

Theorem 3.5 , p | b. 
The next theorem is a generalization of Euclid’s Lemma.

Theorem 6.2 Suppose that a1 , a2 , . . . , an are integers and p is a prime. If

p | a1 a2 · · · an , then p | ak for some k = 1, 2, . . . , n.

Proof. The proof is by mathematical induction. The base step, n = 2, is

Euclid’s Lemma (Theorem 6.1).
Suppose that the statement holds for some n ≥ 2 and p | a1 a2 · · · an an+1 . If
p | a1 , we are done. Otherwise, again by Theorem 6.1, p | a2 a3 · · · an an+1 . By
the induction hypothesis, there is k, 2 ≤ k ≤ n + 1, such that p | ak . 
Euclid’s Lemma plays a pivotal role in the proof of the Fundamental The-
orem of Arithmetic. The theorem states that every integer greater than 1 is
either prime or can be represented uniquely as a product of primes. Origi-
nally, the existence of prime factorization was established in Euclid’s Elements
(Propositions 30–32, Book VII in [2]). A rigorous proof of the uniqueness part
of the theorem was given by Gauss in his Disquisitiones Arithmeticae published
in 1801.

Theorem 6.3 (Fundamental Theorem of Arithmetic). Every integer greater

than 1 is a prime or a product of primes. This product is unique, up to the
order of factors.

Proof. (Existence.) Below we reproduce the proof given in [1, Example 1.48]
that uses the Strong Principle of Induction (Theorem 1.47 in [1]).
The property P (n) states “n > 1 is either prime or a product of primes”.
Suppose P (k) is true for all 2 ≤ k < m. There are two mutually exclusive cases:
Case 1. m is a prime number. Then P (m) is true and we are done.
Case 2. m is a composite number. Then it is a product of two natural
numbers each of which is different from 1. By the induction hypothesis each of
these two numbers is a product of primes. It follows that m itself is a product
of primes, that is, P (m) holds.

10
 (Uniqueness.) Suppose that there is an integer n > 1 that admits two
distinct prime factorizations:

n = p1 p2 · · · pr = q 1 q 2 · · · q s ,

where
p1 ≤ p2 ≤ · · · ≤ pr and q1 ≤ q2 ≤ · · · ≤ qs .
By the Well-Ordering Principle (cf. Theorem 1.25 in [1]), we may assume that
n is the smallest integer greater than 1 satisfying this property.
By Theorem 6.2, there is 1 ≤ k ≤ s such that p1 | qk , because p1 | n. Since
qk is prime, p1 = qk . Similarly, there is 1 ≤ l ≤ r such that q1 = pl . Then,
p1 = qk ≥ q1 = pl ≥ p1 . It follows that p1 = q1 . By the Cancellation Law of
Multiplication (cf. Theorem 2.32 in [1]), we have two distinct prime factorization
of the integer
m = p2 · · · pr = q 2 · · · q s .
We obtained a contradiction, because m < n. 
In contemporary terminology, Theorem 6.3 claims that the ring Z is a unique
factorization domain. The following examples demonstrate that there are rings
that are not unique factorization domains.

Example 6.1 Let R = 2 Z be the ring from Example 2.27c) in [1]. The numbers
2, 6, 10, 14, . . . are primes in R, because they are not products of positive
elements of R. We have two distinct factorization of 60 ∈ R into primes:

60 = 6 · 10 = 2 · 30.

The ring 2 Z from the above example is not an integral domain. The ring
in the next example is an integral domain which is not a unique factorization
domain.

Example 6.2 Let R be the set of complex numbers defined by

√
R = {z ∈ C : z = x + 5yi, x, y ∈ Z}.

It is easy to verify that R is closed under addition and multiplication of complex

numbers with the zero and identity elements 0 and 1, respectively. Because C
is a field, it follows
√ that R is an integral domain (cf. Definition 2.31 in [1]). It
is denoted by Z[ −5].
We say that z ∈ R is factored if there are z1 , z2 ∈ R such that

z = z1 · z2 , where |z1 | > 1 and |z2 | > 1.

Note that the only complex numbers z ∈ R with |z| ≤ 1 are integers 0, 1, −1.
Hence our definition of factoring excludes trivial factorings z = 1·z = (−1)·(−z).
A number z ∈ R with |z| > 1 that cannot be factored is called a prime in R.
We show that numbers 2 and 3 are primes in R. Indeed, suppose, for instance,

11
 √ √
that 2 = z1 · z2 where z1 = x1 + 5y1 i, z2 = x2 + 5y2 i. Clearly, y1 , y2 6= 0.
We have q q
2 = |2| = |z1 | · |z2 | = x21 + 5y12 · x22 + 5y22 ≥ 5,
a contradiction. The same argument shows that 3 is prime in R.
Finally, √ √
6 = 2 · 3 = (1 + 5i)(1 − 5i)
proves that there is no unique prime factorization
√ of 6 ∈√R. (Note that this
conclusion does not require showing that 1 + 5i and 1 − 5i are primes in R,
although they are.)

How many primes are there? To answer this question, we prove the following
theorem (cf. Book IX, Proposition 20 in Euclid’s Elements [2]).

Theorem 6.4 Let S = {p1 , . . . , pn } be a finite set of primes. There exists a

prime that does not belong to S.

Proof. Let q = p1 p2 · · · pn + 1. If q is a prime, then q ∈

/ S, because q > pk
for all 1 ≤ k ≤ n. Otherwise, let p be a prime factor of q. If p = pk for some
1 ≤ k ≤ n, then p | q and p | (q−1). By Theorem 1.2(e), p divides q−(q−1) = 1,
a contradiction. Hence, p ∈ / S. 
The result of the above theorem, clearly, implies that there are infinitely
many primes. However, as the next example demonstrates, primes are rather
“rare” elements of the set of integers N. Namely, it shows that for any positive
integer n there exist n consecutive composite integers.

Example 6.3 For n > 0, consider n consecutive integers

(n + 1)! + 2, (n + 1)! + 3, . . . (n + 1)! + k, . . . (n + 1)! + n + 1.

Each integer in this sequence is composite, because k divides (n + 1)! + k for

2 ≤ k ≤ n + 1.

7 Congruences
Definition 7.1 Let m be a nonzero integer. Two integers a and b are said to
be congruent modulo m if m divides a − b. In this case, we write

a≡b (mod m).

The integer m is called a modulus.

Because a − b is divisible by m if and only if it is divisible by −m, we may

assume that the modulus is a positive integer. Clearly, any two integers are
congruent modulo 1. In the rest of this section, the modulus m is an integer
greater than 1.

12
 When a = qm + r, where q is the quotient and r is the remainder upon
dividing a by m (cf. Theorem 2.1), we write

a mod m = r or a = r mod m,

and say that r is a modulo m. (Note that, in this case, a ≡ r (mod m).)
It follows immediately from the definition that a ≡ b (mod m) if and only
if a = b + mq for some integer q. Below, we use this fact without referring to it
explicitly.
The two properties of the congruence relation in the following theorem are
basic in modular arithmetic.

Theorem 7.1 If a ≡ b (mod m) and c ≡ d (mod m), then

a+c≡b+d (mod m) and ac ≡ bd (mod m).

Proof. We have a = b + mq and c = d + mq 0 for some q, q 0 ∈ Z. Then

(a + c) − (b + d) = (b + mq + d + mq 0 ) − (b + d) = m(q + q 0 ),

so m | [(a + c) − (b + d)]. Hence, a + c ≡ b + d (mod m).

Furthermore,

ac − bd = (b + mq)(d + mq 0 ) − bd =
= bd + bmq 0 + mqd + mqmq 0 − bd = m(bq 0 + qd + qmq 0 ),

so m | (ac − bd). Therefore, ac ≡ bd (mod m). 

By the Cancellation Law of Multiplication for integers (cf. Exercise 8, Chap-
ter 2, in [1]), if ac = bc and c 6= 0, then a = b. More care must be used in
dividing a congruence through by c, as the following example suggests.

Example 7.1 We have 2 · 3 ≡ 4 · 3 (mod 6). However, 2 6≡ 4 (mod 6).

Theorem 7.2 (Cancellation Law of Congruence.) If ac ≡ bc (mod m) and

gcd(c, m) = 1, then a ≡ b (mod m).

Proof. By Theorem 3.5, m | c(a − b) and gcd(c, m) = 1 imply m | a − b.

Hence, a ≡ b (mod m). 
The next theorem generalizes properties established in Theorem 7.1.

Theorem 7.3 Let

f (x) = cn xn + cn−1 xn−1 + · · · + c1 x + c0 , x, cn , . . . , c1 , c0 ∈ Z

be a polynomial of degree n considered as a function f : Z → Z.

If a ≡ b (mod m), then f (a) ≡ f (b) (mod m).

13
 The following proof can be easily made rigorous by using mathematical in-
duction.
Proof. We apply Theorem 7.1 repeatedly to obtain a2 ≡ b2 (mod m),
a ≡ b3 (mod m), . . . , an ≡ bn (mod m), then ck ak ≡ ck bk (mod m) for
3

k = 0, 1 . . . , n, and, finally,

cn an + · · · + c1 a + c0 ≡ cn bn + · · · + c1 b + c0 (mod m),

so f (a) ≡ f (b) (mod m). 

Example 7.2 (Tests for Divisibility.) Clearly, 10 ≡ 1 (mod 3). Suppose that
we have a natural number N whose decimal expansion is cn cn−1 . . . c1 c0 . This
means that
N = cn 10n + cn−1 10n−1 + · · · + c1 10 + c0 .
By Theorem 7.3,

N ≡ cn + cn−1 + · + c1 + c0 (mod 3).

We obtained a well-known test for divisibility by 3: add up the digits of the

number in base 10, and check if the result is divisible by 3. (Repeat, if necessary.)
Because 10 ≡ 1 (mod 9), the same test works for divisibility by 9.

The following theorem is known as Fermat’s Little Theorem. It is one of the

fundamental results in elementary number theory.

Theorem 7.4 If p is a prime, then ap ≡ a (mod p) for every integer a.

Proof. We assume that a > 0 and prove the claim by mathematical induction
on a. The base step, a = 1, trivially holds. Suppose that ap ≡ a (mod p) for
some a ≥ 1. By the binomial theorem,
     
p p p p−1 p p−k p
(a + 1) = a + a + ··· + a + ··· + a + 1,
1 k p−1

where  
p p · (p − 1) · · · (p − k + 1)
= , 0 < k < p.
k 1 · 2···k
Clearly, p divides kp for every k, 0 < k < p. By Theorem 7.1, all middle

terms in the above binomial expansion are congruent to zero. Therefore, by the
induction hypothesis,

(a + 1)p ≡ ap + 1 ≡ a + 1 (mod p).

Hence the result.

Clearly, 0 ≡ 0 (mod p). For a negative integer a the result follows from the
identities (−a)p = −ap for p > 2, and (−a)2 = a2 . 
Fermat’s Little Theorem is often stated in the following equivalent form.

14
Theorem 7.5 If p is prime and p - a, then ap−1 ≡ 1 (mod p).

Proof. By Theorem 7.2, ap ≡ a (mod p) implies ap−1 ≡ 1 (mod p), provided

that p - a. 
By definition, ≡ is a binary relation on the set of integers Z. Note that this
relation depends on the choice of modulus m.

Theorem 7.6 The relation ≡ is an equivalence relation on Z.

Proof. We need to establish three properties defining an equivalence relation

(cf. Section A.3 on page 132 in [1]).
Reflexivity. Clearly, a ≡ a (mod m) for all a ∈ Z.
Symmetry. If a = b + mq, then b = a + m(−q). Hence, a ≡ b (mod m)
implies b ≡ a (mod a).
Transitivity. Suppose that a = b + mq and b = c + mq 0 . Then,

a = c + m(q + q 0 ).

Therefore, a ≡ b (mod m) and b ≡ c (mod m) imply a ≡ c (mod m). 

For a ∈ Z, the equivalence class [a] of the relation ≡ (cf. Section A.3 on
page 132 in [1], especially, Theorem A.8 there) is called the residue class of a
modulo m. Clearly,

[a] = {a + mq : q ∈ Z} = {. . . a − 2m, a − m, a, a + m, a + 2m, . . .}.

By Theorem 2.1, for every a there exist unique integers q and r such that
a = mq + r and 0 ≤ r < m. Because a ≡ r (mod m), we have [a] = [r]. It
follows that there are exactly m distinct residue classes modulo m:

[0], [1], [2], . . . , [m − 1].

Definition 7.2 The set

Zm = {[a] : a ∈ Z} = {[0], [1], [2], . . . , [m − 1]}

is called the ring of integers modulo m or, simply, integers modulo m.

Operations of addition, +, and multiplication, · are defined on Zm by

[a] + [b] = [a + b] and [a] · [b] = [a · b],

respectively. By Theorem 7.1, these definitions are unambiguous.

Theorem 7.7 The set Zm endowed with operations + and · is a ring.

Proof. We need to verify conditions R1–R5 of Definition 2.24 on page 49

in [1]. Below, a, b, and c are integers.

15
R1. Because a + b = b + a, we have

[a] + [b] = [a + b] = [b + a] = [b] + [a].

R2. Because a + (b + c) = (a + b) + c, we have

[a] + ([b] + [c]) = [a] + [b + c] = [a + (b + c)]

= [(a + b) + c] = [a + b] + [c] = ([a] + [b]) + [c].

R3. Let x = [b − a]. Then

[a] + x = [a] + [b − a] = [a + (b − a)] = [b].

R4. We have

[a] · ([b] · [c]) = [a] · [b · c] = [a · (b · c)] = [(a · b) · c] = [a · b] · [c] = ([a] · [b]) · [c].

R5. We have

[a] · ([b] + [c]) = [a] · [b + c] = [a · (b + c)] = [a · b + a · c]

= [a · b] + [a · c] = [a] · [b] + [a] · [c].

Similarly, ([b] + [c]) · [a] = [b] · [a] + [c] · [a]. 

Clearly, [0] is the zero element of the ring Zm , and [1] is its unity.

Theorem 7.8 The ring Zm is a field if and only if m is prime.

Proof. (Necessity.) Suppose to the contrary that m is not prime, so there is

a nontrivial factorization m = a · b. Then [a] · [b] = [0], so Zm is not an integral
domain, a contradiction (cf. the note on the bottom of page 70 in [1]).
(Sufficiency.) Let m = p be a prime. For [a] 6= [0] in Zp , we have p - a.
By Fermat’s Little Theorem (Theorem 7.5), a · ap−2 ≡ 1. Hence, [ap−2 ] is the
multiplicative inverse of [a], so Zp is a field. 
Addition and multiplication tables for rings Z2 , Z3 , and Z4 are found in
Examples 2.27 b), 3.22, and Exercise 24 (Chapter 2), respectively, in [1].
The ring Zm is often defined as an algebraic structure hZm , +, ·i, where

Zm = {0, 1, 2, . . . , m − 1, m}

and operations of addition, +, and multiplication, ·, are defined by

a + b = (a + b) mod m and a · b = (a · b) mod m,

respectively. It can be shown that the algebraic structure hZm , +, ·i is a ring

isomorphic to the ring Zm .

16
References
[1] Ovchinnikov, S. Number Systems. An Introduction to Algebra and Analysis,
American Mathematical Society, Providence, Rhode Island, 2015.

[2] Fitzpatrick, R. Euclid’s Elements of Geometry, a modern English

translation, [Link]
pdf, 2008.

17