Foundations of Mathematics: Math 3250

University of Missouri - St. Louis

David Covert

Lecture Notes
What follows is a set of lecture notes for the course Foundations of Mathematics (Math
3250) taught at University of Missouri - Saint Louis. Kindly notify me of any typos/errors
at CovertDJ@[Link].

An up-to-date version of this course notes where errors will be updated frequently can be
found on my website: [Link] in the “Lecture Notes”
section. Many of the graphs in this text have been generating using GeoGebra.

2
Contents

1 Sets and Relations 5

1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1 Weak Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Relations, Functions, and Cardinality 21

2.1 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.1 Sequences and Series . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3 Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3 Logic and Proofs 37

3.1 Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Structure of Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1 Primary Types of Proofs . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4 Number Theory 49
4.1 Basic Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.2 Primes and Euclid’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2.1 Greatest Common Divisors . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.2 Linear Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.2.3 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5 Combinatorics 73
5.1 Basic Definitions and Examples . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.1.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2 Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.3 Inclusion-Exclusion Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.4 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3
 5.4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5 Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6 Inequalities 85
6.1 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7 Appendix 93
7.1 Real Number Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.2 Integer Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

4
Chapter 1

Sets and Relations

1.1 Sets
We can think of a set as simply a collection of objects. We use capital letters A, B, C, etc.
to denote sets. The objects in a set are called elements of the set, and we write x is an
element of A as “x ∈ A.” Two sets are equal (written A = B) if A and B have exactly the
same elements. There are a few common sets for which it will be nice to have a shorthand
notation.
Definition 1.1. The integers Z = {. . . , −2, −1, 0, 1, 2, . . . } are the positive whole num-
bers, the negative whole numbers, and zero. The positive integers will be denoted by
Z+ = Z>0 = {1, 2, 3 . . . }, while the nonnegative integers (also called the natural num-
bers) nare denoted N = Z>0o= {0, 1, 2, 3, . . . }.1 The rational numbers will be written as
a
Q= : a, b ∈ Z and b 6= 0 , and the irrational numbers are the real numbers which can
b
never be expressed as a fraction of integers. Then, R will denote the real numbers which
are the numbers that are rational or irrational2 . The empty set ∅ = {} is the set with no
elements.
Definition 1.2.
• The union of two sets A and B is the set
A ∪ B = {x : x ∈ A or x ∈ B}.

1
Note that some authors refer to the positive integers as the natural numbers, so please be careful when
reading other resources!
2
This definition of the real numbers is circular, but to rigorously define the reals takes some care. For
now it is sufficient to think of the real numbers as the set of numbers with a decimal expansion.

5
 • The intersection of A and B is the set

A ∩ B = {x : x ∈ A and x ∈ B}.

• The set difference of A and B is

A \ B = {x ∈ A : x ∈ B}

• The symmetric difference of A and B is

A ⊕ B = {x : x ∈ A ∪ B and x ∈
/ A ∩ B}.

Example 1.3. Let A = {1, 4, 6, 9} and B = {0, 2, 4, 6}. Then:

A ∪ B = {0, 1, 2, 4, 6, 9}
A ∩ B = {4, 6}
A ⊕ B = {0, 1, 2, 9}

Definition 1.4. The Cartesian Product of A and B is

A × B = {(a, b) : a ∈ A and b ∈ B}.

6
Figure 1.1: The Cartesian Product A × B, where A = {2, 4, 5, 8} and B = {1, 2, 4}. Note
that A × B 6= B × A for general sets A and B.

Example 1.5. If A = {0, 1} and B = {0, 2, 4}, then

A × B = {(0, 0); (0, 2); (0, 4); (1, 0); (1, 2); (1, 4)}

while

B × A = {(0, 0); (2, 0); (4, 0); (0, 1); (2, 1); (4, 1)}

Definition 1.6. Two sets A and B are called disjoint if A ∩ B = ∅.

Definition 1.7. We say that A is a subset of B (written A ⊆ B or A ⊂ B) when x ∈ A

implies x ∈ B.

Two sets A and B are equal (written A = B) when they contain exactly the same
elements. Equivalently, A = B if and only if A ⊆ B and B ⊆ A. This characterization
will be very useful for us, as we will see in the time to come. Furthermore to show that
A ⊆ B, we will pick an arbitrary element of A, and show that it must also be in B. This
demonstrates that every element of A is in B.

Proposition 1.8. For any sets A and B we have

(i) (A ∩ B) ⊆ A

(ii) A ⊆ (A ∪ B)

(iii) ∅ ⊆ A

(iv) A ⊆ A

Proof. To prove that one set is a subset of another, we pick an arbitrary element in the first
set, and then demonstrate that the element must also be in the second set. For example
to see that (A ∩ B) ⊆ A, pick x ∈ A ∩ B. Then x ∈ A and x ∈ B. In particular x ∈ A.

7
Thus we have shown that (A ∩ B) ⊆ A. Notice for number (iii), the statement is vacuously
true. That is the statement “if x ∈ ∅, then x ∈ A” is true for all sets A since the initial
hypothesis “x ∈ ∅” is never satisfied. We leave the proofs of the other two statements as an
exercise.

Proposition 1.9. For all sets A, B, C we have:

(i) A ∪ B = B ∪ A

(ii) A ∩ B = B ∩ A

(iii) A ∪ (B ∪ C) = (A ∪ B) ∪ C

(iv) A ∩ (B ∩ C) = (A ∩ B) ∩ C

In particular A ∪ B ∪ C and A ∩ B ∩ C are unambiguous without the need for parentheses.

Proof. Exercise.

Definition 1.10. The set U will denote the universal set, that is, the set of all elements
under consideration. This universal set will depend on context, but the choice of universal
set should always be clear. The complement of a set A, denoted A, is the set of elements in
the universal set which are not in A. That is, A = {x ∈ U : x ∈
/ A} = {x ∈/ A}.

Proposition 1.11 (De Morgan’s Law). For all sets A and B we have:

(i) A ∪ B = A ∩ B, and

(ii) A ∩ B = A ∪ B.

Proof. We only prove the first statement, and leave the second statement as an exercise.
Notice that we two statements to prove. First we will show A ∪ B ⊆ A ∩ B. Then we will
also need to show A ∩ B ⊆ A ∪ B.

Pick x ∈ A ∪ B. Then x ∈ / (A ∪ B). Notice that if x ∈ A or if x ∈ B, then x ∈ A ∪ B.

Thus, x ∈/ A and x ∈/ B. In other words x ∈ A and x ∈ B. It follows that x ∈ A ∩ B. Thus
we have the first inclusion: A ∪ B ⊆ A ∩ B. For the second part, assume that x ∈ A ∩ B.
Then x ∈ / A and x ∈/ B. Suppose x ∈ A ∪ B, so that either x ∈ A or x ∈ B. If x ∈ A this
would contradict x ∈/ A. Likewise if x ∈ B this would contradict x ∈/ B. Hence, x ∈
/ A ∪ B.
It follows that x ∈ A ∪ B. Thus we have A ∩ B ⊆ A ∪ B. Since both A ∪ B ⊆ A ∩ B and
A ∩ B ⊆ A ∪ B, then we finally see that A ∪ B = A ∩ B.

8
Figure 1.2: A Visual depiction of DeMorgan’s Law. Remember that a picture is not a proof!

Proposition 1.12. For any sets A, B, C we have the following distributive laws

(i) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), and

(ii) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Proof. Again we prove only the first statement and leave the second set equality as an
exercise. First we will show that A ∪ (B ∩ C) ⊆ (A ∪ B) ∩ (A ∪ C). Let x ∈ A ∪ (B ∩ C). If
x ∈ A, then x ∈ A ∪ B and x ∈ A ∪ C. Hence, x ∈ (A ∪ B) ∩ (A ∪ C). If x ∈ B ∩ C, then
x ∈ B and x ∈ C. Then x ∈ A ∪ B and x ∈ A ∪ C. Thus, x ∈ (A ∪ B) ∩ (A ∪ C).
Next we will show that (A ∪ B) ∩ (A ∪ C) ⊆ A ∪ (B ∩ C). Let x ∈ (A ∪ B) ∩ (A ∪ C). If
x ∈ A then x ∈ A ∪ (B ∩ C). If x ∈ / A, then x ∈ A ∪ B implies x ∈ B. Likewise x ∈ A ∪ C
implies x ∈ C. Hence x ∈ B ∩ C, so that x ∈ A ∪ (B ∩ C).

Figure 1.3: The set A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). Again a picture is not a proof!

Definition 1.13. The Power Set of A is denoted 2A or P(A), and it consists of the collection
of all subsets of A. For example if A = {1, 2, 3}, then

2A = ∅; {1}; {2}; {3}; {1, 2}; {1, 3}; {2, 3}; {1, 2, 3} .


9
 We say that a set A is finite if the number of elements in A is a nonnegative integer. If A is
a finite set with n elements we say that A has cardinality n, and we write |A| = n. If A and B
are disjoint sets, then |A∪B| = |A|+|B|. Also, if A is a finite set, then |A\B| = |A|−|A∩B|.
Thus for general finite sets A and B, we have |A ∪ B| = |A| + |B| − |A ∩ B|, since we are
double-counting the elements of A ∩ B. More rigorously we can partition A ∪ B intro three
disjoint sets A ∪ B = (A \ B) ∪ (A ∩ B) ∪ (B \ A). Since these sets are disjoint, we have:

|A ∪ B| = |A \ B| + |A ∩ B| + |B \ A|
= |A| − |A ∩ B| + |A ∩ B| + |B| − |A ∩ B|
= |A| + |B| − |A ∩ B|.

Figure 1.4: The inclusion-exclusion principle: |A ∪ B| = |A| + |B| − |A ∩ B|

10
1.2 Principle of Mathematical Induction
1.2.1 Weak Induction
Suppose that P (n) is a statement concerning all integers n > 1, say P (n) = “2n > n.”
One method we could use to prove such results is called induction (also sometimes called
mathematical induction or “weak” induction), and induction works as follows. First, we will
check that P (1) is true, and we can do this by hand: 21 > 1 since 21 = 2, which shows P (1)
is true. Our second and last step is to show that if the statement is true for some integer
k > 1, then it is also true for k + 1. We will finish this proof below.

Proposition 1.14. Let P (n) be some statement concerning all integers n > n0 . Then to
show that P (n) is true for all n > n0 , it is enough to show the following:

(i) P (n0 ) is true

(ii) If P (k) is true for some k > n0 , then P (k + 1) is also true

Remark 1.15. Step (i) is called the base case or base step while step (ii) is referred to as the
inductive step. Also the statement P (k) that we assume is true for some k > n0 is called
the inductive hypothesis. Notice that for the inductive step, we assume that P (k) is true
for some k > n0 . Be careful never to assume that P (k) is true for all k > n0 , since that is
precisely what we are showing (hence, circular reasoning). Furthermore, we are showing two
things in a proof by induction. We are showing that the base case is true (say for n = n0 ),
and then we are showing that if P (k) is true for some k > n0 , then P (k + 1) is also true.
Also, notice that induction is a very method we can utilize to prove something, but it doesn’t
tell us what to prove.
n
X xn+1 − 1
Example 1.16. For x 6= 1, show that xj = for all n > 0.
j=0
x−1

Proof. We check the base case by hand. When n = 0, we have

0
X x−1
xj = x0 = 1 =
j=0
x−1

so that the statement holds when n = 0. Now, for the inductive step. Suppose that the
statement
k
X xk+1 − 1
xj =
j=0
x−1

holds for some k > 0. We will show that the statement also holds for k + 1. To see this, we

11
write
k+1
X k
X
j
x = xj + xk+1
j=0 j=0

xk+1 − 1
= + xk+1
x−1
xk+1 − 1 + xk+1 (x − 1)
=
x−1
k+2
x −1
=
x−1
and it follows that if the statement holds for some k > 0, then it also holds for k + 1. By
the principle of mathematical induction, this establishes the claim.
Recall that the factorial is defined as

n(n − 1) . . . (2)(1) n>1
n! =
1 n=0

Hence 0! = 1! = 1, and 5! = 5 · 4 · 3 · 2 · 1.
Example 1.17. Show that 2n < n! for n > 4.
Proof. First, we check the base case n = 4: If n = 4, then 24 = 16 and 4! = 24. Since
16 < 24, the base case indeed holds. Now, suppose that 2k < k! for some k > 4. We will
show the statement also holds for k + 1. We have

2k+1 = 2 · 2k < 2 · k! < k!(k + 1) = (k + 1)!.

Note that the inequality 2k < k! was our inductive hypothesis, and the inequality 2 < k + 1
followed since we assumed k > 4. This establishes the inequality.
Example 1.18. Let
n
1 1 1 X1
Hn = 1 + + + · · · + =
2 3 n j=1
j

n
be the nth Harmonic number. Show that H2n > 1 + 2
for all n > 0. Conclude that the
harmonic series diverges.
Proof. We first check our base case n = 0:
1
X 1 0
H20 = H1 = =1>1+
j=1
j 2

which is a valid inequality. Now, suppose that

k
H2k > 1 +
2
12
holds for some k > 0. Now
k+1
2X
1
H2k+1 =
j=1
j
2k k+1
2X
X 1 1
= +
j=1
j j
j=2k +1
2X k+1
k 1
>1+ +
2 k
j
j=2 +1

1 1
Thus for 2k + 1 6 j 6 2k+1 , note that j 6 2k+1 , and hence > k+1 . Then we have
j 2
2X k+1
k 1
H2k+1 >1+ +
2 k
j
j=2 +1
2X k+1
k 1
>1+ +
2 k
2k+1
j=2 +1
k 1
=1+ + k+1 · 2k
2 2
k+1
=1+ ,
2
and this concludes our proof.

Example 1.19. Show that 2n > n for all n > 1, thus finishing our example from the
beginning of the section.

Proof. We first check the base case n = 1: 21 > 1, so that the base case holds. For the
inductive step, suppose that 2k > k for some k > 1. Then:

2k+1 = 2 · 2k > 2 · k > k + 1,

since k > 1.

13
1.2.2 Strong Induction
There are some cases where standard induction is simply not robust enough to use. For
these occasions, we will employ strong induction.

Proposition 1.20. Let P (n) be a statement about all integers n > n0 . To show that P (n)
is true for all n > n0 , it is enough to show the following:

(i) P (n0 ), P (n0 + 1), . . . , P (s) are all true

(ii) If P (j) is true for all values j such that n0 6 j 6 k for some k > s, then P (k + 1) is
true.

Remark 1.21. This is called strong induction, since we are making stronger assumptions.
The difference between strong induction and weak (or regular) induction is twofold. First,
note that there can be multiple base cases for strong induction, and the number of necessary
base cases will depend on the situation. Second, with regular induction you are showing that
the (k + 1)-st case follows from the kth case, whereas with strong induction, you show that
the (k + 1)-st case follows from all of the previous cases.

Example 1.22. Let (fn ) be the nth Fibonacci number. That is, f0 = 0, f1 = 1, and when
√
1 + 5
n > 2, we define fn = fn−1 + fn−2 . Show that fn > ϕn−2 for all n > 2, where ϕ =
2
satisfies ϕ2 = ϕ + 1.

Proof. Because the Fibonacci sequence is defined by the sum of its two previous values, we
0
will have two base cases
√ to check: First, when n = 2, we have f2 = 1 > ϕ . When n = 3, we
1+ 5
have f3 = 2 > ϕ = 2 . Now for the inductive step suppose that fj > ϕj−2 for all j such
that 2 6 j 6 k for some k > 3. Then,

fk+1 = fk + fk−1
> ϕk−2 + ϕk−3
= ϕk−3 (ϕ + 1)
= ϕk−3 · ϕ2
= ϕk−1

as claimed.
√ √
1+ 5 1− 5
Example 1.23. Set ϕ = and β = , and note that both ϕ2 = ϕ + 1 and
2 2
β 2 = β + 1. Let fn be the nth Fibonacci number. Prove that

ϕn − β n
fn =
ϕ−β

for all n > 0.

14
Proof. We first check the two bases cases:

ϕ0 − β 0 1−1
f0 = 0 = =
ϕ−β ϕ−β
and
ϕ−β
f1 = 1 = .
ϕ−β

ϕj − β j
Next for the inductive step we assume that fj = for all 0 6 j 6 k for some k > 1.
ϕ−β
Then

fk+1 = fk + fk−1
ϕk − β k ϕk−1 − β k−1
= +
ϕ−β ϕ−β
k k−1
ϕ +ϕ − β k − β k−1
=
ϕ−β
ϕ (ϕ + 1) − β k−1 (β + 1)
k−1
=
ϕ−β
k+1 k+1
ϕ −β
= .
ϕ−β

Example 1.24. Let (Tn ) be the tribonacci sequence. That is, define T1 = T2 = T3 = 1, and
Tn = Tn−1 + Tn−2 + Tn−3 for n > 4. Prove that Tn < 2n for all n > 1.

Proof. We will have three bases cases: T1 = 1 < 21 ; T2 = 2 < 22 ; T3 = 1 < 23 . Now, suppose
that Tj < 2j for all 1 6 j 6 k for some k > 3. Then,

Tk+1 = Tk + Tk−1 + Tk−2

< 2k + 2k−1 + 2k−2
= 2k−2 (4 + 2 + 1)
< 2k−2 · 23
= 2k+1 .

15
1.3 Exercises
Exercise 1.1. Determine whether the following statements are true or false:
(A) 0 ∈ ∅

(B) {0} ⊆ ∅

(C) ∅ ∈ ∅

(D) ∅ ⊆ ∅

(E) ∅ ∈ {∅, {∅}}

(F) ∅ ⊆ {∅, {∅}}

(G) {∅} ∈ {∅, {∅}}

(H) {{∅}} ⊆ {∅, {∅}}

Exercise 1.2. Determine whether the following statements are true or false:
(A) 2 ∈ {Z}

(B) 2 ⊆ {Z}

(C) 2 ∈ Z

(D) {2} ⊆ Z

(E) {2} ⊆ {Z}

(F) {2} ∈ Z
Exercise 1.3. Write down the set 2A given A = {3, 4, 5}. What is the cardinality of 2A ?
Exercise 1.4. Are the sets A × (B × C) and (A × B) × C the same set? Explain.
Exercise 1.5. Finish the proof of Proposition 1.8.
Exercise 1.6. Prove Proposition 1.9, part (iii).
Exercise 1.7. Prove the following version of DeMorgan’s Law for sets A and B:

A∩B =A∪B

Exercise 1.8. Prove that for sets A and B we have

A \ B = A ∩ B.

Exercise 1.9. Prove that for sets A and B we have

A ∩ (B \ A) = ∅.

16
Exercise 1.10. Prove or find a counterexample. If A ∩ C = B ∩ C, then A = B.
Exercise 1.11. Prove or find a counterexample. If A ∪ C = B ∪ C then A = B.
Exercise 1.12. Prove or disprove that for sets A and B we have

A \ (A \ B) ⊆ B.

Exercise 1.13. Prove or find a counterexample. If A ⊆ B then B ⊆ A.

Exercise 1.14. Prove or find a counterexample. If A ⊆ B then 2A ⊆ 2B .
n
X
Exercise 1.15. Prove that (2j − 1) = n2 for all integers n > 1.
j=1

n
X n(n + 1)
Exercise 1.16. Prove that j= for all integers n > 1.
j=1
2

n(n + 1)(2n + 1)
Exercise 1.17. Prove that 12 + · · · + n2 = for all n > 1.
6
Exercise 1.18. Prove that (1 + · · · + n)2 = 13 + · · · + n3 for all n > 1.
√
Exercise 1.19. Consider (xn ) such that x0 = 1 and xn+1 = xn + 6. Prove that xn < 3 for
all n > 0.
Exercise 1.20 (Bernoulli’s Inequality). Let x > −1 be a real number. Prove that for all
n > 0 we have

(1 + x)n > 1 + nx.

n
X
Exercise 1.21. Prove that j · j! = (n + 1)! − 1 for all n > 1.
j=1

n ∞
X 1 1 X 1
Exercise 1.22. Prove that 2
6 2 − for all n > 1. Conclude that 2
converges.
j=1
j n j=1
j
√
Exercise 1.23. Define x1 = 1 and xn+1 = 1 + xn . For example:
r
√ √
q q
x2 = 1 + 1, x3 = 1 + 1 + 1,

and so on. Prove that xn is irrational for all n > 2.

Exercise 1.24. Prove that
    
1 1 1 n+1
1− 2 1 − 2 ... 1 − 2 =
2 3 n 2n
for all n > 2.

17
Exercise 1.25. Prove that if (an ) is a recursive sequence defined by an = 3an−1 − 2an−2
(when n > 2) and a0 = 0, a1 = 1, then we have an = 2n − 1 for all n > 0.
n
X
Exercise 1.26. Prove that fj = fn+2 − 1 for all n > 0, where (fn ) is the Fibonacci
j=0
sequence.
Exercise 1.27. Let A1 , . . . , An be finite sets. Prove the following generalizations of DeMor-
gan’s Law for sets:
A1 ∪ · · · ∪ An = A1 ∩ · · · ∩ An
and
A1 ∩ · · · ∩ An = A1 ∪ · · · ∪ An .
Exercise 1.28. Find the error in the following false “proof” of the statement:

n  2
X 1 1
j= n+
j=1
2 2

for all n > 1.

Proof. The base case clearly holds. For the induction step, suppose that the statement is
true for some k > 1. Then,
k+1
X k
X
j= j + (k + 1)
j=1 j=1
 2
1 1
= k+ + (k + 1)
2 2
 
1 2 1
= k +k+ +k+1
2 4
1 2 3 9
= k + k+
2 2 8
 2
1
1
= k+1 +
2 2

Exercise 1.29. Find the error in the following false “proof” of the statement:

2n > n2 for all n > 0.

Proof. The base case clearly holds as 20 > 02 . For the inductive step, we have
2k+1 = 2 · 2k > 2 · k 2 > (k + 1)2 .
as claimed.

18
Exercise 1.30. Find the error in the following false “proof” of the statement:

Let (f√n ) be the Fibonacci sequence. Prove that for all n > 2, we have fn = ϕn−2 , where
1+ 5
ϕ= satisfies ϕ2 = ϕ + 1.
2
Proof. The base case holds for n = 2: f2 = 1 = ϕ0 . For the inductive step: Suppose that
the statement holds for all values j such that 2 6 j 6 k for some k > 2. Then,

fk+1 = fk + fk−1
= ϕk−2 + ϕk−3
= ϕk−3 (ϕ + 1)
= ϕk−3 ϕ2
= ϕk−1 .

19
20
Chapter 2

Relations, Functions, and Cardinality

2.1 Relations
Definition 2.1. Given sets A and B, we say a (binary) relation R from A to B is any subset
R ⊆ A × B. A relation from A to A is called a relation on A.
For example

R1 = {(x, y) ∈ R × Q : x2 = y}

is a relation from R to Q, and

R2 = {(x, y) ∈ R × R : x 6 y}

is a relation on R.
Definition 2.2. A relation R on a set A is said to be reflexive if (x, x) ∈ R for all x ∈ A.
R is said to be symmetric if (x, y) ∈ R implies (y, x) ∈ R for all x, y ∈ A. R is said to be
transitive if (x, y) ∈ R and (y, z) ∈ R implies (x, z) ∈ R for all x, y, z ∈ A.
Note 2.2.1. Some authors write (x, y) ∈ R as xRy. Thus R is reflexive if xRx for all x ∈ A,
R is symmetric if xRy implies yRx for all x, y ∈ A, and R is transitive if xRy and yRz
implies xRz for all x, y, z ∈ A.
Example 2.3. Consider the relation

R = {(x, y) ∈ R × R : x 6 y}.

Then R is reflexive since x 6 x for all x ∈ R (and hence (x, x) ∈ R for all x ∈ R). R is not
symmetric since (1, 2) ∈ R, but (2, 1) ∈/ R. R is transitive since if x 6 y and y 6 z, then
x 6 z for all x, y, z ∈ R.
For real numbers x we define the floor and ceiling functions as

bxc = max(n ∈ Z : n 6 x) and dxe = min(n ∈ Z : n > x),

respectively.

21
Example 2.4. Let S = {(x, y) ∈ R × R : bxc = byc}. Then S is reflexive, symmetric, and
transitive. We leave the details as an exercise.
Definition 2.5. A relation is said to be an equivalence relation if it is reflexive, symmetric,
and transitive. If R is an equivalence relation then we write x ∼ y for (x, y) ∈ R.
Definition 2.6. Given an equivalence relation R on a set A, the equivalence class of a ∈ A
is the set

[a] = {b ∈ A : (a, b) ∈ R} = {b ∈ A : a ∼ b}.

Definition 2.7. Given a set X and an equivalence relation R 6= ∅, the quotient set of X/R
(said “X mod R”) is the set of all equivalence classes of X under R.
We say that an integer x is even if there exists k ∈ Z such that x = 2k. Similarly x ∈ Z
is odd if there exists k ∈ Z such that x = 2k + 1.
Example 2.8. Let R = {(x, y) ∈ Z × Z : x − y is even}. Then R is reflexive since x − x = 0
is even for all x ∈ Z. Moreover if x − y is even, then there exists k ∈ Z with x − y = 2k. Thus
y − x = 2(−k). Finally, if x − y is even, and if y − z is even, then there exist k, ` ∈ Z such
that x − y = 2k and y − z = 2`. Therefore, x − z = (x − y) + (y − z) = 2k + 2` = 2(k + `),
so x − y is even as well. It follows that R is an equivalence relation.

Next, we will describe the equivalence class [7]. Using the definition we have

[7] = {x ∈ Z : x ∼ 7}
= {x ∈ Z : x − 7 is even}
= {x ∈ Z : x is odd}
= {. . . , −3, −1, 1, 3, . . . }

When we write [7] = {. . . , −3, −1, 1, 3, . . . }, we say that 7 is the representative of the
equivalence class. Likewise we also have [1] = {. . . , −3, −1, 1, 3, . . . } = [7]. Thus we can
have more than one way to describe a set! On the other hand, consider

[0] = {x ∈ Z : x ∼ 0}
= {x ∈ Z : x − 0 is even}
= {. . . , −4, −2, 0, 2, 4, . . . }

Finally, notice that the quotient set Z/R = {[0], [1]} contains only two elements. More-
over, these two sets split Z into two parts: Z = [0] ∪ [1], since every integer is either even or
odd, and hence every integer is equivalent to either 0 or 1. Also, [0] and [1] are disjoint. We
will say that the sets [0] and [1] partition Z.
Example 2.9. Let X = {(a, b) ∈ Z × Z : b 6= 0}. Then,


R = (a, b); (c, d) ∈ X × X : ad = bc

is an equivalence relation on X. The quotient set formally defines the rational numbers.
That is, X/R = Q.

22
Example 2.10. Let X = R2 \ {(0, 0)}. Define an relation R on X where (x, y) ∈ X and
(x0 , y 0 ) ∈ X are related if the points (x, y) and (x0 , y 0 ) lie on the same line through the origin.
This defines an equivalence relation. The quotient set is called the real projective plane of
R2 and is denoted RP 2 or P G(2, R).

Definition 2.11. A partition of a set X is a collection of subsets {A1 , A2 , A3 , . . . } such that:

(i) Ai 6= ∅ for all i,

(ii) Ai ∩ Aj = ∅ for i 6= j, and

(iii) ∪i Ai = X.

Proposition 2.12. Suppose that R is an equivalence relation on a set A, and let a, b ∈ A.

Then the following are equivalent.

(i) a ∼ b

(ii) a ∈ [b]

(iii) [a] ∩ [b] 6= ∅

(iv) [a] = [b]

Proof. Exercise 2.8.

Theorem 2.13. Given an equivalence relation R on A, the set of equivalence classes of

R forms a partition of A. Conversely, every partition of A is derived from an equivalence
relation R on A.

Proof. Exercise 2.9.

23
2.2 Functions
Let R ⊆ A × B be a binary relation. We say that R is defined (or serial) if for each a ∈ A,
there exists b ∈ B such that (a, b) ∈ R. We say that R is well-defined if for each a ∈ A, there
exists a unique b ∈ B such that (a, b) ∈ R. In other words, R is well-defined if (a, b) ∈ R
and (a, c) ∈ R implies b = c.

Relations which are both defined and well-defined are called mappings (or functions) from
A to B. Rather than referring to the underlying relation R ⊆ A × B, it is customary to
think of a function f from A to B as a rule which maps elements in A to elements in B.
Note that A is called the domain of f , while B is called the codomain of f (the range of
f comes later). Therefore by definition we know that if f : A → B is a function, then for
every a ∈ A, there exists b ∈ B with f (a) = b. If f (a) = b, we call b the image of a (under
f ), and we say a is a preimage of b.

Next, suppose that f : A → B is a function, and C ⊆ A. The image of C under f is the set
f (C) = {f (x) : x ∈ C}.
The image of A under f (where A is the domain of f ) is called the range of f . On the other
hand if D ⊆ B, then we define the preimage of D under f as the set
f −1 (D) = {x ∈ A : f (x) ∈ D}.
Note that for z ∈ A, we have z ∈ f −1 (D) if and only if f (z) ∈ D.
Example 2.14. Let f : Z → N be given by f (x) = x2 . Then Z is the domain of f and N is
the codomain of f . Moreover we have
f ({−1, 0, 1, 2, 3}) = {f (−1), f (0), f (1), f (2), f (3)} = {0, 1, 4, 9},
and
f −1 ({4}) = {x ∈ Z : f (x) ∈ {4}} = {x ∈ Z : x2 = 4} = {−2, 2}.
Note that f −1 ({3}) = ∅, since x2 = 3 has no solutions in Z. Finally the range of f is the set
of squares:
f (Z) = {f (x) : x ∈ Z} = {x2 : x ∈ Z} = {0, 1, 4, 9, 16, . . . }
Example 2.15. Let f → Z → Z be given by f (x) = 4x + 3. Then Z is both the domain and
codomain of f . Moreover, f ({1, 2, 3}) = {7, 11, 15}, while f −1 ({1, 2, 3, 4}) = {0}. Finally
the range of f is
{f (x) : x ∈ Z} = {4x + 3 : x ∈ Z} = {. . . , −5, −1, 3, 7, . . . }.
Definition 2.16. We will say that the function f : A → B is one-to-one (or injective) if:
f (x) = f (y) implies x = y for all x, y ∈ A.
If f : A → B where A, B ⊆ R, then f will be one-to-one if and only if it passes the horizontal
line test.

24
Example 2.17. The function f : R → R given by f (x) = 2x + 1 is one-to-one since:

f (x) = f (y) =⇒ 2x + 1 = 2y + 1
=⇒ 2x = 2y
=⇒ x = y.

Example 2.18. The function f : R → R given by f (x) = x2 is not one-to-one since

f (−1) = f (1), but −1 6= 1. Notice that f (x) = f (y) =⇒ x = ±y. This is both too
much and not enough information. Precisely, we do not need to solve this equation, though
the solution to the equation can suggest counterexample. This solution x = ±y is not a
counterexample, and thus it is not sufficient to show that f is not one-to-one.

Example 2.19. The function f : Z+ → Z+ given by f (x) = x2 is one-to-one since:

f (x) = f (y) =⇒ x2 = y 2 =⇒ x = y,

since we are restricting ourselves to only positive integers. Notice that being one-to-one is a
condition on the function and its domain and codomain1 .

Example 2.20. The function f : R → Z given by f (x) = bxc is not one-to-one, since

f (0) = f (0.5), and yet 0 6= 0.5.

Definition 2.21. We will say that a function f : A → B is onto (or surjective) if for every
b ∈ B, there exists an element a ∈ A such that f (a) = b. Equivalently, f : A → B is onto if
the range and codomain are equal: f (A) = B.

Note 2.21.1. Since we have f (A) ⊆ B for all functions f : A → B, we only need to show
that B ⊆ f (A) in order to prove that f is onto.

Example 2.22. The function f : R → R given by f (x) = 2x + 1 is onto. To see this, we

will show that R ⊆ f (R). We will pick an arbitrary element b ∈ B, and show that it must
be in f (R). Let b ∈ B. To show that b ∈ f (A), we will find an explicit element a ∈ R such
b−1
that f (a) = b. Note that f (a) = b if 2a + 1 = b, so given any b, we can take a = . This
2
shows B ⊆ f (A) (which in our case was R ⊆ f (R).

Example 2.23. The function f : Z → Z given by f (x) = 2x + 1 is not onto, since f (x) = 0
has no solutions.

Example 2.24. The function f : R → R given by f (x) = x2 is not onto since f (x) = −1
has no solutions.

Example 2.25. The function f : R → Z given by f (x) = bxc is onto since for every integer
k ∈ Z, we have f (k) = k, so that every integer is the image of some element in R.
1
This is slightly misleading, but it gets across the point succinctly. If I wanted to be more accurate, I
should say that a function is determined by the given rule y = f (x) along with its domain and codomain.

25
Definition 2.26. If f : A → B is both one-to-one and onto, we say that f : A → B is a
bijection (sometimes called a one-to-one correspondence).

Definition 2.27. Let A ⊆ R be any nonempty set. Define the identity function as

idA : A → A where idA (x) = x.

Then idA is a bijection from A to A (you should be able to prove this!). When the underlying
set A is clear from the context we write idA = id.

Proposition 2.28. Suppose f : A → B is a bijection, and g : B → C is a bijection. Then

(g ◦ f ) : A → C is a bijection.

Proof. Let h = g ◦ f . First we show that h : A → C is one-to-one. Let x, y ∈ A, and assume

h(x) = h(y). Then g(f (x)) = g(f (y)). Since g : B → C is one-to-one, and since we have
g(f (x)) = g(f (y)), it follows that f (x) = f (y). Finally since f : A → B is one-to-one, we
must have x = y. Hence h is one-to-one.
Next, we demonstrate that h is onto. Pick an arbitrary element x ∈ C. Since g is onto,
there exists b ∈ B such that g(b) = x. For this value b ∈ B, as f : A → B is onto, there
exists an element a ∈ A such that f (a) = b. Thus, we have h(a) = g(f (a)) = g(b) = c.
Hence h : A → C is onto.
Since h is both one-to-one and onto, h is a bijection.

Proposition 2.29. Let f : A → B be a bijection. Then there exists a function g : B → A

such that f ◦g = idB and g ◦f = idA . g is called the inverse of f (with respect to composition)
and is customarily written as f −1 .

Proof. Let f : A → B be the prescribed bijection. We define g : B → A via the following

rule: If f (a) = b, then g(b) = a. We need to show a few items here. First, we need to
show that g is actually both defined and well-defined. We know that g is defined since f is
onto: for all b ∈ B, there exists a ∈ A such that f (a) = b. Hence for all b ∈ B, there exists
a ∈ A such that g(b) = a. Moreover, g is well-defined since f is one-to-one. Suppose that
f (x) = f (y). Then x = y, since f is one-to-one. Writing this in terms of g, we just said that
if x = y, then g(x) = g(y). Thus g is well-defined.
Next we need to show that g is a bijection. First, suppose that g(x) = g(y) for some
x, y ∈ A. Notice that if f (a) = x and f (b) = y, then g(x) = a and g(y) = b. Since a = b
by assumption, then f (a) = f (b) since f is well defined. Thus, x = y, showing that g is
one-to-one. Finally to see that g is onto, pick a ∈ A. Since f : A → B is a function, then
there exists b ∈ B such that f (a) = b. Hence there exists b ∈ B such that g(b) = a, showing
g is onto. It follows that g : B → A is a bijection.
Finally, notice that if f (a) = b, then g(b) = a. Thus, for all a ∈ A, we have (g ◦ f )(a) =
g(f (a)) = g(b) = a, so that g ◦ f = idA . Similarly, for all x ∈ B if g(x) = y, then f (y) = x,
so that (f ◦ g)(x) = f (g(x)) = f (y) = x. Hence f ◦ g = idB .

Example 2.30. The function f : R → R given by f (x) = 2x + 1 is a bijection. Its inverse

x−1
is f −1 (x) = .
2
26
Example 2.31. The function f : Z → Z given by f (x) = 2x + 1 is one-to-one, but not onto,
so it is not a bijection.

Example 2.32. The function f : R → R given by f (x) = x2 is neither one-to-one nor onto.

Example 2.33. The function f : R → Z given by f (x) = bxc is onto, but not one-to-one,
so it is not a bijection.

Sometimes elementary calculus can helpful in showing that a function is one-to-one and
onto.

Example 2.34. 3 The function f : R → R given by f (x) = 2x3 + x is a bijection. To

show this, we need to show that f (x) is one-to-one and onto. To show it is one-to-one, we
show that it passes the horizontal line test since it is an increasing function. The function
is increasing on (−∞, ∞) since f 0 (x) = 6x2 + 1 > 0. To see that the function is onto, notice
that

lim (2x3 + x) = ∞.
x→∞

Recall precisely what it means for lim f (x) = ∞: For all y ∈ R, there exists t ∈ R so that
x→∞
f (x) > y for all x > t. Likewise we have

lim (2x3 + x) = −∞.

x→−∞

Thus in our case for all b ∈ R, there exists t > 0 so that 2x3 + x > b for all x > t and
2x3 + x < b for all x < −t. Since f (x) is continuous (as it is a polynomial), the intermediate
value theorem implies that there exists a ∈ [−t, t] where f (a) = b. Since b is arbitrary, the
function is onto. Notice that we did not need to explicitly solve the equation 2a3 + a = b for
a in order to demonstrate surjectivity. Moreover this technique can be used on any function
that is continuous on its domain and which tends to ∞ and −∞ on its domain.


Definition 2.35. The graph of f : A → B is the set of order pairs x, f (x) : x ∈ A .

Example 2.36. Consider f : N → N is given by f (x) = x2 , then

Graph(f ) = {(0, 0); (1, 1); (2, 4); (3, 9); . . . }.

Note 2.36.1. Be careful with notations as we have used the −1 superscript in many different
ways. First, if x ∈ (0, ∞), then x−1 = x1 is the multiplicative inverse. If f : A → B is a
bijection, then f −1 : B → A is the inverse function of f with respect to compostion. Finally,
even if f : A → B is not a bijection, the inverse image f −1 (D) is still defined for sets D ⊆ B.

27
2.2.1 Sequences and Series
A sequence is a function whose domain is a subset of N. Instead of writing f (0) or f (1), we
usually just write f (0) = a0 , f (1) = a1 , and so on. Thus we can think of a sequence as an
ordered list of elements:

∞
ak k=0 = (a0 , a1 , a2 , . . . ).

Typically ai ∈ R, but the images can be any object, and sequences may be finite or infinite.
A series is simply a sum of the elements in a sequence, assuming that it makes sense to add
the elements in a sequence.
∞
X
ak = a0 + a1 + a2 + . . . .
k=0

By convention the empty sum is

X
x = 0.
x∈∅

We will occasionally use product notation:

∞
Y
ak = a1 · a2 · a3 · . . . .
k=1

n
Y
For example we could have defined the factorial as n! = k. Additionally, we could write
k=1

n
Y
2n = 2.
i=1

By convention the empty product is

Y
x = 1.
x∈∅

28
2.3 Cardinality
Consider finite sets A and B with say |A| = 3 and |B| = 2. Notice that no function from A
to B can be one-to-one. Likewise, no function from B to A can be onto.

Thus for finite sets we have the following.

Proposition 2.37. Let A and B be finite sets. Then there exists a surjection (onto function)
f : A → B if and only if |A| > |B|. Likewise there exists an injection f : A → B if and only
if |A| 6 |B|. Thus, there exists a bijection f : A → B if and only if |A| = |B|.
Proof. Exercise.
This will be our main motivation for the following definition:
Definition 2.38. Let A and B be two (possibly infinite) sets. Then we say that A and B
have the same cardinality if and inly if there exists a bijection f : A → B.
Before we wade too deeply into this topic, let’s consider a preliminary example.
Example 2.39 (Hilbert’s Hotel). Before we get into technical details, it is helpful to think
about how infinity works (and how it doesn’t work). In class, we talked about Hilbert’s hotel,
which is a famous example of the German mathematician David Hilbert. I have included a
link for Hilbert’s Hotel ([Link] which will more
easily be explained via video. The moral of the story: Infinity is weird!. Also, please
note that infinity is NOT a number, so we should not expect it to behave like a number.
We will say that a set X is finite if it contains a finite number of elements. We will say
that a set X is countable if there exists a bijection f : X → Z+ . It turns out that if there
exists a one-to-one function f1 : A → B, and if there exists another one-to-one function
f2 : B → A, then there must exist a bijection f : A → B. This statement is called the
Schröder-Bernstein Theorem, and even if it sounds obvious, it is rather tricky!
Example 2.40. Show that the set X = {2, 4, 6, 8, 10, . . . } of even positive integers is count-
able. That is, construct a bijection f : X → Z+ .

29
Proof. Notice that the function f (x) = x/2 is a bijection between the two sets. The function
is one-to-one since:

f (x) = f (y) =⇒ x/2 = y/2 =⇒ x = y.

The function is onto since for every positive integer k ∈ Z+ , we have f (2k) = k. That is,
every positive integer is in the range of the function. Therefore, f (x) = x/2 is a bijection,
and the two sets have the same cardinality: |X| = |Z+ |.

Thus we can put the elements in X and the elements in Z+ in one-to-one correspondence:

X: 2 4 6 8 10 . . .
l l l l l
Z+ : 1 2 3 4 5 ...

In other words, since our function f (x) = x/2 is one-to-one, we know that every element
in Z+ gets counted at most once by an element in X. Likewise, since f (x) = x/2 was onto,
then every element in Z+ gets counted at least once by an element in X. These observations
together make it clear that every element in Z+ gets counted exactly once.

Proposition 2.41. The set of integers Z is countable.

Proof. Count the following way:

Z: 0 1 −1 2 −2 . . .
l l l l l
Z+ : 1 2 3 4 5 ...

Proposition 2.42. Prove that the set of positive rational numbers is countable.

Proof. Write down the positive rationals in the following infinite array:
1 1 1 1 1 1
1 2 3 4 5 6
...

2 2 2 2 2 2
1 2 3 4 5 6

3 3 3 3 3 3
1 2 3 4 5 6

4 4 4 4 4 4
1 2 3 4 5 6

5 5 5 5 5 5
1 2 3 4 5 6

6 6 6 6 6 6
1 2 3 4 5 6

.. ..
. .

30
If we count moving along diagonals, then we have put the positive rationals in one-to-one
correspondence with the positive integers, and hence the positive rationals are countable.
Note that if we skip the red entries, then we will create a bijection. However, counting along
the diagonals is sufficient as this creates a surjection which is all we need. This shows that
the set of rational numbers is at most countable.
Remark 2.43. How could we adapt the previous argument to show that the set of all rational
numbers is countable?
Proposition 2.44. Let A and B be sets which are at most countable (that is finite or
countable). Then A ∪ B and A × B are also at most countable.
Proof. Write A = {a1 , a2 , a3 , . . . } and B = {b1 , b2 , b3 , . . . }. First, note that if A and B are
finite, then so are A ∪ B and A × B. Next, if A or B are infinite, then so is A ∪ B and A × B.
We may assume that A and B are countable and that A ∩ B = ∅. Now,
A ∪ B = {a1 , b1 , a2 , b2 , a3 , b3 . . . }.
We leave it as an exercise to find an explicit bijection f : Z+ → A ∪ B. The Cartesian
Product of A and B can be written in an array
 

 (a1 , b1 ) (a1 , b2 ) (a1 , b3 ) (a1 , b4 ) . . . 

(a , b ) (a , b ) (a , b ) (a , b ) . . .

 

 2 1
 2 2 2 3 2 4 

(a3 , b1 ) (a3 , b2 ) (a3 , b3 ) (a3 , b4 ) . . .


 (a4 b1 ) (a4 , b2 ) (a4 , b3 ) (a4 , b4 ) . . . 


 .
.. .
.. .
.. .
.. ..  
 . 

We count similarly to the way we counted in Proposition 2.42.

Theorem 2.45 (Cantor, 1874). The interval [0, 1] is not countable.
Proof. (Cantor’s Diagonal Argument, 1891) This will be a proof by contradiction. Suppose
that the set of real numbers was countable. Then we could put the set in one-to-one cor-
respondence with the set of positive rationals. Say that we have enumerated the interval:
[0, 1] = (rn )n∈Z+ . We will construct a number not on this list showing that the enumeration
was not a one-to-one correspondence. Write out the decimal expansion of the list of real
numbers, where we use dij denote the j th decimal place of the ith term in the sequence.
r1 = 0.d11 d12 d13 d14 d15 . . .
r2 = 0.d21 d22 d23 d24 d25 . . .
r3 = 0.d31 d32 d33 d34 d35 . . .
r4 = 0.d41 d42 d43 d44 d45 . . .
r5 = 0.d51 d52 d53 d54 d55 . . .
..
.
Now, we construct the real number using the diagonal decimal digits:
D = 0.d11 d22 d33 d44 d55 . . .

31
D may still be on the list, so to be sure that we have constructed a number which is not on
the list, we will change each decimal of D in the following way. If dii = 4, then set ci = 5. If
dii 6= 4, then set ci = 4. Finally, consider the number

C = 0.c1 c2 c3 c4 c5 . . .

C is not in our list. Notice that C 6= r1 , since the numbers differ in the first digit. Likewise,
C 6= r2 , since the numbers differ in the second digit, and so on. This shows that C is not
on our list which means that our original enumeration could not have been a one-to-one
correspondence. We conclude that [0, 1] is uncountable.
Remark 2.46. Why does the previous proof not work for the rational numbers. That is, why
does the proof not show that the set of rational numbers is uncountable?
Example 2.47. Show that the interval (0, 1) and the interval (1, ∞) have the same cardi-
nality.
Proof. Let f (x) = x1 ...
Proposition 2.48. Every nonempty open interval (a, b) is uncountable.
Proof. Define f : (0, 1) → (a, b) by f (x) = bx + (1 − x)a...
Corollary 2.49. The set of irrational numbers is uncountable.
Proof. Assume for a contradiction that the set of irrationals was countable. Then

Q ∪ {irrational numbers} = R

would also be countable since the rationals are countable. However, we just showed that the
set of reals is uncountable. This is a contradiction and hence, this completes the proof.
Proposition 2.50. If A ⊆ B, then there exists a function f : A → B which is one-to-one.
Proof. Consider f : A → B given by f (a) = a. Then f is one-to-one as f (x) = f (y) =⇒
x = y, since f (x) = x and f (y) = y, for all x, y ∈ A.
Theorem 2.51 (Cantor’s Theorem - 1873). Let A be any set. Then there is no bijection
from A to its power set 2A .
Proof. Suppose for a contradiction that f : A → 2A is a bijection. In particular f must be
onto. Consider the set

E = {a ∈ A : a ∈
/ f (a)} ⊆ A.

Note that since E ⊆ A, then E ∈ 2A . Since f is onto, there exists x ∈ A with f (x) = E. We
consider two cases. If x ∈ E, then x is such that x ∈/ f (x), implying that x ∈
/ E, which is a
contradiction. If x ∈
/ E, then x ∈ f (x) so that x ∈ E, a contradiction. Thus in both cases we
have reached a contradiction, and we conclude our hypothesis is false. That is, f : A → 2A
must not be onto (and hence cannot be a bijection).

32
2.4 Exercises
Exercise 2.1. Let X = {f : R → (0, ∞)} be the set of functions mapping the real numbers
to the positive real numbers. Determine whether or not the following relations are equivalence
relations on X.
 
f (x)
(A) R = (f, g) ∈ X × X : lim =1
x→∞ g(x)

(B) R = {(f, g) ∈ X × X : f (0) = g(0)}

(C) R = {(f, g) ∈ X × X : f (0) = g(0) or f (1) = g(1)}

Exercise 2.2. Determine whether the following are equivalence relations. If so, prove it and
find the quotient sets of the relation. If not, what properties do they lack?

(A) R = {(x, y) ∈ Z × Z : x and y have the same parity}

(B) R = {(x, y) ∈ Z × Z : xy + 1 is even}

(C) R = {(x, y) ∈ R × R : x 6= y}

(D) R = {(x, y) ∈ R × R : bxc = byc}

(E) R = {(x, y) ∈ R × R : |x − y| 6 5}

(F) R = {(x, y) ∈ R × R : xy > 0}

(G) R = {(x, y) ∈ R × R : x 6 y}

Exercise 2.3. A serial relation R is one such that for all x ∈ A, there exists y ∈ A so that
(x, y) ∈ R. Find an example of an infinite relation which is serial. Find an example of an
infinite relation which is not serial.

Exercise 2.4. Prove that every serial, symmetric, transitive relation must also be reflexive.
Is this statement still true if we relax the hypothesis that R is serial?

Exercise 2.5. Let C[0, 1] denote the function space of continuous functions with domain
[0, 1]. Recall that every continuous function is integrable on its domain. Determine whether
the following relation is an equivalence relation:
 Z 1 Z 1 
R = (f, g) : C[0, 1] × C[0, 1] : f (x) dx = g(x) dx .
0 0

For Exercise 2.6: A bit-string of length n is a sequence of n 0s and 1s. For example 0010
is a bit-string of length four. Let Bn denote the set of bit strings of length n.

33
Exercise 2.6. Given x, y ∈ Bn , let DH (x, y) denote the Hamming distance of x and y, which
is defined as the number of components by which x and y differ. For example:

dH (011, 001) = 1 while dH (00101, 11100) = 3.

Let

R = {(x, y) ∈ Bn × Bn : dH (x, y) = 1}.

Determine whether R is reflexive, symmetric, or transitive.

Exercise 2.7. Let A 6= ∅, and consider the empty relation R = ∅ ⊆ A × A. Is R reflexive,
symmetric, or transitive?
Exercise 2.8. Prove Proposition 2.12.
Exercise 2.9. Prove Theorem 2.13.
Exercise 2.10. A poset (or partially ordered set) is a relation R which is reflexive, transitive,
and antisymmetric: (i.e., (x, y) ∈ R and (y, x) ∈ R implies x = y). Prove that the following
are posets:
(i) R = {(A, B) ∈ 2R × 2R : A ⊆ B}

(ii) R = {(x, y) ∈ R × R : x 6 y}
jnk lnm
Exercise 2.11. Prove that n = + for all n ∈ Z.
2 2
Exercise 2.12. Determine whether or not the given functions f : Z → Z are one-to-one or
onto (or neither or both). If they are one-to-one or onto, prove it. If they are not, explain
why not.
(A) f (x) = 2x + 3

(B) f (x) = |x| − 2

jxk
(C) f (x) =
2
(D) f (x) = x3 + 1
Exercise 2.13. Determine whether or not the functions f : Z × Z → Z are onto.
(A) f (m, n) = m2 − n2

(B) f (m, n) = m − n

(C) f (m, n) = m + n

(D) f (m, n) = |m| + |n|

(E) f (m, n) = mn − 1

34
 (F) f (m, n) = m2 − 1
 
m+n+3
(G) f (m, n) =
2
Exercise 2.14. Prove or disprove the following for all sets A and B and all function f .

(i) f (A ∪ B) = f (A) ∪ f (B)

(ii) f (A ∩ B) = f (A) ∩ f (B)

(iii) f −1 (A ∪ B) = f −1 (A) ∪ f −1 (B)

(iv) f −1 (A ∩ B) = f −1 (A) ∩ f −1 (B)

Exercise 2.15. Construct uncountable sets A and B such that A \ B is:

(A) finite

(B) countably infinite

(C) uncountable

Exercise 2.16. Suppose that A and B are countably infinite sets.

(A) Show that A ∪ B is countably infinite

(B) Show that A × B is countably infinite

Exercise 2.17. Suppose Ai is a countable set for each i = 1, 2, . . . .

(A) Prove that A1 ∪ · · · ∪ An is countable for each n > 1

(B) Prove that A1 × · · · × An is countable for each n > 1

∞
[
(C) Prove that Ai is countable
i=1

Hint: For parts (A) and (B), use Exercise 2.16.

Exercise 2.18. Let X = 2R be the power set of the real numbers R, and let

R = {(A, B) ∈ X × X : there exists a bijection f : A → B}.

(A) Show that R is an equivalence relation

(B) What are the equivalence classes of {1}, {1, 2, 4, 10}, Q, and [0, 1]?

35
36
Chapter 3

Logic and Proofs

3.1 Logic
A proposition is a statement that is either true or false (but not both). For example, “Today
is Tuesday” and “1 + 2 = 7” are propositions. We will use the letters p, q, r and s to denote
propositions. There are six main logical operators which we will discuss: ¬p denotes the
negation of p, and is read “not p.” We will use p ∧ q to denote “p and q.” We will write
p ∨ q to denote “p or q” (or possibly both p and q), and this is called the (inclusive) or.
The exclusive-or is denoted p ⊕ q and denotes p or q, but not both. The implication p → q
means that p implies q, or equivalently, q occurs whenever p occurs. Finally p ↔ q will
denote “p if and only if q.” We will properly define these logical operators using truth tables.
Truth tables are a convenient way to discuss the truth values of certain propositions. In our
truth tables, we will let 1 denote a true statement, and 0 will denote a false statement. For
example:

p ¬p
1 0
0 1

Likewise, we define:

p q p∧q p∨q p⊕q p→q p↔q

1 1 1 1 0 1 1
1 0 0 1 1 0 0
0 1 0 1 1 1 0
0 0 0 0 0 1 1

A few items might catch your attention here. First, notice that the implication p → q is
true if both p and q are true or if p is false. In other words, the implication p → q is false
only if p is true and q is false. Consider, for example, the statement “if x is even, then x + 1
is odd.” We all should agree that such a statement should be true regardless of whether x is

37
even ot odd. The implication p → q is of special importance to us as many math proofs are of
the form “if p then q.” In the implication p → q, p is called the hypothesis, and q is called the
conclusion. The converse of p → q is the compound proposition q → p. The contrapositive
of p → q is the compound proposition (¬q) → (¬p). The second item you should notice
is regarding the if-and-only-if operator (also called the biconditional operator). Notice that
the statement p ↔ q is true whenever p and q have the same truth values. Finally, an
explanation is due for the distinction between inclusive-or and exclusive-or. The inclusive-or
p ∨ q is true whenever at least one of p or q is true. The exclusive-or p ⊕ q is true whenever
exactly one of p or q is true. For example, consider that you are at your favorite restaurant,
and you are asked whether you want coffee or tea. This type of or would be in exclusive-or,
as the waiter is implying that you can have either tea or coffee, but not both. Next you are
asked whether you want cream or sugar. The implication here is that you can have cream or
sugar or possibly both. This type of or is an inclusive-or. Unless it is otherwise specified, you
should always assume that if you see the word “or” in a mathematical context, the author
intends the statement to be a statement using the inclusive-or.

Definition 3.1. We say that two compound propositions p and q are equivalent if they have
the same truth values. In that case we write p ≡ q.

Proposition 3.2. The implication p → q is equivalent to its contrapositive. That is,

(p → q) ≡ (¬q) → (¬p).


Proposition 3.3. The propositions p ↔ q and (p → q) ∧ (q → p) are equivalent. Further-
more,

¬(p ∨ q) ≡ (¬p) ∧ (¬q) (3.1.1)

¬(p ∧ q) ≡ (¬p) ∨ (¬q) (3.1.2)

The equivalences (3.1.1) and (3.1.2) will be collectively referred to as De Morgan’s Law.

Definition 3.4. A tautology is a proposition which is always true. A contradiction is a

proposition which is always false.

Note that the p ↔ q is a tautology if and only if p ≡ q, and r is a contradiction if and

only if ¬r is a tautology.

38
3.2 Structure of Proofs
We will utilize the truth tables from the previous section when we are discussing the structure
of mathematical proofs. Most mathematical statements are written using words (in full
sentences). Therefore, we will be making a shift to writing in full sentences. The following
quantifiers and symbols should only be used in informal settings and only if they
clarify the intended meaning of a statement.

Definition 3.5. The universal quantifier ∀ will be used to denote the phrase “for all.” The
existential quantifier ∃ will be used to denote “there exists.”

We will also be using the symbols “ =⇒ ” and “ ⇐⇒ ” to denote the words “implies” and
“if and only if,” respectively. We will frequently nest quantifiers, though we will need to be
very precise about the ordering. For example, let P (x, y) denote some proposition concerning
real numbers x and y. Then, ∀x∃yP (x, y) denotes the statement “for all real numbers x,
there exists a real number y, such that P (x, y) occurs.” On the other hand, ∃y∀xP (x, y)
denotes the statement “there exists a real number y such that for all real numbers x, P (x, y)
occurs.” These are two drastically different statements. The first says that we can pick any
x value we like, and once we have chosen that x value, we can find a value of y (possibly
depending on x) such that P (x, y) occurs. The second statement asserts that there exists
one particular y value such that P (x, y) occurs for all values x.
To make this more concrete, let P (x, y) denote the statement “x + y = 3.” Then, the
statement ∀x∃y(x + y = 3) is true, since we can pick any x value we like, and then once we
have chosen an x value, we can choose y = 3 − x, so that x + y = 3. However, the statement
∃y∀x(x + y = 3) is false. There is no y-value such that x + y = 3 for all x. To see this,
suppose that there were such a y-value, say y0 . If x + y0 = 3 for all real numbers x, then in
particular, x + y0 = 3 holds for x = 0 and x = 1. However, this is impossible since 0 + y0 = 3
implies y0 = 3, and 1 + y0 = 3 implies y0 = 2. No matter what value of y0 we initially
choose, we can find an x value such that x + y0 6= 3. The key difference in the statements
∀x∃yP (x, y) and ∃y∀xP (x, y) is the order in which x and y are chosen.

Proposition 3.6. We have the following equivalences:

¬(∀xP (x)) ≡ ∃x(¬P (x))

and

¬(∃xP (x)) ≡ ∀x(¬P (x))

Thus in order for the statement “for all x, P (x) occurs” to be false there must exist some
x where P (x) does not occur. Likewise in order for the statement “there exists an x such
that P (x) occurs” to be false, it must be that for every element x, P (x) does not occur.
Finally, to show that the statement ∀xP (x) is true, we must show that P (x) occurs for all
values x. To show that ∀xP (x) is a false statement, we must only demonstrate one example
where the property P (x) does not occur. A value x such that the statement “∀xP (x)” is
false is called a counterexample.

39
3.2.1 Primary Types of Proofs
Before we discuss the different types of proofs which we are most likely to encounter, we first
need some terminology. An axiom is a statement which is assumed to be true. A statement
which is able to be proven true is called a proposition. An important proposition is called a
theorem. A systematic deduction of a statement from axioms is called a proof. A lemma is a
theorem which plays a major role in the proof of another theorem. A corollary is a statement
which easily follows from another theorem. Finally, a conjecture is a statement which has
not yet been proven, but is widely believed to be true. Notice that all of these terms can be
subjective, so there is no hard line between a theorem and proposition, for example.

Definition 3.7. A direct proof refers to a proof of a statement of the form p → q wherein
we assume that p is true and demonstrate that q is true.

Definition 3.8. A proof via contraposition or a proof of the contrapositive of p → q is a

direct proof of the implication (¬q) → (¬p). That is, we assume that q is false and deduce
that p is false.

Definition 3.9. A proof by contradiction of a statement is a proof such that we assume

the statement to be false, and we derive some logical contradiction. This shows that the
statement must in fact be true.

Example 3.10. Show that if n is an even integer, then n2 is also even.

Proof. (Direct proof:) Assume that n is even. Then, there exists an integer k such that
n = 2k. It follows that n2 = 4k 2 = 2(2k 2 ) which is even as it is twice an integer.

Example 3.11. Show that if n2 is even, then n is even.

Proof. We will prove the contrapositive of the statement: If n is odd, then n2 is odd. How-
ever, this follows easily since if n is odd, then there exists an integer k so that n = 2k + 1.
Then, n2 = 4k 2 + 4k + 1 = 2(2k 2 + 2k) + 1, so that n2 is also odd.

Example 3.12. Show that if x + y > C, then either x > C/2 or y > C/2.

Proof. We will prove the contrapositive: If x < C2 and y < C2 , then x + y < C. This follows
immediately from adding the two inequalities: x + y < C2 + C2 = C.
√
Example 3.13. Prove that 2 is irrational.

Proof.
√ We will supply a proof by contradiction. Suppose to the contrary
√ that the real number
a
2 is rational. Then, there exists integers a and b 6= 0 such that 2 = b and we may assume
√ √
that ab is simplified. Now, 2 = ab implies that a = b 2, which after squaring both sides
shows that a2 = 2b2 . Therefore, a2 is even, which implies that a is even (see Example 3.11).
Since a is even, there exists an integer k such that a = 2k, and this shows that (2k)2 = 2b2 ,
so that b2 = 2k 2 which then shows that b2 is even, and hence b is even. However, this
is a contradiction since we assumed that √ a/b was reduced, and therefore a and b cannot
both be even. Since√the assumption that 2 is rational provides a contradiction, we have
demonstrated that 2 is irrational.

40
Other Types of Proofs
Example 3.14 (Proof by cases). Show that 2n 6 n2 for n = 2, 3, 4

Proof. When n = 2, we have 22 6 22 which is true. When n = 3 : 23 6 32 or 8 6 9 which is

true, and when n = 4, we have 24 6 42 which is true as 24 6 42 .

Example 3.15 (Without Loss of Generality (WLOG)). Show that if x and y are of opposite
parity (that is if one of the given numbers is even and the other is odd), then x + y is odd.

Proof. Suppose without loss of generality that x is odd and y is even. Then, there exist
integers k and ` such that x = 2k and y = 2` + 1. Then, x + y = 2k + 2` + 1 = 2(k + `) + 1
is odd.

Example 3.16 (Equivalence). Show that n is even if and only if 3n + 2 is even.

Proof. We will show both equivalences: If n is even, then 3n + 2 is even, and if 3n + 2 is even,
then n is even. We start by showing the forward implication, and we employ a direct proof.
Assume that n is even. Then, there exists an integer k such that n = 2k, and it follows that
3n + 2 = 3(2k) + 2 = 2(3k + 1) so that 3n + 2 is even. Now, we show the converse implication,
and for this we use a proof by contraposition. Suppose that n is odd. Then, there exists an
integer k such that n = 2k + 1, and this implies that 3n + 2 = 3(2k + 1) + 2 = 2(3k + 2) + 1,
so that 3n + 2 is odd.

Example 3.17. Show that the following are equivalent:

(i) n is an even integer

(ii) n + 3 is odd

(iii) n2 − 2 is even

Proof. Our proof consists of three parts:

• Step 1: (i) =⇒ (ii): Assume that n is even. Then there exists an integer k such that
n = 2k. This shows that n + 3 = 2k + 3 = 2(k + 1) + 1, so that n + 3 is odd.

• Step 2: (ii) =⇒ (iii): Suppose that n + 3 is odd. Then, there exists an integer k such
that n + 3 = 2k + 1, so n = 2k − 2. Hence, n2 − 2 = (2k − 2)2 − 2 = 4k 2 − 8k + 4 − 2 =
2(2k 2 − 4k + 1), which shows that n2 − 2 is even.

• Step 3: (iii) =⇒ (i) (Contraposition): Assume that n is odd. Then, there exists an
integer k so that n = 2k + 1, and hence n2 − 2 = (2k + 1)2 − 2 = 4k 2 + 4k + 1 − 2 =
4k 2 + 4k − 2 + 1 = 2(2k 2 + 2k − 1) + 1, so that n2 − 2 is odd. This completes our proof.

41
Example 3.18. Show that the following are equivalent:

(i) n is an even integer

(ii) n2 + 1 is odd

(iii) 3n + 2 is even

Proof. The structure of our proof will be different from the previous example since the
implication “n2 + 1 is odd implies 3n + 2 is even” is difficult to prove directly. However, it
is easy to see that items (ii) and (iii) are both equivalent to the fact that n is even, so we
will show (i) ⇐⇒ (ii) and (i) ⇐⇒ (iii). Our proof will consist of four parts:

• Step 1: (i) =⇒ (ii): Suppose that n is even. Then n = 2k for some integer k, and
hence n2 + 1 = 2(2k 2 ) + 1 is odd.

• Step 2: (ii) =⇒ (i) (Contrapositive): Suppose that n is odd. Then n = 2k + 1 for

some k, and hence n2 + 1 = 2(2k 2 + 2k + 1) is even.

• Step 3: (i) =⇒ (iii): Suppose that n is even. Then n = 2k for some integer k, and
hence 3n + 2 = 2(3k + 1) is even.

• Step 4: (iii) =⇒ (i) (Contrapositive): Suppose that n is odd. Then n = 2k + 1 for

some k, and hence 3n + 2 = 2(3k + 2) + 1 is odd.

As an alternative proof to the one above, we could show that n2 + 1 is odd if and only
if 3n + 2 is even by considering the two cases when n is odd and when n is even. We then
would aim to show that all the statements always have the same truth value. What if we
were only asked to show that n2 + 1 is odd if and only if 3n + 2 is even. What would be the
best way to proceed?

Example 3.19 (Existence, constructive). There exists an even integer which can be written
as the sum of two distinct primes in at least two separate ways.

Proof. For example, we can take 16 = 13 + 3 = 11 + 5.

Example 3.20 (Existence, nonconstructive). Show that there exist two irrational numbers
x and y such that xy is rational
√
√ 2 √ √ √2
Proof. (Nonconstructive) If 2
is rational, then we can take x√ = y = 2. If 2 is
√ √2
 √ 2
√ √ 2
irrational, then, we can take x = 2 and y = 2 as 2 = 2 which is rational.
Hence in either case we have found irrational numbers x and y such that xy is rational.

42
Example 3.21 (Uniqueness). Given any real number x, there exists a unique real number
y such that x + y = 0.

Proof. Uniqueness proofs have two parts. First, we must show existence. Then, we will
demonstrate uniqueness.

• Existence: Given any real x, we will take y = −x, and then x + (−x) = 0.

• Uniqueness: Suppose that y and z both satisfy x + y = 0 and x + z = 0. Then,

x + y = x + z =⇒ y = z which gives uniqueness.

Conjecture 3.22. The real number π + e is irrational.

Conjecture 3.23 (Collatz). Given a positive integer n, define:


n/2 n is even
f (n) =
3n + 1 n is odd

Then, regardless of the original input, every iterate of the function will eventually contain
the cycle 4 → 2 → 1. For example:

7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

43
3.3 Exercises
Exercise 3.1. Construct the truth table for the given compound propositions:

(A) p ∨ (¬q)

(B) p ∨ (p → q)

(C) (p ∧ q) ⊕ (p ∨ q)

(D) (p ∨ ¬r) ∧ (q ∨ r)

(E) r → (p → q)

(F) p → (q → r)

(G) (p → q) → r

Exercise 3.2. Find any compound proposition which would produce the following truth
table:

p q r ... ??
1 1 1 ... 1
1 1 0 ... 0
1 0 1 ... 1
1 0 0 ... 0
0 1 1 ... 1
0 1 0 ... 0
0 0 1 ... 0
0 0 0 ... 0

Exercise 3.3. Determine whether or not the following propositions are equivalent:

(A) (p ∨ q) ∨ (q ∧ r); (p → q) ∧ (¬r)

(B) p ↔ q; (¬p) ↔ (¬q)

(C) ¬(p → q); p ∨ (¬q)

Exercise 3.4. Determine whether or not the following propositions are tautologies:

(A) (p ∨ q) ⊕ (p ∧ q)
 
(B) (p → q) ∧ (q → p) → (p ↔ q)
 
(C) (p ∨ q) ∧ (¬p) → q

44
Exercise 3.5. Let Q(x) be the statement “x + 1 > 5x.” If the domain consists of all rational
numbers, what are these truth values?
(A) Q(0)

(B) Q(1/4)

(C) Q(−3)

(D) ∃x (Q(x))

(E) ∀x (Q(x))

(F) ∃x (¬Q(x))

(G) ∀x (¬Q(x))
Exercise 3.6. Determine the truth value of the following statements assuming the domain
is the set of real numbers:
(A) ∀x∀y(x + y = y + x)

(B) ∀x∃y(xy = 1)

(C) ∃x∀y(xy = 1)

(D) ∃x∀y(xy = 0)

(E) ∃x∃y(xy 6= yx)

(F) ∀x∃y(x2 = y)
Exercise 3.7. Determine the truth value of the following statements assuming the domain
is the set of positive real numbers
(A) ∀x∃y(xy > 2)

(B) ∃y∀x(xy 6 2)

(C) ∀x∀y(x2 > xy)

(D) ∃x∃y(x2 > xy)

(E) ∀x∃y(x + y = 2)

(F) ∃x∀y(x + y = 2)
Exercise 3.8. Write the negation of each of the following statements assuming the domain
is the set of positive real numbers
(A) ∀x∃y(xy > 2)

(B) ∃y∀x(xy 6 2)

45
 (C) ∀x∀y(x2 > xy)

(D) ∃x∃y(x2 > xy)

(E) ∀x∃y(x + y = 2)

(F) ∃x∀y(x + y = 2)

Exercise 3.9. Prove that the sum of two odd integers is an even integer.

Exercise 3.10. Let m, n, p be integers. Prove that if m + n and n + p are even integers,
then m − p is even.

Exercise 3.11. Prove that every odd integer can be written as a difference of two squares.

Exercise 3.12. Prove or disprove: The product of two rational numbers is rational.

Exercise 3.13. Prove or disprove: The product of two irrational numbers is irrational.

Exercise 3.14. Prove that if x and y are irrational, then either x + y is irrational or x − y
is irrational.

Exercise 3.15. Prove that if m, n are integers and mn is even, then either m or n is even.

Exercise 3.16. Prove that n is even if and only if n2 + 1 is odd.

Exercise 3.17. Prove that the following statements are equivalent for an integer n:

(A) n is even

(B) n2 + 10 is even

(C) 3n − 40 is even

Exercise 3.18. Prove or disprove: x is an irrational number if and only if 1/x is irrational.

Exercise 3.19. Prove or disprove: If x and y are rational numbers then xy is also rational.

Exercise 3.20. Prove that there are no integer solutions to the equation 2x2 + 5y 2 = 14.

Exercise 3.21. Prove that between every two distinct rational numbers is another rational
number. More precisely, suppose that x and y are rational with x < y. Prove that there
exists a rational number z with x < z < y.

Exercise 3.22. Prove that between every rational number and irrational number is an
irrational number.

Exercise 3.23. Prove that there exist integers x and y such that xy − y x = 1. Is your proof
constructive or nonconstructive?

46
Exercise 3.24. Let x, y ∈ R. Prove that max(x, y) + min(x, y) = x + y, where

x x>y
max(x, y) =
y y>x

and

y x>y
min(x, y) =
x x<y

Exercise 3.25 (Triangle-Inequality). Let x, y ∈ R. Prove that

|x + y| 6 |x| + |y|

47
48
Chapter 4

Number Theory

4.1 Basic Definitions and Examples

Throughout the section, we will be working with integers unless explicitly told otherwise.

Definition 4.1. Let a, b ∈ Z be integers. We say that a divides b (written a | b) if there

exists an integer k such that b = ak. Note that the phrases “a divides b”, “a is a factor of
b”, “a is a divisor of b”, and “b is a multiple of a” all denote the same relationship.

Proposition 4.2. The following statements hold:

(i) 1 | a for all a ∈ Z

(ii) a | a for all a ∈ Z

(iii) a | 0 for all a ∈ Z

(iv) 0 | a only for a = 0.

Proof. Exercise.

Proposition 4.3. Divisibility is transitive. That is if a | b and b | c, then a | c.

Proof. Exercise.

Proposition 4.4. Suppose that a | x and a | y. Then, a | (sx + ty) for all integers s and t.
In particular a | (x + y) and a | sx for all s ∈ Z.

Proof. Exercise.

Theorem 4.5 (Division Algorithm). Given any integer a ∈ Z and any positive integer
d ∈ Z+ , there exist unique integers q and r such that 0 6 r < d, and

a = dq + r.

49
Proof. Consider the set S = {a − dk : k ∈ Z and a − dk > 0}. First, note that S 6= ∅. If
a > 0, then a = a − 0 · k ∈ S. If a < 0, then a − ad = a(1 − d) ∈ S. Since S ⊆ N and
S 6= ∅, it follows that S has a smallest element, call it r = a − dq. Note that r > 0 as r ∈ S.
Furthermore if r > d, then r − d = a − (d + 1)q > 0, and hence r − d ∈ S, contradicting the
minimality of r. It is clear that r is unique as it is the smallest element of S. To see that q
is unique, note that if a − dq = r = a − dq 0 , then −dq = −dq 0 , which implies q = q 0 . This
gives uniqueness.
Definition 4.6. The quantities a, d, q, r in the preceding theorem have special names. The
integer a is the dividend, d is the divisor, q is the quotient, and r is the remainder.
Definition 4.7. Suppose that a = dq + r by the division algorithm. Then, we define two
functions:
a DIV d = q and a mod d = r.
Note that we can explicitly define a DIV d = b ad c and a mod d = a − d
a
d
.
Example 4.8. We have 100 DIV 3 = 33 and 100 MOD 3 = 1. What are
120 DIV 8 and 120 mod 8? What does it mean if a mod d = 0?
Definition 4.9 (Congruence modulo m). Given two integers a, b ∈ Z, and given an integer
m ∈ Z such that m > 2, we say that a is congruent to b modulo (or mod) m, written
a ≡ b (mod m)
if m | (a − b).
Note 4.9.1. Every time we write a ≡ b (mod m), we tacitly assume that m > 2.
Example 4.10. Sometimes this is called clock arithmetic:
16 ≡ 4 (mod 12), 21 ≡ 9 (mod 12),
and so on. These congruences follow since 12 | (16 − 4) and 12 | (21 − 9).
Example 4.11. Additional examples include
1200 ≡ 0 (mod 10), 100 ≡ 4 (mod 3), 41 ≡ −1 (mod 21),
which are true as 10 | (1200 − 0), 3 | (100 − 4), and 21 | (41 − (−1)), respectively. We could
technically write
10 = 100 (mod 90),
but an unwritten rule in the definition a ≡ b (mod m) states that we should make b as
simple as possible. Can you categorize all the integers x such that x ≡ 0 (mod 2)?
We next give two alternate ways of thinking about the relationship a ≡ b (mod m).
Proposition 4.12. Let a, b, m ∈ Z with m > 2. Then a ≡ b (mod m) if and only if
a = b + mk, for some k ∈ Z.
Proof. If a ≡ b (mod m), then m | (a − b), so that a − b = mk for some k ∈ Z. On the other
hand, if a = b + mk for some k ∈ Z, then, k = a−b
m
so that m | (a − b).

50
Proposition 4.13. We have a mod m = b mod m if and only if a ≡ b (mod m).
Proof. If a mod m = b mod m, then a and b have the same remainder when divided by
m. Since the remainder are the same, we can write a = mq + r and b = mn + r. Hence,
a − mq = b − mn, and thus a − b = m(q − n), so that m | (a − b), and hence a ≡ b (mod m).
On the other hand, suppose a ≡ b (mod m) so that m | (a−b). By the division algorithm,
write a = mq1 + r1 and b = mq2 + r2 , where 0 6 r1 , r2 < m. We need to show that r1 = r2 .
Now,
a − b = m(q1 − q2 ) + r1 − r2 =⇒ a − b − m(q1 − q2 ) = r1 − r2 .
Since m | (a − b) by assumption, and since m | m(q1 − q2 ), it follows that m | r1 − r2 as well.
Finally, notice that since 0 6 r1 , r2 < m, then −m < r1 − r2 < m. The only integer between
−m and m that is a multiple of m is zero, so it follows that r1 − r2 = 0, or r1 = r2 .

Proposition 4.14. Suppose that a ≡ b (mod m) and c ≡ d (mod m) where a, b, c, d, m ∈ Z

with m > 2. Then,
(i) a + c ≡ b + d (mod m)
(ii) ac ≡ bd (mod m)
(iii) a ≡ b (mod m) =⇒ an ≡ bn (mod m) for all nonnegative integers n.
Proof. Exercise.
Example 4.15. Congruence notation is very nice, and it immediately makes some number
theory proofs quite easy. For example, suppose that we wanted to show that 5n − 2n is a
multiple of 3 for all nonnegative integers n. We could use induction, but with all we know
regarding congruences, this problem becomes trivial:
5≡2 (mod 3) =⇒ 5n ≡ 2n (mod 3) for all nonnegative integers n,
and hence 3 | 5n − 2n for all n ∈ N.
Example 4.16. A few other tricks are quite useful. For example, why is 202 ≡ 1 (mod 21)?
Well since 20 ≡ −1 (mod 21), it follows that 202 ≡ (−1)2 ≡ 1 (mod 21).
Note 4.16.1. One word of caution is necessary here. We have used that a ≡ b =⇒ an ≡ bn
for all n. However, it is not true that a ≡ b (mod m) =⇒ na ≡ nb (mod m). Try to find a
counterexample that demonstrates that this congruence indeed does not hold for all n.
Example 4.17. Suppose that we want to find all the integer solutions to the Diophantine
equation
x2 − 4y 2 = 23.
Suppose that there exists a solution (x0 , y0 ) so that x20 − 4y02 = 23. Since the equation holds
over the integers, it must also hold over the integers mod 4 (why?). However,
−4y 2 ≡ 0 (mod 4), since − 4 ≡ 0 (mod 4).

51
This means that the solution must satisfy x20 ≡ 3 (mod 4). But, you can check that if you
square any integer and take the remainder mod 4, the only possible values you can obtain
are 0 and 1. Hence, the congruence x20 ≡ 3 (mod 4) has no solutions, and therefore the
equation x2 − 4y 2 = 23 has no integral solutions. When using this technique, we say that
the equation “fails mod 4”.

Definition 4.18. We next define two operations +m and ·m . Given any two integers a and
b, define

a ⊕m b = (a + b) mod m

and

a m b = ab mod m

Definition 4.19. We define Z/mZ = {0, 1, 2, . . . , m−1} equipped with the operations above
⊕m and m . This set is called the ring of integers modulo m, and it will play a special role
in the theory of abstract algebra. When p is a prime, the set Z/pZ is what is called a finite
field, and thus it is often denoted as Fp . The set Fp together with the operations ⊕p and ⊗p
is called the finite field of order p.

4.2 Primes and Euclid’s Algorithm

Definition 4.20. An integer n > 2 is said to be composite if there exists integers a, b such
that 2 6 a, b 6 n − 1. If no such a and b exist (that is, if the only positive divisors of n are
1 and itself), then we say n is prime.

The first few primes are:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, . . .

We will typically use p to denote a prime. We can think of the primes as the building blocks
of the integers.

Theorem 4.21. Every integer n > 2 is either prime or a unique1 product of primes.

Proof. The proof will proceed by (strong) induction. First, the statement holds for n = 2,
since 2 is a prime. Next, suppose that the statement holds for all integers n such that
2 6 n 6 k, for some k > 2. Then, we will show the statement also holds for k + 1. Now, we
have two cases. If k + 1 is a prime, then we are done. If k + 1 is a composite integer, then
there exists integers a, b such that 2 6 a, b 6 k and k + 1 = ab. By our inductive hypothesis,
the fundamental theorem holds for both a and b, so that a and b are either prime or a unique
product of primes, and hence the same is true for ab.
1
By unique we mean that given an integer n > 2, there is exactly one way to write n as a product of
primes up the the trivial reordering of the divisors. For example 15 = 3 · 5 = 5 · 3, but 3 and 5 are the unique
prime factors of 15.

52
Proposition√ 4.22. If n is a composite integer, then n has a prime factor which is less than
or equal to n.
√ √
Proof. This proof relies on the fact that if ab = n, then either a 6 n or b 6 n, and we
proved this in Chapter 1 (you should reprove this if necessary). Now, if n is composite, then
√
we can write n = ab, where 1 < a 6 b < n. By the comment above √ we must have a 6 n.
Let p be the smallest prime factor of a, and note that p 6 a 6 n.

Using the previous fact, we could construct an algorithm

√ which could determine whether
not n is prime by checking all the prime numbers up to n. This process or algorithm is
called the Sieve of Eratosthenes.

Example 4.23. Show that 97 is a prime.

Theorem 4.24 (Euclid). There are infinitely many primes.

(Proof by Contradiction, often incorrectly attributed to Euclid). Suppose that there are only
finitely many primes p1 , . . . , pn for some n. Let Q = p1 p2 . . . pn + 1, and note that pi - Q for
all i (why is this?), which violates the Fundamental Theorem of Arithmetic. Hence, either Q
is a prime, or Q is a product of primes not in the list p1 , . . . , pn , contradicting our assumption
that the only primes were p1 . . . , pn .

Now that we know that there are infinitely many primes, it makes sense to ask how many
primes are there up to a given number. For example, how many primes are there less than
10? How many primes are less than 100? Less than 1000? While this is difficult to answer
directly, we do know how many primes there are up to a given number in an approximate
sense:

Theorem 4.25 (Prime Number Theorem). Let π(x) denote the number of primes that are
less than or equal to x. For example, π(3) = 2, π(10) = 4, π(50) = 15, . . . . Then,

π(x)
lim = 1.
x→∞ x/ ln x

Since the Prime Number Theorem describes an asymptotic bound, then the approxi-
mation x/ ln x for the number of primes 6 x gets better as the value of x get larger. For
example,

π(100)
= 1.1513 . . .
100/ ln(100)

while

π(10, 000, 000)

= 1.0712 . . . .
10, 000, 000/ ln(10, 000, 000)

53
4.2.1 Greatest Common Divisors
Definition 4.26. Suppose that a, b are nonnegative integers, with a and b not both zero.
Then the greatest common integer which is a divisor of both a and b is called the greatest
common divisor of a and b, and is denoted by gcd(a, b).

Example 4.27.

• gcd(36, 48) = 12

• gcd(100, 29) = 1

• gcd(26 52 73 , 28 32 72 ) = 26 72

• gcd(0, b) = b for b 6= 0

Why is gcd(0, 0) undefined?

Definition 4.28. The integers a and b are called relatively prime or coprime if gcd(a, b) = 1.
The integers a1 , a2 , . . . , an are called pairwise relatively prime if gcd(ai , aj ) = 1 for all i 6= j.

Example 4.29. The integers 100 and 29 are relatively prime since gcd(100, 29) = 1. The
integers 10, 11, 12 are not pairwise relatively prime despite the fact that gcd(10, 11, 12) = 1,
since gcd(10, 12) 6= 1. The integers 8, 27, 50 are pairwise relatively prime since gcd(8, 27) =
gcd(8, 50) = gcd(27, 50) = 1.

Note 4.29.1. The notion of greatest common divisor can be extended to more than two
integers in the obvious way: gcd(a1 , . . . , an ) denotes the largest common divisor of a1 , . . . , an .

Definition 4.30. Let a and b be two positive integers. The smallest positive common
multiple of a and b is called the least common multiple of a and b and is denoted lcm(a, b).

Example 4.31.

• lcm(10, 91) = 910

• lcm(10, 18) = 90

• lcm(26 52 73 , 28 32 72 ) = 28 32 52 73

Proposition 4.32. Let a, b ∈ Z+ , and write a = pα1 1 . . . pαnn and b = pβ1 1 . . . pβnn . Then,
min(α1 ,β1 )
gcd(pα1 1 . . . pαnn , pβ1 1 . . . pβnn ) = p1 . . . pnmin(αn ,βn )

and
max(α1 ,β1 )
lcm(a, b) = p1 . . . pnmax(αn ,βn ) .

In particular, gcd(a, b) · lcm(a, b) = a · b.

Proof. Exercise.

54
Proposition 4.33. Let a = dq + r. Then, gcd(a, d) = gcd(d, r).
Proof. We will show the slightly stronger statement that the set of common divisors of a
and d and the set of common divisors of d and r are exactly the same set. In particular,
the largest element in each set is identical also. Now, suppose that x | a and x | d. Then,
x | (a − qd), so that x | r as well. Hence, any common divisor of a and d is also a common
divisor of d and r. Finally, suppose that x | d and x | r. Then, x | (dq + r), so that x | a.
Hence, any common divisor of d and r is also a common divisor of a and d.
Algorithm 4.34 (Euclidean Algorithm). Suppose that we want to find gcd(a, d), where
a > d. Then, we apply the following procedure.
(A) Write a = r0 and d = r1 .

(B) Repeatedly apply the Division Algorithm to get

r0 = r1 q1 + r2 0 6 r2 < r1
r1 = r2 q2 + r3 0 6 r3 < r2
..
.
rn−1 = rn qn + rn+1 0 6 rn+1 < rn
rn = rn+1 qn+1

The process terminates when rn+1 | rn (i.e., when rn+2 = 0).

(C) Conclude gcd(a, b) = rn+1 .

Proof. Exercise. Hint: Apply the previous Proposition (You should at least be able to justify
why this process terminates).
Definition 4.35. Given a, b ∈ Z, a linear combination of a and b is a quantity of the form
ax + by where x, y ∈ Z.
Theorem 4.36 (Bézout’s Little Theorem). Suppose that a and b are positive integers. Then,
we can write gcd(a, b) as a linear combination of a and b. Furthermore, gcd(a, b) is the
smallest positive integer with this property. That is, if 0 < c < gcd(a, b), then the integer c
cannot be written as a linear combination of a and b.
Proof. That gcd(a, b) can be written as a a linear combination of a and b follows from
Euclid’s algorithm. Suppose that a = dq1 + r2 ; . . . ; rn−1 = rn qn + rn+1 , so gcd(a, b) = rn+1
Then backwards substituting rn+1 = rn−1 −rn qn = rn−1 −(rn−2 −rn−1 qn−1 )qn = · · · = ax+by.
Now suppose that d := gcd(a, b) > 1, and let 0 < c < d, and suppose for a contradiction
that there exist integers x and y such that c = ax + by. Since gcd(a, b) = d, then d | a and
d | b, and there exist integers k, ` such that a = dk and b = d`. Thus

c = ax + by = dkx + d`y = d(kx + `y).

Notice that the right-hand side is a multiple of d, and yet c is not as 0 < c < d. This is a
contradiction.

55
Definition 4.37. When we write gcd(a, b) = ax + by, we call x and y the Bézout coefficients
of a and b.
Example 4.38. Write gcd(11, 51) as as a linear combination of 11 and 51.
First, we apply Euclidean algorithm to 11 and 51 (we will see the reasons for this below).
51 = 11 · 4 + 7
11 = 7 · 1 + 4
7=4·1+3
4=3·1+1
3=1·3
so that gcd(11, 51) = 1. Now, we take the remainders from the Euclidean algorithm, and we
work backwards
1 = 4 − 3 · 1 =⇒ 1 = 4 − (7 − 4) = 2 · 4 − 7
=⇒ 1 = 2 · (11 − 7) − 7 = 2 · 11 − 3 · 7
=⇒ 1 = 2 · 11 − 3(51 − 11 · 4) = 14 · 11 − 3 · 51
Bézout coefficients are not unique. For example, we could also write 1 = 65 · 11 − 14 · 51.
Example 4.39. Write gcd(33, 48) as a linear combination of 33 and 48. We will apply the
same steps as before. First, apply the Euclidean algorithm:
48 = 33 · 1 + 15
33 = 15 · 2 + 3
15 = 3 · 5,
so that gcd(33, 48) = 3. Now, we work backwards:
3 = 33 − 15 · 2 =⇒ 3 = 33 − (48 − 33) · 2
=⇒ 3 = 3 · 33 − 2 · 48.
Example 4.40. Write gcd(1000, 81) as a linear combination of 1000 and 81. As before:
1000 = 81 · 12 + 28
81 = 28 · 2 + 25
28 = 25 · 1 + 3
25 = 3 · 8 + 1
3 = 1 · 3,
so that gcd(1000, 81) = 1. Now,
1 = 25 − 8 · 3 =⇒ 1 = 25 − 8 · (28 − 25) = 9 · 25 − 8 · 28
=⇒ 1 = 9 · (81 − 28 · 2) − 8 · 28 = 9 · 81 − 26 · 28
=⇒ 1 = 9 · 81 − 26 · (1000 − 81 · 12) = 9 · 81 − 26 · 1000 + 312 · 81
=⇒ 1 = 321 · 81 − 26 · 1000

56
Lemma 4.41 (Euclid’s Lemma). Suppose that p is a prime and p | ab. Then p | a or p | b

Proof. Assume that p | ab and p - a. We will show that p | bs. Since p | ab, there exists
k ∈ Z such that ab = pk. Also, since gcd(a, p) = 1, then by Bézout’s Little Theorem, there
exist integers x, y ∈ Z such that 1 = ax + py. Multiplying both sides by b yields

1 = ax + py =⇒ b = abx + bpy
=⇒ b = pkx + bpy
=⇒ b = p(kx + by),

and hence p | b.
Euclid’s Lemma can be extended to composites as well.

Proposition 4.42. Suppose that a | bc and gcd(a, b) = 1. Then a | c.

Proof. Exercise

Corollary 4.43. If ac ≡ bc (mod m), and gcd(c, m) = 1, then a ≡ b (mod m).

Proof. By definition:

ac ≡ bc (mod m) =⇒ m | (ac − bc) =⇒ m | c(a − b),

since gcd(m, c) = 1, by the previous proposition, we have m | (a − b), so a ≡ b (mod m).

Theorem 4.44 (Rational Root Theorem). Let f (x) = cn xn + cn−1 xn−1 + · · · + c1 x + c0 be

a polynomial of degree n with integer coefficients c0 , . . . , cn satisfying c0 6= 0. If f (x) has a
rational root ab , then a | c0 and b | cn .

Proof. Exercise.
√ √
Example 4.45. Prove that 3 is irrational. Suppose that 3 is rational, so that f (x) =
x2 − 3 has a rational root ab . By the rational root theorem, a | (−3) and b | 1. Thus
±3
the only possible solutions would be ab = ±1 = ±3 and ab = ±1±1
= ±1. Since none of
2
f (−3),√f (−1), f (1), f (3) are zero it follows that f (x) = x − 3 has no rational root, and
hence 3 is irrational.

57
4.2.2 Linear Congruences
Suppose that we want to solve the linear congruence 4x ≡ 16 (mod 20). In other words, we
want to know what are the values of x that make the congruence true? How many solutions
are there to this congruence, if any? How do we systematically go about finding such a
solution. The first way we could do this would be to just check the 20 different values (since
we’re working mod 20). However, this approach is clearly unwieldy if the value 20 were to
increase even slightly, so we should be more systematic here. We start with a few definitions.
Definition 4.46. We say that the integer a ∈ Z has an inverse (mod m) if there is a
solution to the congruence
ax ≡ 1 (mod m).
The solution x is called the inverse of a (mod m) and will be denoted by a−1 (mod m).
Proposition 4.47. If gcd(a, m) = 1, then there exists a unique inverse of a. If gcd(a, m) 6=
1, then no such inverse exists.
Proof. In addition to proving that such an inverse exists, we demonstrate a systematic
method we can use to find such an inverse. Since gcd(a, m) = 1, we can write ax + my = 1
for some x, y ∈ Z. Since every integer is congruent to itself mod m (for any m), we can write
1 ≡ (ax + my) (mod m) =⇒ 1 ≡ ax (mod m),
so that a−1 ≡ x (mod m). When gcd(a, m) = 1, it remains to show that this inverse is
unique mod m, but this follows immediately from Corollary 4.43. Indeed, suppose that the
inverse were not unique. That is, suppose that we have two values b and c such that ab ≡ 1
(mod m) and ac ≡ 1 (mod m). In particular, ab ≡ ac (mod m). Since gcd(a, m) = 1,
we conclude b ≡ c (mod m). We leave the proof of the fact that a−1 does not exist when
gcd(a, m) > 1 as an exercise (Hint: use Bézout’s Theorem!)
Example 4.48. Solve the congruence 3x = 2 (mod 100).

Solution: First, we find 3−1 (mod 100). We need the Bézout coefficients, so we apply
the Euclidean algorithm:
100 = 3 · 33 + 1
3=1·3
Hence,
1 ≡ 100 − 33 · 3 (mod 100)
≡ −33 · 3 (mod 100)
so that 3−1 ≡ −33 (mod 100) which simplifies to 3−1 ≡ 67 (mod 100). Hence,
3x = 2 (mod 100) =⇒ 67 · 3x ≡ 67 · 2 (mod 100)
=⇒ x ≡ 134 (mod 100)
=⇒ x ≡ 34 (mod 100)

58
Example 4.49. Solve the congruence 8x ≡ 101 (mod 103).

Solution: We have

103 = 8 · 12 + 7
8=7·1+1
7=1·7

Hence,

1=8−7
= 8 − (103 − 8 · 12) = 13 · 8 − 103

Then, 8−1 ≡ 13 (mod 103). Finally,

8x ≡ 101 (mod 103) =⇒ 13 · 8x ≡ 13 · 101 (mod 103)

=⇒ x ≡ 13 · 101 (mod 103)
=⇒ x ≡ 13 · (−2) (mod 103)
=⇒ x ≡ −26 (mod 103)
=⇒ x ≡ 77 (mod 103)

Example 4.50. Solve the equation 11x ≡ 17 (mod 201).

Solution: As before,

201 = 11 · 18 + 3
11 = 3 · 3 + 2
3=2·1+1

Thus,

1=3−2
= 3 − (11 − 3 · 3) = 4 · 3 − 11
= 4 · (201 − 11 · 18) − 11 = 4 · 201 − 73 · 11

Hence, 11−1 ≡ −73 (mod 201). Finally,

11x ≡ 17 (mod 201) =⇒ −73 · 11x ≡ −73 · 17 (mod 201)

=⇒ x ≡ −1241 (mod 201)
=⇒ x ≡ 166 (mod 201).

Note 4.50.1. In the preceding proposition, we showed that ax ≡ b (mod m) has a unique
solution mod m if gcd(a, m) = 1. So what happens when gcd(a, m) > 1? In this case, there
may be no solutions, and there may in fact be multiple solutions. For example:

2x ≡ 4 (mod 8)

59
has two solutions (x ≡ 2 (mod 8) and x ≡ 6 (mod 8)), while

2x ≡ 3 (mod 8)

has no solutions. What happens in general when gcd(a, m) > 1? As a hint, count the number
of solutions to the congruence ax ≡ b (mod m), and compare the number of solutions to
gcd(a, m). Can you prove what happens in general?

Finally, we discuss solving systems of linear congruences.

Proposition 4.51 (Chinese Remainder Theorem, Version 1). Let m and n be positive rela-
tively prime integers. Then

a ≡ b (mod mn)

if and only if both

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

Proof. Let gcd(m, n) = 1. Suppose that a ≡ b (mod mn). Then mn | (a − b) implies

m | (a − b) and n | (a − b) as m and n divide mn, and hence a ≡ b (mod m) and a ≡ b
(mod n). For the converse statement, assume that a ≡ b (mod m) and a ≡ b (mod n). Then
there exists k ∈ Z such that a = mk + b. Hence mk ≡ 0 (mod n). Since gcd(m, n) = 1, it
follows that k ≡ 0 (mod n) (See Exercise 4.18). Thus, n | k so there exists ` ∈ Z such that
k = `n. Finally, we see that a − b = mk = m`n, so it follows that a ≡ b (mod mn).
Proposition 4.52 (Chinese Remainder Theorem, Version 2). Suppose that m and n are
relatively prime integers both of which are all at least 2. Given a, b ∈ Z, the system

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

has a unique solution (mod mn).

Proof. Assume that x ≡ a (mod m) and x ≡ b (mod n). Then there exists k ∈ Z such that
x = mk + a. Hence, mk + a ≡ b (mod n), or mk ≡ (b − a) (mod n). Since gcd(m, n) = 1,
we know that there exists m−1 (mod n). Thus we must have k ≡ m−1 (b − a) (mod n). It
follows that there exists ` ∈ Z such that k = n` + m−1 (b − a). Therefore,

x = mk + a
= m(m−1 (b − a) + n`) + a
= mm−1 (b − a) + mn` + a.

We finally check that such an integer x satisfies both congruences:

x ≡ mm−1 (b − a) + mn` + a (mod m)

≡ a (mod m)

60
and

x ≡ mm−1 (b − a) + mn` + a (mod n)

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

Example 4.53. Suppose we want to solve the system

x ≡ 5 (mod 10)
x ≡ 17 (mod 21).

One way to find the solution involves a guess and check procedure: We know that x ≡ 17
(mod 21), so we can just look for integers congruent to 17 mod 21 until we find one also
congruent to 5 mod 10. For example the integers

17, 38, 59, 80, 101, 122, 143, 164, 185

are all congruent to 17 (mod 21). Since 185 ≡ 5 (mod 10), we can stop our search, so that
x ≡ 185 (mod 210) is our solution.
Example 4.54. Solve the following linear system:

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

Example 4.55. Solve the system

x ≡ 3 (mod 4)
x ≡ 1 (mod 5)
x ≡ 10 (mod 11)

Definition 4.56. We define the function ϕ : Z+ → Z+ as

ϕ(n) = |{x ∈ Z+ : x 6 n and gcd(x, n) = 1}|.

That is, ϕ(n) is the number of positive integers 6 n that are relatively prime with n. This
function is called Euler’s totient function.
Example 4.57. ϕ(10) = 4 since 1, 3, 7, and 9 are all relatively prime with 10. ϕ(7) = 6,
since 1, 2, 3, 4, 5, and 6 are relatively prime with 7. ϕ(p) = p − 1 if and only if p is prime.
Since gcd(1, 1) = 1, we also put ϕ(1) = 1.
Theorem 4.58 (Euler’s Theorem). Suppose that gcd(a, n) = 1. Then,

aϕ(n) ≡ 1 (mod n).

61
Example 4.59. Suppose n = 10 and a = 7. Then,

aϕ(n) = 74 = 2401 ≡ 1 (mod 10).

Corollary 4.60 (Fermat’s Little Theorem). For all a ∈ Z and for all primes p, we have

ap ≡ a (mod p).

Proof. If gcd(a, p) = 1, and since ϕ(p) = p − 1 for any prime p, Euler’s theorem implies that

aϕ(p) = ap−1 ≡ 1 (mod p).

Multiplying both sides by a gives the result. On the other hand if gcd(a, p) 6= 1, then
gcd(a, p) = p, and hence

ap ≡ 0 ≡ a (mod p).

In all cases, the result holds.

We will use these results in our next section regarding cryptography.

62
4.2.3 Cryptography
∗ This section of material is optional and will only be covered if time permits. For a de-
tailed and very well-written history and description of cryptography, see “Introduction to
Cryptography with Coding Theory,” by Trappe and Washington.

Cryptography is one of the many applications of number theory. Cryptography goes back
at least to the times of Julius Caesar and was particularly useful in both world wars. Today,
cryptography is used in the encryption of data including credit card use, online banking,
password storage, and so on. The classic setup is that a person named Alice wants to
send Bob a message. There is a possibility that an encrypted code could be intercepted or
tampered with by a middleman named Oscar.
We discuss a few of the basic ciphers including what was used in World War I by Britain
and Germany. At the end we discuss the modern day ciphers used including RSA and the
theory of Public Key Cryptography. In what follows, the plaintext refers to the message
which is to be encoded, the key refers to the method used to encrypt the data, and the
ciphertext refers to the encrypted data.

Private Key Encryption

Private Key Encryption is when two parties meet before hand and decide on how they will
encrypt and decrypt a message. This method has the disadvantages that the two parties must
meet prior to exchanging information, and they must trust each other. If one party shares the
encryption cipher with someone else, then all of the encrypted data has been compromised.
This has the advantage, however, that data is easy and inexpensive to encrypt. Since the
encryption and decryption methods are basically inverse operations of one another, such
encryption systems are frequently called symmetric key methods. Traditionally, each letter
is assigned a number:

A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Shift and Affine Ciphers

The oldest known such cipher is simply called the shift cipher or the Caesar cipher. Though
simple, this cipher was apparently effective at the time. The cipher here was simply trans-
lated a certain number of units and then the message was decoded by shifting the letters
back. The invertible map applied to the data was the map f (x) = x + k MOD 26, and
then to decipher the data once simply applied the map f −1 (x) = x − k mod 26 to the data.
Typically, one removes spacing between words to increase security. Julius Caesar used k = 3.
The shift cipher is easy to break for multiple reasons. First, there are only 26 possible
keys, so a brute force search is very reasonable here. Furthermore, if the message is not
short, there is typically only one possible message that could be encrypted.

63
 One level of sophistication higher than the shift cipher is the affine cipher. For any α ∈ Z
such that gcd(α, 26) = 1, the map f (x) = αx + β mod 26, is invertible. This map relies on
the same premises as the shift cipher but increases the complexity of the decryption process.
Rather than 26 keys, there are ϕ(26) · 26 = 12 · 26 = 312 possible keys. The weaknesses of
the shift cipher and the affine cipher are essentially the same, however, since a brute force
attack would be easy to implement using a computer.

Substitution Ciphers
One level of sophistication further than the affine cipher is what is colloquially known as
the Vigenère cipher. The key for the encryption relied on a keyword of a particular key
length. Each letter in the keyword was then assigned its letter, for example, vector =
(21, 4, 2, 19, 14, 17), and then the first letter would be translated by 21, the second letter
by 4, and so on. When the end of the keyword was reached, the seventh letter would be
translated by 21, the eighth by 4, and so on. This is what is more generally known as a
substitution cipher. It turns out that this encryption method for such ciphers is again not
secure. A possible attack uses the fact that frequencies of letters are not equal. The letter e
is the most common letter, followed by t, a, o, i, n, s, h, r. A knowledge of the language and
knowing which letters are used most commonly greatly reduces the work necessary to find
the key.

Block Ciphers
We next discuss block ciphers. We have already seen examples of block ciphers. The Playfair
cipher took the letters and grouped them into two letter blocks and then encoded each block.
Block ciphers typically used algebraic methods to encrypt data including linear algebra and
modular arithmetic. A simple block cipher could be constructed by taking an invertible 2 × 2
matrix, say
 
1 4
M=
1 3
writing a secret message as a matrix with two rows and then performing the multiplication.
For example, the plaintext secret message was written as a string of numbers
18 4 2 17 4 19 12 4 18 18 0 6 4
and then put into a matrix placing a 26 at the end if necessary:
   
1 4 18 4 2 17 19 4 12
·
1 3 4 18 18 0 6 4 26
 
34 76 74 17 43 20 116
=
30 58 56 17 37 16 90
and the ciphertext would then read as the string of numbers. To decrypt the message, one
needs to know the encryption matrix M so that one can find M −1 . The multiplication
by M −1 brings the decrypted message back to its original state. Variations of this method
include working mod 26 (and then finding a matrix M with gcd(det(M ), 26) = 1 or changing
the size of the encryption matrix.

64
World War I
Britain and Germany used closely related ciphers in World War I. The British used what is
known as the Playfair cipher. The key is again a word, for example, Remainder. One takes
the keyword, lops off the repeated letters (Remainder becomes Remaind) and places all
25 letters of the alphabet in a 5 × 5 array (treating i and j as the same letter):

R E M A I
N D B C F
G H K L O
P Q S T U
V W X Y Z

Suppose the plaintext to be encrypted is meet at the schoolhouse. Remove the spaces and
divide the text into groups:

me et at th es ch oo lh ou se

If there is a doubled letter appearing as a group, insert an x and regroup. Add an extra x
at the end to complete the last group if necessary:

me et at th es ch ox ol ho us ex.

Now use the matrix to encrypt the data in the following way. If the two letters are not
in the same row or column, replace each letter by the letter that is in its row and is in the
column of the other. For example, et becomes AQ since A is in the same row as E and in
the same column as T . If the two letters are in the same row, replace each letter with the
letter immediately to its right, with the matrix wrapping around from the last column to
the first. For example, me becomes AM . If the two letters are in the same column, replace
each letter with the letter immediately below it, with the matrix wrapping around from the
bottom to the top. For example, at becomes CY .
The system succumbs to a frequency attack since the frequencies of the various digrams
(two-letter combinations) have been calculated.
The German method, known as the ADF GX cipher was also used in World War I. Put
the letters of the alphabet (again treating i and j as the same). For example, the matrix
could be
A D F G X
A p g c e n
D b q o z r
F s l a f t
G m d v i w
X k u y x h

Each plaintext letter is labeled by the letter in its row and then its column. For example, l
becomes FD. The plaintext Julius Caesar becomes

GG XD FD GG XD FA AF FF AG FA FF DX.

65
This so far is just a disguised substitution cipher. To increase complexity, a keyword is
chosen, say Roman. Then the text is labeled as following:

R O M A N
G G X D F
D G G X D
F A A F F
F A G F A
D X

Then the columns are put in alphabetical order:

A M N O R
D X F G G
X G D G D
F A F A F
F G A A F
X D

The encrypted message is then

DXFGGXGDGDFAFAFFGAAFXD

The initial matrix and the keyword were changed frequently. While this was the original
cipher developed for use, the ADFGVX cipher was ultimately used in WWI allowing all 26
letter and the 10 digits to be used. The letters A, D, F, G, V , and X were used as they were
not easily confused in Morse code.

66
Public Key Cryptography
Modern technology has allowed the use of what is known as public key cryptography. Private
key or symmetric key cryptography suffered the disadvantage that both parties must meet
before hand, decide on a cipher, and then trust each other. Furthermore, should the cipher
be compromised, there was no way to devise another cipher without again meeting in person.
These problems were solved by Public Key Cryptography (PKC). The ideas of PKC were
started by Diffie-Hellman (1976). PKC allows Alice and Bob to communicate openly without
being in the same location. A non-mathematical way to describe PKC is as follows. Suppose
that Alice needs to communicate a secret message to Bob, but they have not decided on a
cipher and their communications are open (meaning anyone can see what they send each
other). Alice sends Bob a package with a lock on it, and Alice is the only person with a
key to her lock. Bob sends the locked box back to Alice with a second lock on it, and Bob
is the only one with a key to his lock. Alice can then take off her lock, and send the box
back to Bob, so that he can take off his own lock. Notice that this requires sending data
multiple times. For all of its advantages, PKC is inefficient, and it takes considerable time
to send moderate amounts of data. What is usually done in practice, however, is Alice can
communicate a cipher with Bob using PKC, and then can send the lengthy method using
private key algorithms.

RSA: Rivest, Shamir and Adleman

RSA relies on operations which are invertible, but much harder to invert than to apply the
original map. For example, given two large primes, it is trivial to multiply these two numbers
(using any computer), but it is very difficult to factor the product of the two numbers without
knowing what the two primes are. The one-way difficulty of these implementations is crucial
for the algorithm’s security. More precisely, let n = pq, where p, q are large primes (p, q can
be as large as ∼ 2364 ). To encrypt the message, Bob chooses two numbers E and D such that
ED ≡ 1 (mod ϕ(n)). E can be a large prime, and often people just take E = 216 +1 = 65537.
This determines D. The public key is (n, E). The private key is (D, p, q).
To encrypt the bit x ∈ Zn , Alice computes y = xE (mod n). To decrypt, Bob computes
D
y (mod n). Since ED = 1 (mod ϕ(n)), there exists k ∈ Z such that

ED = 1 + kϕ(n).

Recall that if gcd(x, n) = 1, then Euler’s theorem gives

xϕ(n) ≡ 1 (mod n).

Putting these together, we have

k
y D = xED = x1+kϕ(n) = x · xϕ(n) ≡ x (mod n).

67
Example
Suppose that Alice wants to send Bob a secret message. Bob choose the primes

p = 341550132831667
q = 4093082899

He then computes

n = pq = 1397993007844474643362633
ϕ(n) = (p − 1)(q − 1) = 1397993007502920417448068

Finally, he chooses E = 216 + 1 = 65537, and he computes D = 108469939776803184807413,

which is the inverse of E mod n.

Suppose Alice wants to send Bob the message “Vacation”. She first converts the message
from text into ASCII: x = 086097099097116105111110. She then computes:

y := xE (mod n) = 254631014816264736195113

and sends this to Bob. Then, Bob computes

yD (mod n) = 86097099097116105111110,

at which point he can translate from ASCII to text (remembering to add a zero at the
beginning since every ASCII character has three digits).

68
4.3 Exercises
Exercise 4.1. Prove that divisibility is transitive: Let a, b, c ∈ Z. Show that if a | b and
b | c, then a | c.

Exercise 4.2. Prove that if a | b, then a | bc for all c ∈ Z.

Exercise 4.3. Prove that 1 | n for all n ∈ Z.

Exercise 4.4. Fix an integer m > 2. Consider the relation

R = {(x, y) ∈ Z × Z : x ≡ y (mod m)}

(A) Prove that R is an equivalence relation

(B) Determine the equivalence classes of R.

(C) Describe the quotient set Z/R

Exercise 4.5. Let a1 a2 . . . an be an n digit number. Prove that

(A) a1 a2 . . . an ≡ a1 + a2 + · · · + an (mod 3)

(B) a1 a2 . . . an ≡ an (mod 5)

(C) a1 a2 . . . an ≡ a1 + a2 + · · · + an (mod 9)

(D) a1 a2 . . . an ≡ an − an−1 + an−2 − · · · + (−1)n+1 a1 (mod 11)

Exercise 4.6. Compute the following quantities:

(A) 123 DIV 10

(B) 123 MOD 10

(C) 2178 DIV 9

(D) 2178 MOD 9

Exercise 4.7. Evaluate the following greatest common divisors:

(A) gcd(200, 13)

(B) gcd(1010, 22)

(C) gcd(17, 357)

69
Exercise 4.8. First find the greatest common divisor of the following pairs of positive
integers. Then write the gcd(a, b) as a linear combination of a and b.

(A) 100, 17

(B) 318, 18

Exercise 4.9. Solve the congruence:

(A) 11x ≡ 51 (mod 91)

(B) 27x ≡ 5 (mod 1000)

Exercise 4.10. Let n = a1 a2 . . . ak be a k-digit number.

(A) Prove that n = a1 a2 . . . ak is divisible by 9 if and only if a1 + a2 + · · · + ak is divisible

by 9.

(B) Prove that n = a1 a2 . . . ak is divisible by 11 if and only if a1 − a2 + . . . (−1)k+1 ak is

divisible by 11.

(C) Prove that n = a1 a2 . . . ak is a multiple of 4 if and only if ak−1 ak is a multiple of 4.

(D) Prove that n = a1 a2 . . . ak is a multiple of 8 if and only if ak−2 ak−1 ak is a multiple of 8.

Exercise 4.11. Prove that gcd(n2 , n − 1) = 1 for all n > 1.

Exercise 4.12. Prove that gcd(n, n + 2) is either 1 or 2.

Exercise 4.13. Prove that gcd(fn+1 , fn ) = 1 for all n > 0, where fn is the nth Fibonacci
number.

Exercise 4.14. Prove or disprove: If p and q are distinct odd primes, then pq + 2 is also a
prime.

Exercise 4.15. Prove or disprove: If p1 , p2 , . . . , pn are primes, then p1 p2 . . . pn + 1 and

p1 p2 . . . pn − 1 are also primes.

Exercise 4.16. Prove or disprove: The smallest prime factor of 100! + 1 is greater than or
equal to 101.

Exercise 4.17. Let p be a prime. Prove that if ab ≡ 0 (mod p), then either a ≡ 0 (mod p)
or b ≡ 0 (mod p). Is this statement still true if p is not prime?

Exercise 4.18. Suppose gcd(m, n) = 1, and mx ≡ 0 (mod n). Prove that x ≡ 0 (mod n).

Exercise 4.19. Suppose that x ∈ Q and x2 ∈ Z. Prove that x ∈ Z.

Exercise 4.20. Solve the congruence x2 ≡ 1 (mod 8) by inspection.

Exercise 4.21. Prove that x2 ≡ 1 (mod p) has exactly two solutions when p > 3 is a prime.

70
Exercise 4.22. Prove that if a | bc and gcd(a, b) = 1, then a | c. (Hint: Use Bézout’s
Theorem)

Exercise 4.23. Prove that if a | c, b | c, and gcd(a, b) = 1, then ab | c. (Hint: Use Bézout’s
Theorem)

Exercise 4.24. Prove that if gcd(a, c) = 1 and gcd(b, c) = 1, then gcd(ab, c) = 1. (Hint:
Use Bézout’s Theorem)

Exercise 4.25. (A) State the Fundamental Theorem of Arithmetic.

(B) Let p > 2 be a prime. Prove that if p | n2 , then p | n.

√
(C) Prove that p is irrational, where p > 2 is prime.

(D) Prove that log2 (k) is irrational if k > 1 is odd.

71
72
Chapter 5

Combinatorics

5.1 Basic Definitions and Examples

Proposition 5.1 (Sum Rule for Counting). If A and B are finite sets, then

|A ∪ B| = |A| + |B| − |A ∩ B|.

In particular, if A and B are finite disjoint sets, then |A∪B| = |A|+|B|. One could interpret
this rule in the following way. If you have n ways of doing some task T1 , and m ways of
doing task T2 , and none of the ways of doing tasks T1 and T2 are identical, then there are
n + m ways of doing task T1 or T2 . The case when we have to find the cardinality of the
union of three or more sets is more involved, and we will discuss this later in the chapter
(see inclusion-exclusion).
Proposition 5.2 (Product Rule for Counting). If A1 , A2 , . . . , An are all finite sets, then

|A1 × A2 × · · · × An | = |A1 | · |A2 | · · · · · |An |.

This has the following combinatorial interpretation. If you have a procedure P which can be
broken down into n tasks T1 , T2 , . . . , Tn , and if there are k1 ways to do task T1 , k2 ways to
do task T2 , and so on, then the number of ways to perform the procedure P is k1 k2 . . . kn .
Proposition 5.3 (Division Rule for Counting). If A and B are finite sets and the function
f : A → B maps exactly k elements from A to a unique element in B, then |A| = k|B|.
This also has a combinatorial interpretation (what chapter are we in again?). If there are n
total ways of performing a procedure, and for each of the ways of performing the procedure
exactly d are identical ways, then there are n/d unique ways of performing the procedure.
We further illustrate this idea with the following example.
Example 5.4. Suppose that there is a group of 3 people, and we are to choose a team of
two. For simplicity, call these people Annie, Bob, and Cathy. How many ways can we form a
group of two people from this set of three? Obviously there are three teams: Annie and Bob,
Annie and Cathy, and Bob and Cathy. Let’s count another way: We have three choices for
the first person, and two choices for the remaining person giving 6 possible choices. However,
the order the person has been chosen is irrelevant as the team consisting of Annie and Bob

73
and the team consisting of Bob and Annie are precisely the same. Since there are 2 ways
to choose Annie and Bob (and hence two ways to choose every team), the total number of
3·2
possible teams is .
2

5.1.1 Examples
We will solve the following problems together in class. Recall a bit string is literally a string
of bits (that is, a sequence of zeros and ones such as 01001011). Also, a standard deck of
cards consists of 52 cards split into four suits: clubs (black), diamonds (red), hearts (red),
and spades (black). Each suit contains the cards 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King,
and Ace.

(1) How many 6-character license plates consist of 3 letters follows by 3 numbers?
Solution: 26 · 26 · 26 · 10 · 10 · 10

(2) How many 6-character license plates consist of 3 letters follows by 3 numbers, where
characters cannot be repeated?
Solution: 26 · 25 · 24 · 10 · 9 · 8

(3) How many cards from a standard deck are aces or jacks?
Solution: 4 + 4 − 0 = 8

(4) How many cards from a standard deck are clubs or queens?
Solution: 4 + 13 − 1 = 16

(5) How many cards from a standard deck are kings or red?
Solution: 4 + 26 − 2 = 28

74
 5.2 Permutations and Combinations
Definition 5.5. Given a set of n objects, an r-permutation (0 6 r 6 n) is an arrange-
ment of r objects from the set of n objects. The number of r-permutations is P (n, r)
and is pronounced “n permute r.”

Definition 5.6. Given a set of n objects, an r-combination (0 6 r 6 n) isa 

selection
n
of r objects from the set of n objects. The number of r-combinations is and is
r
pronounced “n choose r.” Note that some authors prefer the notation C(n, r) or n Cr .

5.2.1 Examples
(6) Given a set of 10 books, in how many ways can you arrange 3 of the books on a shelf?
Solution: P (10, 3) = 10 · 9 · 8

(7) Determine the number of r-permutations on a set of n objects.

n!
Solution: P (n, r) = n(n − 1) . . . (n − r + 1) =
(n − r)!

(8) In how many ways can a commanding officer choose 3 soldiers from a group of five
soldiers to go on a particular mission.
5·4·3 5!
Solution: =
3·2·1 2! · 3!

(9) Determine the number of r-combinations on a set of n elements.

P (n, r) n!
Solution: =
r! (n − r)! · r!

(10) If you want to draw a path from the origin (0, 0) to the point (4, 5), how many ways
can you do this if you must move going one unit to the right or one unit up at a time,
and where you travel only on integer coordinates (x, y) ∈ Z × Z?
 
9
Solution:
4

   
n n
Question 5.7. From a counting perspective, why is = ?
k n−k

75
5.3 Inclusion-Exclusion Principle
We have already seen that for finite sets A and B, we have:

|A ∪ B| = |A| + |B| − |A ∩ B|,

but what happens if we have three sets A, B, and C? Let’s derive what happens from the
two-set case:

|A ∪ B ∪ C| = |(A ∪ B) ∪ C|
= |A ∪ B| + |C| − |(A ∪ B) ∩ C|
= |A| + |B| − |A ∩ B| + |C| − |(A ∩ C) ∪ (B ∩ C)|


= |A| + |B| + |C| − |A ∩ B| − |A ∩ C| + |B ∩ C| − |(A ∩ C) ∩ (B ∩ C)|
= |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.

This formula actually works out rather nicely. We end up adding the single sets, subtracting
the intersections of pairs of sets and adding the intersection of all the sets. In general, we
have the following result which is called the inclusion-exclusion principle.

Proposition 5.8. Suppose that A1 , A2 , . . . , An are finite sets. Then,

n
[ n
X X X n
\
n−1
Ai = |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | + · · · + (−1) Ai .
i=1 i=1 16i<j6n 16i<j<k6n i=1

Example 5.9. How any integers less than or equal to 100 are multiples of 3, 4, or 5? For
ease, let An = {x ∈ Z+ | x 6 100 and n | x}. Then, the multiples of 3, 4, or 5 would be

|A3 ∪ A4 ∪ A5 | = |A3 | + |A4 | + |A5 | − |A3 ∩ A4 | − |A3 ∩ A5 | − |A4 ∩ A5 | + |A3 ∩ A4 ∩ A5 |

= |A3 | + |A4 | + |A5 | − |A12 | − |A15 | − |A20 | + |A60 |
             
100 100 100 100 100 100 100
= + + − − − +
3 4 5 12 15 20 60
= 33 + 25 + 20 − 8 − 6 − 5 + 1 = 60

Example 5.10. How many integers 6 1000 are multiples of 4, 5, or 6? Using the same
notation as before:

|A4 ∪ A5 ∪ A6 | = |A4 | + |A4 | + |A6 | − |A4 ∩ A5 | − |A4 ∩ A6 | − |A5 ∩ A6 | + |A4 ∩ A5 ∩ A6 |

= |A4 | + |A5 | + |A6 | − |A20 | − |A12 | − |A30 | + |A60 |
= 250 + 200 + 166 − 50 − 83 − 33 + 16
= 466

76
5.4 Pigeonhole Principle
Theorem 5.11. If you place n lobjects (or pigeons) into k bins (or holes), then there must
nm
be at least one bin with at least objects in it.
k
While this theorem may seem obvious or even whimsical, it is used in many serious
mathematical proofs (specifically in number theory and combinatorics). The first explicit
use of the principle was by Dirichlet who proved the following in 1834.
Theorem 5.12 (Dirichlet’s Approximation Theorem). Given any irrational number α, there
p p 1
exist infinitely many rational numbers such that α − 6 2.
q q q
See [Link] for a proof of Dirichlet’s Approximation Theorem. Thus, if
a real number can be well-approximated by many rational numbers with a relative small
denominator, then that number must be irrational. This theorem quantifies the phenomenon.
Consider the following result which can be proved via the pigeonhole principle:
Proposition 5.13. Let p be an odd prime. Then for all a ∈ Z there exists x, y ∈ Z with
x2 + y 2 ≡ a (mod p). That is, every integer is the sum of two squares mod p.
Proof. Let p be any odd prime. Recall that there are p+1 2
squares (these squares are called
residues) mod p. In other words the set S := {x MOD p : x ∈ Z} has cardinality p+1
2
2
.
Now, consider the set T := {a − y 2 MOD p : y ∈ Z}, and note that T also has cardinality
p+1
2
. Notice that the cardinality of S ∪ T is at most p. Thus,
p+1 p+1
|S ∩ T | = |S| + |T | − |S ∪ T | > + − p > 1.
2 2
In particular S ∩ T =
6 ∅, so there exists x0 ∈ S and y0 ∈ T such that
x20 ≡ a − y02 (mod p).

5.4.1 Examples
(1) Of any group of 37 people, show that at least four were born in the same month, at
least six students were born on the same day of the week, and at least two students
were born on the same number day.
Solution:
 
37
• There are 12 months, and hence at least = 4 students were born in the
12
same month  
37
• There are 7 days of the week, and hence at least = 6 students were born
7
on the same day of the week
 
37
• There are at most 31 days of the month, and hence at least = 2 students
31
were born in the same month

77
(2) Prove that if you select any five integers, then at least two of the integers differ by a
multiple of 4. How can this be generalized?
Solution: Consider any five integers x1 , x2 , x3 , x4 , x5 , and consider their remainders
mod 4. Let mi = xi MOD 4 for i = 1, . . . , 5, and note that mi ∈ {0, 1, 2, 3}. Since we
have five values m1 , . . . , m5 ∈ {0, 1, 2, 3}, at least two of the values must be congruent
mod 4: xi MOD 4 = xj MOD 4. Thus, xi − xj is a multiple of 4.

(3) Suppose we select any 31 integers from the set {1, 2, . . . , 60}. Prove that at least two
of the integers add to 61.
Solution: Consider the partition {1, . . . , 60} = {1, 60} ∪ {2, 59} ∪ · · · ∪ {30, 31}.
Details are left as Exercise 5.16.

(4) Given any five integers, there are three for which the sum of the square of the three
numbers is divisible by 3.
Solution: Let x1 , x2 , x3 , x4 , x5 ∈ Z, and consider mi := x2i (mod 3). Notice that the
squares mod 3 are {0, 1}. Thus, mi ∈ {0, 1}. If at least three values mi , mj , mk = 0,
then x2i + x2j + x2k ≡ 0 (mod 3). Otherwise, at least three values mi , mj , mk = 1. Thus,
x2i + x2j + x2k ≡ 3 ≡ 0 (mod 3).

(5) Your family tree has an incestuous loop. We assume the following noncontroversial
facts: Humans have existed for at least (at least!) 4, 000 years; Each generation occurs
no more than every 100 years; Each person has a biological mother and a biological
father; no more than 1, 000, 000, 000, 000 = 1.0 × 1012 humans have ever lived. Note
that a better upper bound on number of humans who have ever lived is about nine
times smaller and is estimated at 110, 000, 000, 000 = 1.1×1011 ), and most anthropolo-
gists agree that modern humans–homo sapiens sapiens–have existed for approximately
300, 000 years so the situation is worse than I say.
Solution: Note that 240 > 1012 . Hence....

78
5.5 Binomial Theorem
n


In the previous sections, we referred to the numbers k
as binomial coefficients. The reason
for this is the following well-known theorem.

Theorem 5.14 (Binomial Theorem). Given a, b ∈ R, and n ∈ N, we have the following:

n  
n
X n
(a + b) = ak bn−k .
k=0
k

Example 5.15.
 
0 0 0 0
(x + y) = x y =1
0
   
1 1 0 1 0 1
(x + y)1 = xy + x y =x+y
0 1
     
2 2 0 2 2 0 2
(x + y)2 = xy + xy + x y = x2 + 2xy + y 2
0 1 2
       
3 3 3 2 3 3 3
(x + y)3 = x + x y+ 2
xy + y = x3 + 3x2 y + 3xy 2 + y 3
0 1 2 3
         
4 4 4 3 4 2 2 4 4 4
(x + y)4 = x + x y+ xy + 3
xy + y
0 1 2 3 4
= x4 + 4x3 y + 6x2 y 2 + 4xy 3 + y 4 ,

and so on.

Example 5.16. What is the coefficient of x20 in the binomial expansion of (2x + 5)91 ?

91  
91
X 91
(2x + 5) = (2x)k 591−k .
k=0
k

91


Now the x20 term arises when k = 20, so the term with x20 is 20
220 591 x20 , and therefore
91 20 91


the coefficient is 20 2 5 .

d


Example 5.17. Prove that dx
xn = nxn−1 for all nonnegative integers n.

Proof. Let f (x) = xn . Then,

n  
X n k n−k
n
f (x + h) = (x + h) = x h = xn
k=0
k

79
Thus,
f (x + h) − f (x)
f 0 (x) = lim
h→0 h
(x + h)n − xn
= lim
h→0 h
hnxn−1 + h2 g(x)
= lim for some polynomial g(x)
h→0 h
= lim nxn−1 + hg(x)


h→0
n−1
= nx .

Next we discuss the so-called “Freshman’s Dream.”

Proposition 5.18. Given integers a, b and a prime p, we have
(a + b)p ≡ ap + bp (mod p).
Proof. Note that for 1 6 k 6 p − 1 we have:
 
p
≡ 0 (mod p),
k
which follows as kp = k!(p−k)!
p!


. Since k < p and p − k < p by the assumption 1 6 k 6 p − 1, it
but not in the denominator. Hence, kp = p·m


also follows that there is a p in the numerator,
for some integer m, and therefore kp ≡ 0 (mod p) for 1 6 k 6 p − 1 Furthermore,

p  
p p p
X p k k−p
(a + b) − a − b = a b − ap − b p
k=0
k
p−1  
X p k p−k
= a b
k=1
k
≡0 (mod p)
by the result above. Since (a + b)p − ap − bp ≡ 0 (mod p), the result follows.

The binomial theorem can be extended to handle more general exponents.

Theorem 5.19 (Extended Binomial Theorem - Newton (c. 1665)). For α > −1 we have
∞
α
X (α)k
(1 + x) = xk
k=0
k!

where (α)k = α(α − 1)(α − 2) . . . (α − k + 1) is the falling factorial.

√
Example 5.20. This agrees with the usual Taylor expansion for 1 + x when x is near 0:
√ 1 1 1 5 4
1 + x = 1 + x − x2 + x3 − x + ...
2 8 16 128

80
5.6 Exercises
Exercise 5.1.
(A) How many different three-letter initials can a person have?

(B) What if the initials are not repeated?

(C) What if only consecutive initials are not repeated?

Exercise 5.2. How many positive integers less than or equal to 1000 are:
(A) multiples of 4?

(B) multiples of 6?

(C) multiples of 4 and 6?

(D) multiples of 4 or 6?

(E) multiples of 4 but not 6?

(F) multiples of 4 or 6, but not both?

Exercise 5.3. How many positive integers less than or equal to 1000 are multiples of 7, 10,
or 15?
Exercise 5.4. A palindrome is a sequence of characters which reads the same forward and
backwards like RACECAR or 10011011001.
(A) How many bit strings of length 10 are palindromes?

(B) How many bit strings of length 11 are palindromes?

(C) How many bitstrings of length n are palindromes?

Exercise 5.5. How many bit strings of length 12 contain
(A) at most three 1s?

(B) at least three 1s?

(C) an equal number of 0s and 1s?

Exercise 5.6. An n-letter DNA sequence is a sequence of n characters (called bases), each
of which is adenine (A), cytosine (C), guanine (G), and thymine (T). A five-letter DNA
sequence could be ACT GT or GCT AG, for example.
(A) How many ten-letter DNA sequences are possible?

(B) How many ten-letter DNA sequences do not contain the character A?

(C) How many ten-letter DNA sequences contain the letter A at least once?

81
 (D) How many ten-letter DNA sequences contain exactly one A?

(E) How many ten-letter DNA sequences contain exactly two As?

(F) How many ten-letter DNA sequences start and end with the same letter?

(G) How many ten-letter DNA sequences start and end with the same letter and do not
contain any Cs?

(H) How many ten-letter DNA sequences do not contain the same letter consecutively?

(I) The human genome consists of approximately 3 billion base pairs. How many 3 billion-
letter DNA sequences are possible?

Exercise 5.7. Suppose that A is a nonempty finite set with cardinality |A| = n.

(A) How many possible relations can we construct on A?

(B) How many reflexive relations can be constructed on A?

(C) How many symmetric relations can be constructed on A?

(D) How many relations can be constructed on A which are both reflexive and symmetric?

Exercise 5.8. Suppose that a certain computer password is allowed to be from 8 to 12

characters long, and may contain only lowercase letters (a to z), uppercase letters (A to Z),
and numbers (0 to 9).

(A) How many such passwords are possible?

(B) How many such passwords are possible if you cannot repeat characters?

(C) How many such passwords are possible if you cannot repeat characters, and you must
include at least one number?

Exercise 5.9. Recall that a standard deck of cards consists of 52 cards partitioned into
four suits (clubs, diamonds, hearts, spades), an each suit contains cards of denominations
2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King, and Ace.

(A) How many 7-card hands are possible?

(B) How many 7-card hands contain exactly 3 spades?

(C) How many 7 card hands contain at least 1 heart?

(D) How many 7-card hands contain cards from at least two different suits?

(E) How many 7-card hands consist of cards all of the same color (recall clubs and spades
are black, while diamonds and hearts are red).

(F) How many ways are there to distribute 13 cards each to exactly four players?

82
Exercise 5.10. Suppose that we have 18 cookies, all of different types, to give to 6 people.
In how many ways can we give these eighteen cookies to six people so that each person has
exactly three cookies?

Exercise 5.11. Suppose that a certain class consists of 50 students. Find the largest integer
m such that the following is guaranteed to hold.

(A) At least m students were born in the same month.

(B) At least m students were born on the same day of the week

Exercise 5.12.

(A) What is the minimum number of students that must be in a class in order to guarantee
that at least two of the students were born on the same day of the year (assume there
are 366 days in a year).

(B) What is the minimum number of students that must be in a class in order to guarantee
that at least 10 students were born in the same month?

Exercise 5.13. Show that if you select any 5 consecutive integers, then one of those integers
must be a multiple of 5.

Exercise 5.14. Prove that if x1 , . . . xn are real numbers and

x1 + · · · + xn > C,

then xi > C/n for some i = 1, . . . , n.

Exercise 5.15. Suppose that x and y are positive real numbers satisfying xy > 100. Prove
that either x > 10 or y > 10.

Exercise 5.16. Suppose we select any 31 integers from the set {1, 2, . . . , 60}. Prove that at
least two of the integers add to 61.

Exercise 5.17. Suppose we select any 31 integers from the set {1, 2, . . . , 60}. Prove that at
least two of the integers are consecutive and hence relatively prime.

Exercise 5.18. Suppose that a bag contains 10 red marbles and 10 green marbles.

(A) How many marbles must be selected to ensure that you have at least 2 marbles of the
same color?

(B) How many marbles must be selected to ensure that you have at least one red marble?

(C) How many marbles must be selected to ensure that you have at least two red and at
least two green marbles?

Exercise 5.19. Consider a sphere S with 5 points on it. Prove that there exist a closed
hemisphere (a half sphere including its boundary) that contains at least 4 of those points.

83
Exercise 5.20. Prove or find a counterexample to the following generalization of Proposition
5.18:

(a + b)n ≡ an + bn (mod n).

Exercise 5.21. How many bitstrings of length 7 contain the sequence 1001?

Exercise 5.22. We say an integer n > 2 is squarefree if it is not divisible by any square
greater than 1. How many integers in the set {2, 3, 4, . . . , 100} are squarefree?

As an example, 71 and 30 are squarefree, but 12 and 200 are not squarefree.

Hint: Let An = {x ∈ Z+ | 2 6 x 6 100 and n | x}. Start by finding the quantity

|A4 ∪ A9 ∪ A16 ∪ A25 ∪ A36 ∪ A49 ∪ A64 ∪ A81 ∪ A100 |.

Of course some simplifications can be made!

Exercise 5.23. Prove that an entry in the middle of Pascal’s Triangle is the sum of the two
entries above it:
     
n+1 n n
= +
k k k−1

Exercise 5.24. Prove the binomial theorem:

n
X
n
(x + y) = xk y n−k .
k=0

Hint: Use the previous exercise and induction.

84
Chapter 6

Inequalities

In this chapter we focus on methods of proving inequalities which will be of use to you later
in your mathematical careers.
Example 6.1 (Method # 1). Let x ∈ (0, ∞). Then we have
1
x+ > 2.
x
Proof. One method would be to simplify algebraically which happens to work in this case:
1
x+ > 2 ⇐⇒ x2 − 2x + 1 > 0
x
⇐⇒ (x − 1)2 > 0

How else could we prove such an inequality? What if the algebra just doesn’t work out so
nicely? Calculus is a useful tool in our toolbox, and we have probably forgotten about its
utility.
Example 6.2 (Method # 2). Let x ∈ (0, ∞). Then we have
1
x+ > 2.
x
1
Proof. Let f (x) = x + . If x > 0, then we have
x
1
f 0 (x) = 1 − .
x2
Hence f 0 (x) = 0 if x = 1. Note that we are ignoring the solution x = −1 as our inequality
only concerned values x > 0. Now if x ∈ (0, 1), we have f 0 (x) < 0. If x ∈ (1, ∞), then
f 0 (x) > 0. Therefore f (1) is a minimum, and hence f (x) > f (1) = 2.
Of course the second method was more involved, but is a much more flexible (and therefore
is a much more useful) method.

85
Example 6.3. Let x, y, z ∈ R. Prove that

(x2 + 1)(y 2 + 1)(z 2 + 1) > 8xyz.

Proof. For functions of many variables, some more sophisticated solutions exist (such as the
D-test from Calc III for finding relative extrema and Lagrange Multipliers for constrained
optimization), but in this case it is enough to prove that

t2 + 1 > 2t

for all t ∈ R, and apply the inequality three times. We leave the details as an exercise.

Example 6.4. Prove that | sin x − sin y| 6 |x − y| for all x, y ∈ R. There are numerous
methods available here, but let’s use the Mean Value Theorem from calculus.

Theorem 6.5 (Mean Value Theorem). Suppose that f (x) is continuous on an interval [a, b]
and differentiable on (a, b). Then there exists c ∈ (a, b) so that

f (b) − f (a) = f 0 (c)(b − a).

Notice that f (t) = sin t is differentiable on R, and hence f is continuous on R as well.

Thus the Mean Value Theorem applies, and we know for all x, y there exists c between x
and y so that

sin(x) − sin(y) = cos(c)(x − y).

In particular we have

| sin x − sin y| = | cos c||x − y| 6 |x − y|,

thereby establishing the inequality. Note that this inequality gives us the very useful corol-
lary:

| sin x| 6 |x|

which holds for all x ∈ R.

Arguably the most useful inequality in all of mathematics is the Cauchy-Schwarz inequality.

Theorem 6.6 (Cauchy-Schwarz). Let x1 , . . . , xn , y1 , . . . , yn ∈ R. Then

(x1 y1 + · · · + xn yn )2 6 (x21 + · · · + x2n )(y12 + · · · + yn2 ).

Using vector notation, if x = (x1 , . . . , xn ) and y = (y1 , . . . , yn ), then

x · y 6 kxk · kyk
p
where x · y is the dot product, and where kxk = x21 + · · · + x2n is the (Euclidean) length of
the vector x.

86
Proof. Let
n
X n
X
2
A = x2i and B = 2
yi2
i=1 i=1

so that
n
!1/2 n
!1/2
X X
A= x2i and B= yi2
i=1 i=1

A and B are constants, so we can write

n n n
X 1 X X xi yi
xi yi = AB 2
i=1
2 i=1 i=1
AB

xi 2 yi 2
Applying the inequality 2 xAi yBi 6



A
+ B
to the summand, we see that
n n
X 1 X xi y i
xi yi = AB 2
i=1
2 AB
"i=1n n  
#
1 X  xi  2 X yi 2
6 AB +
2 A B
" i=1 n i=1
n
#
1 1 X 2 1 X 2
= AB x + y
2 A2 i=1 i B 2 i=1 i
= AB
n
!1/2 n
!1/2
X X
= x2i yi2
i=1 i=1

Squaring both sides of the expression gives the version of Cauchy-Schwarz stated above.
Theorem 6.7 (Hölder’s Inequality). Let x1 , . . . , xn , y1 , . . . , yn ∈ R, and suppose p, q ∈ (1, ∞)
satisfy p1 + 1q = 1. Then we have

n n
!1/p n
!1/q
X X X
xi y i 6 xpi yiq
i=1 i=1 i=1

Remark 6.8. Note that Cauchy-Schwarz is simply the case p = q = 2. The proof is similar
to that of Cauchy-Schwarz except that it uses an inequality called Young’s Inequality. Let
a, b > 0 and p, q > 1 where p1 + 1q = 1. Then,

ap b q
ab 6 + .
p q
An elementary1 proof of Young’s Inequality follows from Jensen’s Inequality (see below).
1
Do not confuse elementary with easy!

87
Proposition 6.9 (Arithmetic-Geometric Mean Inequality). For positive real numbers x1 , . . . , xn ,
we have
x 1 + x2 + · · · + xn √
> n x1 x2 . . . xn .
n
for all n > 1.

Proof. Let P (n) denote the statement to be proved. Then prove this by induction the
following way.

(1) Prove that P (2n ) =⇒ P (2n+1 ) for all n > 0.

(2) Prove that P (n) =⇒ P (n − 1) for all n > 3.

This induction proof was given by Cauchy.

Definition 6.10. A function f : (a, b) → R is called convex on (a, b) if

f (tx + (1 − t)y) 6 tf (x) + (1 − t)f (y)

holds for all x, y ∈ (a, b) and for all t ∈ [0, 1].

Note 6.10.1. If f (x) is twice differentiable, then f (x) is convex on (a, b) if and only if
f 00 (x) > 0 for all x ∈ (a, b). However convex functions need not be differentiable (consider
f (x) = |x|).

Jensen’s Inequality gives a powerful inequality for convex functions:

Theorem 6.11 (Jensen’s Inequality). Let f : (a, b) → R be convex. Consider t1 , . . . , tn > 0

such that t1 + · · · + tn = 1. Then

f (t1 x1 + · · · + tn xn ) 6 t1 f (x1 ) + · · · + tn f (xn ).

for all x1 , . . . , xn ∈ (a, b).

Proof. We will prove this by induction on n > 2. The base case, n = 2, holds by definition
of convexity. Now assume that

k
! k
X X
f t i xi 6 ti f (xi ).
i=1 i=1

holds for all quantities t1 + . . . tn = 1. We then consider

k+1
! k
!
X X
f t i xi =f ti xi + tk+1 xk+1
i=1 i=1

88
We may assume that tk+1 ∈ (0, 1) (If tk+1 ∈ {0, 1} then the statement is already true
assuming the inductive hypothesis). Then,
k+1
! k
!
X X ti
f ti xi = f (1 − tk+1 ) xi + tk+1 xk+1
i=1 i=1
1 − tk+1
k
!
X ti
6 (1 − tk+1 )f xi + tk+1 f (xk+1 )
i=1
1 − tk+1
k
X ti
6 (1 − tk+1 ) f (xi ) + tk+1 f (xk+1 )
i=1
1 − tk+1
k+1
X
= ti f (xi ).
i=1

This completes the proof.2

Jensen’s inequality admits the following corollary which is sometimes also (confusingly)
called Jensen’s inequality:

Corollary 6.12. Let f : (a, b) → R be convex. Then

 
x1 + · · · + xn f (x1 ) + · · · + f (xn )
f 6
n n

for all x1 , . . . , xn ∈ (a, b).

Proof. Exercise.

2
This proof is correct, but many details have been omitted. You should fill in as many missing details as
is necessary so that you can explain this proof to someone else.

89
6.1 Exercises
x y
Exercise 6.1. Prove that > 2 for all x, y ∈ (0, ∞).
y
+ x
√
Exercise 6.2. Prove that | sin x + cos x| 6 2 for all x ∈ R.

Exercise 6.3. Prove that x2 y 2 (4 − x2 )(4 − y 2 ) 6 16 for all x, y ∈ [−2, 2].

√
Exercise 6.4. Prove that 1 + x < 1 + 12 x for all x > 0.
√
Exercise 6.5. Prove that 2 x + x1 > 3 for all x > 1.

Exercise 6.6. Prove that ex > 1 + x + 21 x2 for all x ∈ (0, ∞).

Exercise 6.7. Prove that

Z π/2 √
sin x 2
dx 6 .
π/4 x 2

Exercise 6.8. Let f : [0, ∞) → [0, ∞) be given by f (x) = x4 − x3 + x.

(A) Show that f (x) is strictly increasing on [0, ∞).

(B) Show that f (x) is a bijection.

Exercise 6.9. Prove that for real numbers x, y, z we have

x2 + y 2 + z 2 > xy + yz + xz.

Exercise 6.10. Let x1 , . . . , xn ∈ R.

(A) Prove that

(x1 + · · · + xn )2 6 n(x21 + · · · + x2n ).

(B) More generally, prove that

(x1 ± · · · ± xn )2 6 n(x21 + · · · + x2n ).

Exercise 6.11 (Cauchy-Schwarz for Integrals). Suppose that f, g : [a, b] → R are continuous
function (and hence, integrable) on [a, b]. Prove
Z b 2 Z b  Z b 
2 2
f (x)g(x) dx 6 f (x) dx g(x) dx
a a a

Exercise 6.12. Let f : [a, b] → R be continuous. Prove that

Z b 2 Z b
f (x) dx 6 (b − a) f (x)2 dx
a a

90
Exercise 6.13. Let f : [0, ∞) → R be a continuous function which is differentiable on
(0, ∞). Suppose further that f (0) = 0 and f 0 (x) ∈ [0, 1] for x ∈ (0, ∞).
Z x
(A) Show that the function F (x) = 2 f (t) dt − f (x)2 is increasing on [0, ∞).
0
Z x
(B) Show that 2 f (t) dt > f (x)2 for x > 0.
0

(C) Show that for x > 0 we have

Z x Z x 2
3
f (t) dt 6 f (t) dt .
0 0

91
92
Chapter 7

Appendix

7.1 Real Number Axioms

The real numbers are assumed to satisfy the following properties.
(i) Addition and Multiplication are associative:
a + (b + c) = (a + b) + c and a · (b · c) = (a · b) · c for all a, b, c ∈ R.

(ii) Addition and Multiplication are commutative:

a+b=b+a and a · b = b · a for all a, b ∈ R.

(iii) Existence of additive identity: there exists 0 ∈ R such that a + 0 = 0 + a = a for all
a∈R
(iv) Existence of multiplicative identity: there exists 1 ∈ R such that 1 · a = a · 1 = a for
all a ∈ R.
(v) Existence of additive inverse: for all a ∈ R, there exists −a ∈ R such that
a + (−a) = (−a) + a = 0.

(vi) Existence of multiplicative inverse: for all a ∈ R \ {0}, there exists a−1 such that
a · a−1 = a−1 · a = 1.

(vii) Distributive Law:

a · (b + c) = (a · b) + (a · c) for all a, b, c ∈ R.

(viii) There exists a set of positive numbers P such that:

i) (Trichotomy Law) a ∈ P, −a ∈ P , or a = 0 for all a ∈ R
ii) (Closure) if a, b ∈ P , then a + b ∈ P and a · b ∈ P.
(ix) Least Upper Bound Property: Every nonempty subset of R which is bounded above
has a least upper bound. (An upper bound of a set E is a number B such that x 6 B
for all x ∈ E.)

93
7.2 Integer Axioms
The integers are a subset of the real numbers: Z ⊆ R. Hence all real-number axioms hold
for integers as well. There are a few additional axioms for integers.

(i) The integers are closed under addition:

x+y ∈Z for all x, y ∈ Z

(ii) The integers are closed under multiplication:

x·y ∈Z for all x, y ∈ Z.

(iii) Every nonempty subset of nonnegative integers has a least element.

Property (C) is called the Well-Ordering Axiom or Well-Ordering Property, and it turns
out to be remarkably useful. We list a few elementary consequences of the Well-Ordering
Axiom, though the Principle of Induction (both weak and strong induction) and the Division
Algorithm were also consequences of the WOA.

Proposition 7.1. Suppose that S ⊆ N is a set satisfying the following two properties
i) 0 ∈ S
ii) If k ∈ S for some k > 0, then k + 1 ∈ S. Then S = N is the set of nonnegative
integers.

Proof. Since we have S ⊆ N by assumption, then we must only show that N ⊆ S. That is,
we have to show that every nonnegative integer is an element of S. Suppose S 6⊆ N, and let
k be the smallest nonnegative integer which is not an element of S. Note that 0 ∈ S, so that
k > 1. However, if k ∈/ S, then k − 1 ∈
/ S, which contradicts that k is the smallest positive
integer which is an element of S. This shows that every nonnegative integer must actually
be in S, and hence S = N.

Proposition 7.2. There is no integer x ∈ (0, 1).

Proof. Suppose that there was an integer 0 < x < 1. By the Well-Ordering Axiom, there
exists a smallest integer b such that 0 < b < 1. Then, multiply all parts of the inequality by
b to see that 0 < b2 < b. Since b2 = b · b is the product of two integers, it must also be an
integer. This contradicts that b is the smallest such integer, and hence there are no integers
in (0, 1).
Remark 7.3. It seems a bit silly to prove that there are no integers in the interval (0, 1), but
this is a remnant of the fact that we are introduced to the integers only informally at first
(which is of course, a very reasonable thing). However, Proposition 7.1 is how one formally
defines the nonnegative integers, and as such, it is not at all obvious (a priori) that there is
no positive integer in (0, 1).

94
Index

ADFGX Cipher, 65 Counterexample, 39

Affine Cipher, 64
Antisymmetric Relation, 34 De Morgan’s Law, 38
Arithmetic-Geometric Mean Inequality, 88 De Morgan’s Law for Sets, 8, 18
Axiom, 40 Disjoint, 7
Dividend, 50
Bézout’s Little Theorem, 55 Division (Number Theory), 49
Bernoulli’s Inequality, 17 Division Algorithm, 49
Bijection, 26 Division Rule for Counting, 73
Binary Relation, 21 Divisor, 50
Binomial Theorem, 79, 80
Block Cipher, 64 Empty Product, 28
Empty Set, 5
Caesar Cipher, 63 Empty Sum, 28
Cantor, Georg, 31 Equivalence Class, 22
Cardinality, 29 Equivalence Relation, 22
Cartesian Product, 6 Equivalent Propositions, 38
Cauchy-Schwarz, 86, 90 Euclidean Algorithm, 55
Ceiling Function, 21 Euler’s Theorem, 61
Chinese Remainder Theorem, 60 Euler’s Totient Function (ϕ), 61
Ciphertext, 63 Extended Binomial Theorem, 80
Collatz Conjecture, 43
Factorial, 12
Combination, 75
Fermat’s Little Theorem, 62
Complement of a Set, 8
Fibonacci Sequence, 14
Composite, 52
Finite Field, 52
Conclusion, 38
Finite Set, 10, 29
Congruence (mod m), 50
Floor Function, 21
Congruence Class, 22
Fundamental Theorem of Arithmetic, 52
Conjecture, 40
Contradiction, 38 Graph of a Function, 27
Contrapositive, 38 Greatest Common Divisor, 54
Converse, 38
Convex, 88 Hölder’s Inequality, 87
Coprime, 54 Harmonic Number, 12
Corollary, 40 Hilbert’s Hotel, 29
Countable Set, 29 Hypothesis, 38

95
Identity Function, 26 Proof, Equivalence, 41
Image, 24 Proof, Existence (Constructive), 42
Inclusion-Exclusion Principle, 10, 76 Proof, Existence (Nonconstructive), 42
Induction, 11 Proof, Uniqueness, 43
Inequalities, 85 Proposition, 40
Injective Function, 24 Proposition (Logic), 37
Integer, 5 Public Key Cryptography, 67
Integers (mod m), 52
Intersection, 6 Quotient, 50
Inverse (mod m), 58 Quotient Set, 22

Jensen’s Inequality, 88 Rational Number, 5

Real Number, 5
Key, 63 Reflexive Relation, 21
Least Common Multiple, 54 Relation, 21
Lemma, 40 Relatively Prime, 54
Remainder, 50
Mean Value Theorem, 86 Ring of Integers (mod m), 52
Natural Number, 5 RSA Encryption, 67

One-to-One Function, 24 Sequence, 28

Onto Function, 25 Serial Relation, 33
Or (Exclusive), 37 Series, 28
Or (Inclusive), 37 Set Difference, 6
Strong Induction, 14
Pairwise Relatively Prime, 54 Sum Rule for Counting, 73
Partially Ordered Set, 34 Surjective Function, 25
Partition, 22, 23 Symmetric Difference, 6
Permutation, 75 Symmetric Key, 63
Pigeonhole Principle, 77 Symmetric Relation, 21
Plaintext, 63
Playfiar Cipher, 65 Tautology, 38
Poset, 34 Theorem, 40
Positive Integer, 5 Transitive Relation, 21
Power Set, 9 Triangle-Inequality, 47
Preimage, 24 Tribonacci Sequence, 15
Prime, 52
Prime Number Theorem, 53 Uncountable Set, 32
Private Key Encyrption, 63 Union, 5
Product Notation, 28 Universal Set, 8
Product Rule for Counting, 73
Vigenére Cipher, 64
Proof, 40
Proof, Cases, 41 Weak Induction, 11
Proof, Contradiction, 40 Without Loss of Generality, 41
Proof, Contraposition, 40
Proof, Direct, 40 Young’s Inequality, 87

96