MATH2301
Workbook on Number Theory
Table of contents
0. Introductory comments
1. Division algorithm
2. Prime factorisation
3. Modular arithmetic
0. Introductory comments
With MATH1061 under your belt, this is not
your first exposure to number theory. How-
ever, this time around, focus will be on proofs
of some main theorems and quick review of
what you have already learnt.
Notation. Throughout this workbook Z de-
notes the integers
{· · · , −2, −1, 0, 1, 2, · · · }.
Moreover, N denotes positive integers
{1, 2, · · · }.
1. Division algorithm
Definition 1.1. Let a, b ∈ Z. We say a
divides b if there exists another integer c ∈ Z
such that
b = ac.
In this case, we write
a | b.
Examples 1.1.
(i) 4 | 12
(ii) 6 6 |15
(iii) n | 0 for all n ∈ Z.
1
Theorem 1.1. Let a, b ∈ Z and suppose
b 6= 0. Then there exists unique integers q
and r such that
a = bq + r
and
0 ≤ r < b.
Terminology 1.1. The integer q is called
the quotient and r is called the remainder.
Proof of existence
2
Proof of uniqueness
3
Exercise 1.1.
(i) Every integer is either even or odd, but
not both.
(ii) The remainder r is zero if and only if b
divides a.
(iii) Suppose a | b and a | c. Then a | bx + cy
for all integers x, y.
(iv) If a | b and b 6= 0, then |a| ≤ |b|. Thus,
only finitely many integers divide a given in-
teger b.
4
Definition 1.2. Let a and b be non-zero
integer. The greatest common divisor of a
and b, denoted by gcd(a, b), is the largest
integer d dividing both a and b.
Comment 1.1 Alternatively, d = gcd(a, b) if
the following three conditions hold:
(i) d | a;
(ii) d | b;
(iii) If c | a and c | b, then c ≤ d.
Example 1.1
(i) gcd(21, 6) =
(ii) gcd(14, 2) =
(iii) gcd(a, b) = gcd(b, a).
(iv) gcd(a, 0) =
(v) gcd(a, −b) = gcd(a, b).
5
Exercise 1.1. Let a = bq +r be as in the di-
vision algorithm. Then gcd(a, b) = gcd(b, r).
Algorithm 1.1: Finding gcd.
Input a ≥ b ≥ 0, a 6= 0.
While b > 0 set a := b and b := r
return r.
Example 1.2
gcd(2234, 1020) =
6
2. Primes
Definition 2.1. Two integers a and b are
said to be coprime if gcd(a, b) = 1.
Comment 2.1. a and b are coprime if and
only if they have no common factor.
Example 2.1
(i) 7 and 17 are coprime.
(ii) 6 and 16 are not coprime.
Exercise 2.1.
(i) a and b are coprime if and only if there
exists integers x and y such that ax + by = 1.
(iu) Suppose a and b are coprime. Then
a | c, and b | c =⇒ ab | c.
7
Definition 2.2.
(i) An integer p ≥ 2 is called prime if its only
divisors are 1 and p.
(ii) An integer q is said to be a prime power
if q = pa for some positive integer a.
(iii) An integer which is not a prime is called
composite .
Theorem 2.1 (Euclid). There exists in-
finitely many primes
Proof.
8
Theorem 2.2 (Fundamental Theorem of
Arithmetic) Every integer a can be written
as
a = p1 p2 · · · pk
where p1 ≤ p2 ≤ · · · ≤ pk are prime numbers.
Moreover, this presentation is unique.
Proof of Existence
9
Proof of Uniqueness
10
Comments 2.2. Unique factorisation fails
in slightly more general setting; e.g. in
√ √
Z[ −5] = {a + b −5 | a, b ∈ Z}.
For instance,
√ √
2.3 = (1 + −5)(1 − −5) = 6.
Theorem 2.3. The number of primes less
than n is asymptotic to logn n .
e
Comments 2.3
(i) Distribution of primes is intimately re-
lated to Riemann Hypothesis.
(ii) It is not known if there are infinitely many
twin primes.
(iii) It is not known if every even integer
greater than 2 can be written as a sum of
two primes.
11
3. Modular Arithmetic
Fix a positive integer n.
Definition 3.1. Let a, b ∈ Z. We say a is
congruent to b modulo n if
n | a − b.
In this case, we write a ≡ b mod n.
Examples 3.1
(i) 21 ≡ 3 mod 6.
(ii) −7 ≡ 3 mod 10.
(iii) n2 ≡ 1 mod 4 for all odd n.
(iv) 10n ≡ 1 mod 9 for all n ≥ 0.
12
Comments 3.1
(i) a ≡ b mod n if and only if a and b have
the same remainder under division by n.
(ii) a ≡ 0 mod n if and only if n | a.
Exercise 3.1. Show that congruence mod-
ulo n defines an equivalence relation on Z.
We let [a] denote the equivalence class con-
taining the integer a. Then [a] is the set
of all integers whose remainders modulo n
equals a.
Examples 3.2
(i) If n = 2 then [1] is the set of all odd num-
bers and [0] is the set of all even numbers.
(ii) If n = 5, then
[2] = {· · · , −8, −3, 2, 7, 12, · · · }
(iii) If n = 2 then [1] = [−1] = [3] = [2017].
(iv) If n = 5 then [1] = [−4] = [2016].
13
Division algorithm tells us
Z = {[0], [1], · · · , [n − 1]}.
Let us call this a new set Zn. We now define
addition and multiplication on Zn:
[a] + [b] = [a + b].
[a].[b] = [a.b].
Examples 3.3
(i) In Z2, [1] + [1] = [0]. This is just saying
that the sum of two odd integers is even.
(ii) In Z5, [3][4] = [2].
(iii) In Z10, [4][9] =
(iv) In Z15, [10] + [10] =
14
Theorem 3.1 Addition and multiplication
in Zn is well-defined; i.e. if [a] = [b] and
[c] = [d] then
[a + b] = [c + d], [ab] = [cd].
Proof.
15
Question 3.1 What about subtracting in
Zn?
Definition 3.2 Let [a] ∈ Zn. An inverse for
[a] is an element [x] ∈ Zn such that
[ax] = [1] ⇐⇒ ax ≡ n mod 1.
Examples 3.3
(i) In Z11, we have [3][4] = [1]. Thus,
[3]−1 = [4].
(ii) In Z5, [2]−1 =
(iii) In Z10, does [2] have an inverse?
(iv) Does [0] ever have an inverse?
Definition 3.3 Invertible elements in Zn are
called units.
16
Theorem 3.2
1. Let n > 1. If [a] ∈ Zn is invertible then
its inverse is unique.
2. If [a] is invertible, then so is [a]−1. More-
over, inverse of [a]−1 equals [a].
Proof.
17
Theorem 3.3 Let n > 1. Then [a] ∈ Zn is
invertible if and only if gcd(a, n) = 1.
Proof.
18
Corollary 3.1 Let p be a prime number and
suppose a 6= 0. Then [a] is invertible in Zp.
Comment 3.2 We see that we can add,
subtract, multiply, and divide (by non-zero
elements) in Zp. We say that Zp is a field.
Exercise 3.2.
(i) Suppose gcd(a, n) = 1. Show that the
equation [a][x] = [b] has a unique solution.
(ii) Show that for all integers r,
([a]−1)r = ([a]r )−1 = [a]−r .
(iii) Show that for all integers r and s,
[a]r [a]s = [a]r+s.
Notation 3.1 Sometimes we drop the bracket
in the notation and write a instead of [a] for
an element of Zn.
19
We have discussed congruence equations of
the form ax = b in Zn. We now want to
discuss systems of congruence equations.
Example 3.4. The system
x≡1 mod 3
x≡2 mod 5
x≡3 mod 7
is solvable. Indeed, x = 52 is a solution. Is
this the only solution?
20
Theorem 3.4 (Chinese Remainder The-
orem). Let m1, · · · , mk ∈ N be pairwise co-
prime positive integers. Then every system
of equations
x ≡ ai mod mi, 1≤i≤k
is solvable. Moreover, the solution is unique
modulo m1m2 · · · mk .
Proof
21
Proof continued.
22
Notation 3.2. We let Z× n denote the set of
units (=invertible) elements in Zn.
Example 3.5. (i) Z12 = {1, 5, 7, 11}.
(ii) If p is prime then Zp = {1, 2, · · · , p − 1}.
Exercise 3.3 Show that if a ∈ Zn is invert-
ible, then there exists an integer k such that
ak = 1.
Definition 3.4 The order of an element a ∈
Z×n , denoted by o(a), is the smallest positive
integer k such that ak = 1.
Example 3.6.
(i) The order of 2 ∈ Z5 is
(ii) The order of 4 ∈ Z11 is
23
Theorem 3.5. Let a ∈ Z× m
n . Then a = 1 if
and only if m is a multiple of o(a).
Proof.
24
Exercise 3.3. Show that if a ∈ Z×
n then
o(a) | |Z×
n |.
Definition 3.5. If o(a) = |Z× n | then a is
called a primitive root of Zn.
Exercise 3.5. Show that if a ∈ Z×
n is a
primitive root then
Z× 2
n = {1, a, a , · · · , a
n−1 }.
Example 3.7. Which one of the following
is a primitive root?
(i) 2 ∈ Z5
(ii) 4 ∈ Z11
(ii) 3 ∈ Z8
Question 3.2 . For which integer n does
Zn have a primitive root?
25
Definition 3.6. The function ϕ : N → N
defined by
n 7→ |Z×
n|
is called the Euler ϕ function.
Example 3.8.
(i) ϕ(6) =
(ii) ϕ(p) =
(ii) ϕ(2n) =
Exercise 3.6. Show that for all primes p,
we have ϕ(pk ) = pk−1(p − 1).
Theorem 3.6. Let m, n ∈ N be coprime.
Then ϕ(mn) = ϕ(m)ϕ(n).
Proof. Later in the course.
Qk a
Exercise 3.7. Compute ϕ( i=1 pi i ).
26
Theorem 3.7 (Euler’s Theorem). Let
a, n ∈ Z with n ≥ 1 and gcd(a, n) = 1. Then
aφ(n) ≡ 1 mod n.
Proof.
27
Corollary 3.2 (Fermant’s Little Theorem).
Let p be a prime and a not divisible by p.
Then ap ≡ a mod p.
Proof.
28
