Introduction to number theory

Lecture notes 2025

Morten S. Risager
These are notes for the 7 week course “Introduction to Number Theory” at the University of
Copenhagen.
Cover photo kindly provided by Christian Rasmussen.

Please send comments and corrections to risager@math.ku.dk

Last compiled with LATEX 2! on June 27, 2025.
 Contents

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1 Divisibility and primes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.1 Notation and basic properties 6
1.2 Euclidean division and greatest common divisor 6
1.3 Diophantine equations 9
1.3.1 Linear equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.4 Primes 11
1.4.1 The fundamental theorem of arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4.2 On the number of primes less than a given size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4.3 Pythagorean triples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.5 Exercises for Chapter 1 15

2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1 Basic structures 16
2.2 Modular arithmetic 17
2.3 Euler’s ∀-function 18
2.3.1 The Chinese remainder theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4 Primitive roots modulo n. 20

2.4.1 Roots of polynomials. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.2 Artin’s conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.5 Local obstructions 23

2.6 Exercises for Chapter 2 23

3 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1 Primality testing 25
3.1.1 Carmichael numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.2 Miller-Rabin’s primality test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.1.3 Modular exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4

3.2 Concrete cryptosystems 28

3.2.1 Diffie–Hellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.2 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.3 Exercises for Chapter 3 31

4 Quadratic reciprocity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.1 Quadratic residues and Legendre symbols 33
4.2 Quadratic reciprocity 34
4.2.1 Algebraic integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
4.2.2 Gauss sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.3 Exercises for chapter 4 41

5 Arithmetic functions and Dirichlet series . . . . . . . . . . . . . . . . . . . . . . . 42

5.1 Arithmetical functions 42
5.1.1 Perfect numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1.2 Convolution of arithmetical functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
5.1.3 The Möbius function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.2 Dirichlet series 47

5.3 Exercises for chapter 5 51

6 Sums of squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
6.0.1 Waring’s problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

6.1 Sums of squares 53

6.1.1 Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.1.2 Sums of two squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
6.1.3 Gaussian integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.1.4 Sums of three squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.1.5 Sums of four squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.2 Exercises for chapter 6 62

7 Continued fractions and approximations . . . . . . . . . . . . . . . . . . . . . . . 64

7.1 Continued fractions 64
7.1.1 Infinite continued fractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

7.2 Approximating real numbers with rationals 70

7.3 Exercises for chapter 7 72

8 The ABC-conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
 Introduction

Number theory has a long history in mathematics. Indeed its problems and concepts have played
a formative role in many branches of mathematics. Even today it is a vibrant and active part of
modern mathematics, and it continues to offer new insights and stimulate the creation of new
mathematical subdisciplines and theories.
Historically there is a clear tendency that number theory has been driven by the desire to tackle
specific problems, e.g.: Does there exist positive integer solutions to the equation

x n + yn = zn

for n → 3 (the answer is no)? Are there infinitely many twin primes (we do not know)? Trying to
answer such questions has often taken precedence, rather than generalizing the theory as much as
possible. This comment should not be taken as an indication that number theory does not use or
develop deep theories, but merely as statement of what motivates and drives many number theorists.
This text gives an introduction to the many facets of number theory, including tastes of its
algebraic, analytic, metric, Diophantine and geometric incarnations. We assume the reader has
taken a first course in algebra and has familiarity with groups as well as modular arithmetic.
The text is somewhat brief at points, and we strongly encourage the reader to dive into other
texts on number theory to get a more multifaceted view on the subject. Several are listed in the
bibliography and they all offer their own unique views on the topic.
 1. Divisibility and primes

1.1 Notation and basic properties

We denote by
• N the set of natural numbers 1, 2, 3, . . .,
• Z the set of integers,
• Q the set of rationals,
• R the set of real numbers, and
• C the set of complex numbers.
If a, b ↑ Z we say that a divides b and write a | b if there exists c ↑ Z such that b = ac. We call a a
factor of b. If a does not divide b we write a ⊋ b.
Proposition 1.1.1 Let a, b, c, d ↑ Z. Then
(i) if a | b and b | c then a | c.
(ii) if a | b and c | d then ac | bd.
(iii) if m ↓= 0 then a | b if and only if ma | mb.
(iv) if d | a and a ↓= 0 then |d| ↔ |a|.

Proof. See Exercise 1.5. ↭

1.2 Euclidean division and greatest common divisor

We start by stating and proving a fundamental property of the integers that we learn already in
elementary school.

Theorem 1.2.1 — Euclidean division. Let a, b ↑ Z with b ↓= 0. Then there exist unique integers
q, r satisfying 0 ↔ r < |b| and a = bq + r.

Proof. The case a = 0 is left as an easy exercise. See exercise 1.7.

We first reduce to the case a, b > 0. If b < 0 we let b↗ = ↘b and a unique solution to a = b↗ q↗ + r↗
with 0 ↔ r↗ < b↗ gives a unique solution q = ↘q↗ , r = r↗ to a = bq + r with 0 ↔ r < |b|. Hence, we
may assume b > 0. If a < 0 and b > 0 we let a↗ = ↘a. Then a unique solution to a↗ = bq↗ + r↗ gives
1.2 Euclidean division and greatest common divisor 7

a unique solution q = ↘q↗ ↘ 1, r = b ↘ r↗ to a = bq + r with 0 ↔ r < |b|. We may therefore assume

a, b > 0.
If a, b > 0 consider
Q = {n ↑ Z|n → 0, a ↘ bn → 0}.
This set is non-empty (0 ↑ Q) and bounded (if n > a/b then a ↘ bn < 0). Let q ↑ Q be its maximal
element. Then r = a ↘ bq < b since if a ↘ bq → b then a ↘ b(q + 1) → 0 which contradicts the
maximality of q. This proves existence in this case.
To prove uniqueness suppose q↗ , r↗ is another set of integers satisfying the conclusion. Then
q ↑ Q so q↗ ↔ q. If q↗ < q then
↗

r↗ = a ↘ bq↗ = a ↘ b(q + (q↗ ↘ q)) = r ↘ b(q↗ ↘ q) → b

which is a contradiction. Hence, q = q↗ and r = r↗ , which proves uniqueness in this case. ↭

↭Example 1.1 The integers q, r from Euclidean division can be found by standard long division:
Given a = 36948, b = 2100 we find

36948 : 2100 = 17
2100
15948
14700
1248

so 36948 = 2100 · 17 + 1248 i.e. q = 17, r = 1248. ↭

As an example of the power of Theorem 1.2.1 we prove a simple result about division. This
will be somewhat easier to prove after we have proved the fundamental theorem of arithmetic below
(Theorem 1.4.2) but the following simple proof shows that it can be proved without the use of
unique factorization.
Proposition 1.2.2 Assume m2 | b2 . Then m | b.

Proof. Certainly there exist natural numbers l such that m | bl (e.g. l = m). By the well-ordering
principle we can let l0 be the smallest such number. Let n, k be the integers such that b2 = m2 n,
bl0 = mk. Notice that mbk = b2 l0 = m2 nl0 so bk = mnl0 . By Theorem 1.2.1 we can write k = ql0 + r
with 0 ↔ r < l0 . But then

br = b(k ↘ ql0 ) = mnl0 ↘ bql0 = m(nl0 ↘ qk)

so m divides br. By the minimality of l0 we must have r = 0. But then bl0 = mk = mql0 which
shows that b = mq. ↭

Definition 1.2.1 Given a, b ↑ Z not both zero we define their greatest common divisor as the
largest natural number which divides both a and b, i.e.

gcd(a, b) = max{d ↑ N : d | a, d | b}.

We define gcd(0, 0) = 0

We note that 1 divides any integer, and that if d | a then |d| ↔ |a|, so the maximum in the above
definition is over a finite non-empty set.
Proposition 1.2.3 Let a, b ↑ Z. Then

gcd(a, b) = gcd(b, a) = gcd(↘a, b) = gcd(a, ↘b) = gcd(a, b ± a)

8 Chapter 1. Divisibility and primes

Proof. We prove that gcd(a, b) = gcd(a, b + a). The other identities are proved a similar way. Let
g1 = gcd(a, b) and g2 = gcd(a, a + b). Since g1 | a and g1 | b we have g1 | a + b so g1 is a common
divisor of a and a + b. It follows that g1 ↔ g2 . Similarly, g2 is a divisor of a and a + b and therefore
also of a and b = (a + b) ↘ a. Hence, g2 ↔ g1 which completes the proof. ↭

The greatest common divisor of two integers a, b can be computed effectively as follows: We
have gcd(a, 0) = gcd(a, ±a) = |a|. If ab ↓= 0, |a| ↓= |b| we may use Proposition 1.2.3 to reduce to
the case a > b > 0. Using Theorem 1.2.1 we write a = bq + r with 0 ↔ r < b. By repeated use of
Proposition 1.2.3 we see that gcd(a, b) = gcd(r, b). If r = 0 we have gcd(a, b) = b. If not we repeat
the above argument with a↗ = b, b↗ = r. This procedure will eventually terminate since r goes down
by at least one in each step. This procedure is called Euclid’s algorithm.
↭ Example 1.2 Consider a = 567 and b = 32. We use Euclid’s algorithm and find

567 = 17 · 32 + 23 so gcd(567, 32) = gcd(23, 32)

32 = 1 · 23 + 9 so gcd(32, 23) = gcd(9, 23)
23 = 2 · 9 + 5 so gcd(23, 9) = gcd(5, 9)
9 = 1·5+4 so gcd(9, 5) = gcd(4, 5)
5 = 1·4+1 so gcd(5, 4) = gcd(1, 4)
4 = 4·1+0 so gcd(4, 1) = gcd(0, 1) = 1,

and we may conclude that gcd(567, 32) = 1. ↭

We see that this procedure constructs integers a0 = a, b0 = r0 = b,

ai = qi bi↘1 + ri (1.1)
with 0 ↔ ri < ri↘1 . This ends when rn = 0 and in this case rn↘1 = gcd(a, b).

Theorem 1.2.4 — Bezout’s identity. Let a, b be integers not both zero. Then there exist an
integer solution x, y ↑ Z to the equation

gcd(a, b) = ax + by.

Proof. One way of proving this is to take the procedure described immediately before the theorem
and then use backwards substitution. Here is another proof that has the advantage of giving an
alternative characterization of gcd(a, b):
Consider
S = {ax + by > 0|x, y ↑ Z} ≃ N
Clearly S is non-empty. Let g = ax0 + by0 ↑ S be its smallest element. Then g | a since if
not a = gq + r with 0 < r < g by Theorem 1.2.1. But since r = a ↘ gq = a ↘ qax0 ↘ by0 q =
a(1 ↘ qx0 ) ↘ by0 q ↑ S this contradicts the minimality of g. By the same argument g | b. Hence g is
a common divisor i.e. g ↔ gcd(a, b).
Clearly gcd(a, b) | ax0 + bx0 = g so gcd(a, b) ↔ g, and we may conclude that gcd(a, b) = g. ↭

R We notice that the proof of Theorem 1.2.4 actually proves that for any a, b ↑ Z we have
gcd(a, b) = min{ax + by > 0|x, y ↑ Z}.
From this observation we easily deduce the following corollary:
 1.3 Diophantine equations 9

Corollary 1.2.5 Let a, b ↑ Z. Then gcd(na, nb) = |n| gcd(a, b).

↭ Example 1.3 In the proof of Theorem 1.2.4 we used the well-ordering principle for N i.e. that
any non-empty subset of the natural numbers contains a smallest element to prove the existence of
solutions to the integer equation gcd(a, b) = ax + by. If we want to actually find such a solution we
may use the procedure described above for finding gcd(a, b) = rn↘1 : We see from (1.1) that we can
express rn↘1 as an integer linear combination of an↘1 and bn↘2 . Doing successive substitution of
the previous equation we arrive at the result.
With the integers from Example 1.2 we find that

gcd(567, 32) = 1 = 5 ↘ 1 · 4
= 5 ↘ 1 · (9 ↘ 1 · 5) = ↘9 + 2 · 5
= ↘9 + 2 · (23 ↘ 2 · 9) = 2 · 23 ↘ 5 · 9
= 2 · 23 ↘ 5 · (32 ↘ 23) = ↘5 · 32 + 7 · 23
= ↘5 · 32 + 7 · (567 ↘ 17 · 32) = 7 · 567 ↘ 124 · 32,

so we find a solution x = 7, y = ↘124. ↭

Definition 1.2.2 Let a, b ↑ Z. We call a, b coprime or relatively prime if gcd(a, b) = 1.

Proposition 1.2.6
(i) The integers a, b are coprime if and only if 1 = ax + by for some x, y ↑ Z.
(ii) Let d = gcd(a, b). Then the integers a/d and b/d are coprime.
(iii) Assume a, b are coprime and a | c and b | c. Then ab | c.
(iv) Assume a, b are coprime and a | bc. Then a | c.

Proof. The claim in (i) follows directly from the remark after Theorem 1.2.4. The remaining 3
claims all use (i).
To prove (ii) we use again Theorem 1.2.4 and divide ax + by = d by d. Then (i) proves the
claim. To see (iii) we note that on the assumptions we have c = ea and c = f b so by (i) we have
c = c(ax + by) = f bax + eaby = ab( f x + ey) which proves the claim. To prove (iv) we note if
a, b are relatively prime and bc = da then by (i) we have c = c(ax + by) = cax + day = a(cx + dy)
which shows that a | c. ↭

1.3 Diophantine equations

Let p(X1 , . . . , Xn ) ↑ Z[X1 , . . . , Xn ] be a polynomial in n variables with integer coefficients. We
want to find integer solutions to the equation p(X1 , . . . , Xn ) = 0. Such equations are usually called
Diophantine equations and they are of central importance in number theory.

1.3.1 Linear equations

We are now ready to discuss this in the simplest possible case namely the case p(X,Y ) = aX +bY ↘c
where a, b, c ↑ Z:

Theorem 1.3.1 Assume a, b, c ↑ Z with a, b not both zero. Let d = gcd(a, b). Then the equation

ax + by = c

has integer solutions if and only if d | c. If d | c the complete solution consists of all pairs of the
10 Chapter 1. Divisibility and primes

form ! "
c b a
(x, y) = (x0 , y0 ) + n · ,↘
d d d
where n ↑ Z. Here (x0 , y0 ) is any particular solution to ax + by = gcd(a, b).

Proof. If an integer solution (x, y) exists then since d divides a and b it also divides ax + by = c.
If on the other hand d | c then we pick a solution (x0 , y0 ) of ax0 + by0 = d which is possible by
Bezout’s identity (Theorem 1.2.4). It is then clear that dc (x0 , y0 ) is a solution to ax + by = c. Let
now (x, y) be any integer solution. Then (u, v) = (x, y) ↘ dc (x0 , y0 ) is an integer solution to
au + bv = 0
and therefore also to
a b
u+ v = 0 (1.2)
d d
It follows from Proposition 1.2.6 (ii) that a/d and b/d are coprime. By Proposition 1.2.6 (iv) we
can conclude that b/d | u, i.e. u = nb/d for some n ↑ Z. Substituting back into 1.2 we find that
v = ↘(a/d)n. We have now proved that any integer solution is of the form
! "
c b a
(x, y) = (x0 , y0 ) + n ,↘
d d d
for some integer n. It is easy to see – by direct verification – that all such integer pairs are indeed
solutions. ↭
↭ Example 1.4 We find all solution to
1485x + 1745y = 15
We start by finding the greatest common divisor of 1485 and 1745. Using division with remainder
we have
1745 = 1 · 1485 + 260
1485 = 5 · 260 + 185
260 = 1 · 185 + 75
185 = 2 · 75 + 35
75 = 2 · 35 + 5
35 = 7 · 5 + 0
so by the discussion before Theorem 1.2.4 we have gcd(1485, 1745) = 5, and since 5 | 15 there are
infinitely many solutions. Doing backwards substitution we find
5 = 75 ↘ 2 · 35
= 75 ↘ 2(185 ↘ 2 · 75) = 5 · 75 ↘ 2 · 185
= 5 · (260 ↘ 185) ↘ 2 · 185 = 5 · 260 ↘ 7 · 185
= 5 · 260 ↘ 7 · (1485 ↘ 5 · 260) = 40 · 260 ↘ 7 · 1485
= 40 · (1745 ↘ 1485) ↘ 7 · 1485
= 40 · 1745 ↘ 47 · 1485
Using Theorem 1.3.1 we find that the complete solution is
! "
1745 1485
(x, y) = 3 · (↘47, 40) + n ,↘ = (↘141, 120) + n · (349, ↘297)
5 5
↭
 1.4 Primes 11

1.4 Primes
We recall the definition of primes:
Definition 1.4.1 A natural number p > 1 is called a prime if its only divisors are 1 and p. A
natural number n > 1 which is not a prime is called a composite number.

We note that by this definition 1 is neither composite or prime. Historically 1 has been considered a
prime for a long time, but certain theorems become easier to formulate if this is not so.
↭ Example 1.5 This is the first 100 primes: 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,-
179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,-
293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421,-
431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541.
Short lists like this can be easily found by hand. For a given n we note that if n is composite
⇐
then n = ab where either a or b is at most n. Hence if we have checked that n has no factors less
⇐
than n it must be prime. (See Exercise 1.8). Using Eratosthenes’ sieve we can find a complete list
of small primes. Much longer lists can be found online e.g. at primes.utm.edu. ↭

R There is a very clever algorithm (published in 2004) based on Fermat’s little theorem (See
Corollary 2.3.2) which checks whether a number is prime or not. The algorithm is called
AKS after its inventors Agrawal, Kayal and Saxena. We will encounter several algorithms
later which verifies whether a number is prime or not, but a major interest in AKS is that it is
the first algorithm that provably runs in ‘computational time’ bounded by a polynomial in
log(p) where p is the number we want to investigate if it is a prime or not. Hence the required
time is polynomial in the number of digits of p. For more information see [AKS04; Gra05].

Maybe the most important fact about prime numbers is the fundamental theorem of arithmetic.
The crucial result we need to prove it, uses the divisibility results from Section 1.2:
Lemma 1.4.1 — Euclid. Let a, b ↑ Z and assume p is a prime. If p | ab then p | a or p | b.

Proof. If p | a we are done. Assume not: Then gcd(p, a) = 1, for if gcd(p, a) ↓= 1 then since 1, p
are the only divisors of p then gcd(p, a) = p which in particular means that p | a but we have
assumed this not to be the case, i.e. gcd(p, a) = 1. Using Bezout (Theorem 1.2.4) we find that there
exist integers x0 , y0 such that x0 p + y0 a = 1. Multiplying this by b we find that

x0 pb + y0 ab = b

Since p | ab we see that p | b which finishes the proof. ↭

1.4.1 The fundamental theorem of arithmetic

We are now ready to prove the main result:

Theorem 1.4.2 — The fundamental theorem of arithmetic. Every natural number n > 1 can
be written as a product of primes. The product is unique up to permutation of terms.

We interpret 1 as being written as the empty product over primes.

Proof. Let X ≃ N be the set of natural numbers which can not be written as a product of primes. To
see that X is the empty set assume that it is not, and let n be its smallest member. Then n cannot be
a prime (then it is clearly a product of primes), so it has a factorization n = ab where a, b < n. But
by minimality a, b are not in X so they can both be written as a product of primes, which implies
12 Chapter 1. Divisibility and primes

that n is a product of primes. But then n is not in X which shows that X is the empty set. Hence
every n > 1 can be written as a product of primes.
To show that such a product is unique we assume that

p1 p2 · · · pd = q1 · · · ql

By successive use of Lemma 1.4.1 we find that pd = q j for some j = 1, . . . l. By possibly renaming
the qi ’s we may assume that pd = ql . Cancelling by ql we find

p1 p2 · · · pd↘1 = q1 · · · ql↘1

Repeating this argument d times we find

1 = q1 · · · ql↘d

But this is only possible if l = d, which means we have removed all primes q j on the right. The
claim follows. ↭

R The fundamental theorem of arithmetic says that every natural number can be factored
in primes. Is factoring a given number n ‘easy’or ‘hard’? We discussed earlier that the
AKS-algorithm determines whether a number n is prime or not, and does so in polynomial
time in the digits of n, i.e. determining whether a number is prime is ‘easy’. If n is not a
prime the AKS algorithm does not give a factorization of n. It is a big unsolved problem if
there exist a polynomial time algorithm which factors n. There is an algorithm due to Schor
[Sho94; Sho97] which can do prime factorizations on quantum computers in polynomial time.
However quantum computing is still in its infancy, so this has not had great practical use so
far. As we shall see later some of the most used cryptosystems like RSA relies on the fact
that no one knows how to factor ‘easily’.

Theorem 1.4.3 There are infinitely many prime numbers.

Proof. We will construct infinitely many prime numbers recursively. 2 is a prime. Assume now
that we have a list of n primes p1 , p2 , . . . pn . Multiplying them together, adding 1, and then using
the fundamental theorem of arithmetic (Theorem 1.4.2) we have

p1 p2 · · · pn + 1 = q1 q2 . . . ql (1.3)

where q1 , . . . ql are (not necessarily distinct) primes. We now notice that q j ↓= pi for all i, j since
if pi = q j = p then by (1.3) we find p | 1 which is impossible. Letting pn+1 be the smallest of the
q j ’s we have added one extra prime to our list. Doing this recursively we see that we can construct
arbitrarily many primes. ↭

The first few terms in the sequence of primes constructed in the proof of Theorem 1.4.3 are

2, 3, 7, 43, 13, 53, 5, 6221671, 38709183810571, 139, 2801, 11, 17, 5471, 52662739, . . .

This is usually called the Euclid-Mullin sequence.

Conjecture 1.4.4 The Euclid-Mullin sequence contains all primes.
The numerical evidence for this conjecture is very sparse. Only the first 51 terms are known
(the last term found September 2012). For primes less than 100 we do not know if 41, 47, 67, 73,
79, 83 are in the Euclid-Mullin sequence.
 1.4 Primes 13

Even if we know that there are at infinitely many primes we have of course only explicitly
computed finitely many. The largest known prime is 282589933 ↘ 1 which is a monstrous number with
24862048 decimal digits. It was found in December 2018. If you want to join the prime-finding
community go to GIMPS or PrimeGrid. The only thing you have to do is to run a piece of software
on your computer.
It was fairly straightforward to prove that there are infinitely many primes. Consider two
coprime integers a and b. Then it is natural to ask if there are infinitely many primes of the form
an + b i.e. infinitely many primes which has remainder b if we divide by a. This is indeed so, but
except for a few simple choices of a and b this turns out to be significantly harder to prove. It was
first proved by Dirichlet more that 2000 years after Euclid’s result (Theorem 1.4.3). See [Apo76,
Thm 7.9] for an accessible proof.

1.4.2 On the number of primes less than a given size

Consider the function #(x) which counts the number of primes less than a given size

#(x) = #{p ↔ x|p prime}.

where x is any real number. Theorem 1.4.3 can be formulated as #(x) ⇒ ! as x ⇒ !. The
proof of Theorem 1.4.3 can be used to show a bit more. One can use the proof to see that
#(x) → log2 (log2 (x)) (See Exercise 1.13). Much more is true: By a relatively elementary argument
one can show that for x > 2 we have #(x) → 16 log(x)
x
([Apo76, Thm 4.6]) as well as an analogous
x
upper bound 6 log(x) . Riemann was probably the first to fully understand the link between #(x) and
the Riemann zeta function
!
1
∃ (s) = ∀ ns when #(s) > 1,
n=1

which we shall study more in Chapter 5. Hadamard and de la Vallée Poussin proved in 1896, using
Riemann’s insights, that in fact
x
#(x) ⇑ , (1.4)
log(x)

meaning that the quotient of the two sides converges to 1 as x ⇒ !. This result is called the prime
number theorem and its validity was conjectured independently by Gauss and Legendre 100 years
earlier. The prime number theorem is very powerful, but we expect a much stronger result to be
true: The Riemann hypothesis, which is usually stated in terms of the zeros of ∃ (s), is equivalent to
the following conjecture:
# x
1
Conjecture 1.4.5 For every ! > 0 we have #(x) ↘ dt = O(x1/2+! ).
2 log(t)

1.4.3 Pythagorean triples

We now discuss another example of a Diophantine equation: Consider the polynomial equation

P(X,Y, Z) = X 2 +Y 2 ↘ Z 2 = 0.

By Pythagoras’ theorem solutions with X,Y, Z > 0 to this equation corresponds to side lengths in
right triangles. Given an integer solution (e.g. (X,Y, Z) = (3, 4, 5)) we can always multiply this by
an integer m and get another integer solution (mX, mY, mZ). Such solutions will always have m as
a common factor. Solutions (X,Y, Z) without common factor are called primitive. Note that if two
of X, Y , Z has a common factor the third has the same factor.
14 Chapter 1. Divisibility and primes

Observe now that no primitive solution has Z = 0, and if (X,Y, Z) is a primitive solution then
(X,Y, ↘Z) is also a primitive solution. Since X and Y has no common factor they cannot both be
even. We claim that they also cannot both be odd. If they were then Z 2 would be of the form 2 + 4k
for some k. But no perfect square is of this form, so one of X, Y is even and the other is odd. Given
a primitive solution (X,Y, Z) we have that (Y, X, Z) is also a solution and this mapping interchanges
the primitive solutions with X even with the primitive solutions with X odd.
We now parametrize all primitive solutions.

Theorem 1.4.6 The primitive integer solution to the equation

X 2 +Y 2 = Z 2 (1.5)

with X odd, Y even and Z > 0 are exactly the triples

(X,Y, Z) = (p2 ↘ q2 , ↘2pq, p2 + q2 )

where p, q are coprime integers with p → 0 satisfying p ↘ q is odd.

Proof.
We recall that there is a bijection between primitive solution of (1.5) and the rational points on
the unit circle, i.e. rational solutions of the equation
X 2 +Y 2 = 1.
This is seen as follows:
Given a primitive solution x2 + y2 = z2 with z > 0 then (X,Y ) = (x/z, y/z) is a rational number
on the unit circle. Furthermore given a rational point (X ↗ ,Y ↗ ) = (x↗ /z↗ , y↗ /w↗ ) with z↗ , w↗ > 0 on the
unit circle then consider (x↗ w↗ )2 + (y↗ z↗ )2 = (z↗ w↗ )2 . It is immediate from Proposition 1.2.2 that if
two of the three numbers x↗ w↗ , y↗ z↗ , and z↗ w↗ has a common factor then so does the third. Hence
we can divide by this common factor m . It follows that we can write (X ↗ ,Y ↗ ) = (a/c, b/c) where
(a, b, c) is a primitive solution to (1.5) with c > 0. The Pythagorean triples with X odd and Y even
correspond exactly to those rational points on the circle (a/c, b/c) with a odd and b even.
We now parametrize all rational points on the unit circle. Consider P = (1, 0) and another
rational point Q = (q1 , q2 ) ↓= P on the unit circle. Then the line between them y = %(x ↘ 1) has
rational slope % = q2 /(q1 ↘1). On the other hand, given a rational slope % ↑ Q the line y = %(x↘1)
and x2 + y2 = 1 intersects at a point Q which satisfies
x2 + % 2 (x ↘ 1)2 ↘ 1 = (1 + % 2 )x2 ↘ 2% 2 x + % 2 ↘ 1 = 0
which has the two solutions
$
2% 2 ± 4% 4 ↘ 4(1 + % 2 )(% 2 ↘ 1) 2% 2 ± 2 %2 ↘ 1
= = 1, .
2(1 + % 2 ) 2(1 + % 2 ) %2 + 1
In particular we note that Q has rational coordinates:
! 2 "
% ↘ 1 ↘2%
Q= , .
%2 + 1 %2 + 1

Q
P
 1.5 Exercises for Chapter 1 15
% 2 2 &
If % = qp is an irreducible fraction with p → 0, we find that Q = pp2 ↘q , ↘2pq . It is straight-
+q2 p2 +q2
forward to see that the second coordinate is of the form b/c with b even precisely if p ↘ q is odd.
By the above discussion the result follows. The Pythagorean triple (1, 0, 1) is covered by p = 1,
q = 0 which corresponds to % = !. ↭
The above theorems might give the impression that it is relatively straightforward to determine
if integer polynomial equations have integer solutions. This is wrong. Most often it is very difficult
to determine all integer solutions. To illustrate this consider Fermat’s equation
xn + yn = zn , for n → 3.
It took almost 400 years between 1637 when Fermat thought that he had proved that this does not
have any integer solutions satisfying xyz ↓= 0 until A. Wiles (and his collaborators) finally found a
definitive proof in 1995.

1.5 Exercises for Chapter 1

Exercise 1.1 Compute gcd(455, 1235).
Exercise 1.2 Find all integer solutions to 455x + 1235y = 130.
Exercise 1.3 Find all integer solutions to 455x + 1235y = 143.
Exercise 1.4 What are the possible reminders when dividing a square n2 by 3? By 4? By 5? By 6?
Exercise 1.5 Prove Proposition 1.1.1
Exercise 1.6 In each of the following, apply the division algorithm to find q and r such that
a = bq + r with 0 ↔ r < |b|:
(a, b) = (302, 19), (a, b) = (829, 31), (a, b) = (300, ↘17), , (a, b) = (449, 4),
Exercise 1.7 Prove Theorem 1.2.1 in the case a = 0. !1
Exercise 1.8 Prove that n ↑ N with n > 1 is a prime if and only if n has no non-trivial factors less
⇐
than or equal to n.
Exercise 1.9 Find all integer solution to 1485x + 1745y = gcd(1485, 1745).
Exercise 1.10 Show that Proposition 1.2.6 (iii), (iv) fails if we do not assume a, b to be coprime.
Exercise 1.11 — Eratosthenes’ Sieve. Assume that P = {p1 , p2 , . . . pk } are the smallest k primes.
Erase from the list pk +1, pk +2, . . . , p2k all multiples of p1 , p2 , . . . pk and add the remaining numbers
to P. Show that P now contains all prime numbers less than p2k . This may be used to easily find
complete lists of primes of moderate size. !
Exercise 1.12 Find, using nothing put pen and paper, all primes less than 200.
Exercise 1.13 Let pn be the n-th prime, and let #(x) = #{pn ↔ x}. Show that #(x) → ⇓log2 (log2 (x))⇔+
n↘1
1. (Hint: Use Theorem 1.4.3 to show that pn ↔ 22 .) !
Exercise 1.14 Show that there are infinitely many primitive Pythagorean triangles, i.e. right
triangles whose side lengths are integers and pairwise coprime.
Exercise 1.15 Prove Proposition 1.2.2 using the theory of primes.
Exercise 1.16 Show that there are infinitely many primes of the form 4n ↘ 1. (Hint: Assume
p1 , . . . pn are of the desired form and consider the prime factorization of 4p1 · · · pn ↘ 1)
Exercise 1.17 Prove that no integer in the sequence 11, 111, 1111, . . . is a perfect square.
Hint: What are the possible remainders when dividing a perfect square by 4?
Exercise 1.18 Assume that ab ↘ 1 is a prime where a, b ↑ N with b → 2. Show that a = 2 and b
is prime. Primes of this form are called Mersenne primes. Most of the largest known primes are
Mersenne primes.
Exercise 1.19 Show that there does not exist a Pythagorean triple (x, y, z) where x, y, z are all
primes.
1 The ! means that it might be a good idea to serve yourself a nice beverage.
 2. Modular arithmetic

2.1 Basic structures

We recall the definition of a ring
Definition 2.1.1 A ring R is a set with two binary operations +,· (usually called addition and
multiplication), and two elements 0, 1 ↑ R such that
(i) (R, +, 0) is an abelian group, and for every a, b, c ↑ R we have
(ii) 1 · a = a · 1 = a, i.e 1 is a multiplicative identity,
(iii) (a · b) · c = a · (b · c), i.e. multiplication is associative,
(iv) a · (b + c) = a · b + a · c, i.e. multiplication is distributive from the right,
(v) (a + b) · c = a · c + b · c, i.e. multiplication is distributive from the left.

↭ Example 2.1 The following are all examples of rings

• Z, Q, R, C (with the usual two binary operations +, ·) are all examples of commutative (or
abelian) rings, i.e. rings where the multiplication is commutative.
• Let n > 1. The set of n by n matrices with coefficients in Z, Q, R, or C denote Mn (Z), Mn (R),
Mn (Q) , and Mn (C) equipped with the usual matrix addition and matrix multiplication are all
examples of non-commutative rings. In this course we will almost exclusively be considering
commutative rings.
• Let n ↑ N. The set of equivalence classes of integers modulo n, Z/nZ with addition and
multiplication defined by
(a + nZ) + (b + nZ) := (a + b) + nZ
(a + nZ) · (b + nZ) := a · b + nZ
It is straightforward to verify that these operations are well-defined and that they make Z/nZ
a commutative ring. You have already seen in your basic algebra course that (Z/nZ, +) is an
abelian group. We shall use both a + nZ, [a]n , and a mod n to denote the equivalence class a
modulo n. If, on the other hand, we write a = b (mod n) we mean that n | (a ↘ b) which is
equivalent to the equivalence classes a mod n and b mod n being equal.
↭
 2.2 Modular arithmetic 17
Definition 2.1.2 Let R be a ring and let a ↑ R. We say that a is invertible or that it is a unit if
there exists a b ↑ R such that ab = ba = 1. The set of invertible elements is denoted by R↖ .

Notice that if a is invertible then a corresponding b is uniquely determined: If both ab = ba = 1 and

ab↗ = b↗ a = 1 then b = b(ab↗ ) = (ba)b↗ = b↗ . We denote this element by a↘1 . We notice also that if
a, b, c ↑ R with c invertible then ac = bc implies a = b by multiplication from the right with c↘1 .
It is straightforward to verify the following proposition (See Exercise 2.1) :
Proposition 2.1.1 Let (R, +, ·) be a ring. The set (R↖ , ·) of invertible elements with · is a group.
↭ Example 2.2 We have
• Z↖ = {±1}, Q↖ = Q\{0}, R↖ = R\{0} , C↖ = C\{0}.
• We have

(Z/nZ)↖ = {x mod n ↑ Z/nZ| gcd(x, n) = 1}. (2.1)

It follows from Proposition 1.2.3 that the set on the right is well-defined. If x mod n ↑ Z/nZ
is invertible then there exist y mod n ↑ Z/nZ such that xy = 1 + kn for some k ↑ Z. But
then by Proposition 1.2.6 (i) we have gcd(x, n) = 1. On the other hand if gcd(x, n) = 1
then again by Proposition 1.2.6 (i) there exist y, k such that 1 = yx + kn which shows that
(x mod n) · (y mod n) = 1 mod n.
↭

Definition 2.1.3 Let R be a ring. If all non-zero elements are invertible then R is called a division
ring or a skew field. If additionally R is commutative then R is called a field.

↭ Example 2.3 By Example 2.2 we see that Q, R, C are fields and Z/nZ is a field if and only if
n = p is a prime. This field is usually denoted F p . ↭

2.2 Modular arithmetic

We will investigate further the ring Z/nZ.
Proposition 2.2.1 The equation

ax = b (mod n) (2.2)

has a solution if and only if gcd(a, n) | b.

Proof. Let g = gcd(a, n). Assume x is a solution. Then n | ax ↘ b so ax ↘ b = nc for some integer
c and hence g | b. Assume on the other hand g | b. Note that by Proposition 1.2.6 (ii) we have
gcd(a/g, n/g) = 1. By (2.1) a/g is a unit in Z/(n/g)Z, so there exists a y such that ya/g = 1+kn/g.
Multiplying by b we find that x = yb/g solves (2.2). ↭

↭ Example 2.4 • Note that x = 4 (mod 8) and x = 0 (mod 8) are two different solutions to
2x = 0 (mod 8). Hence there is not necessarily uniqueness in Proposition 2.2.1.
• Consider solutions to 3x = 7 (mod 5). Euclidean division gives

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

so gcd(5, 3) = 1 and 1 = 3 ↘ 2 = 3 ↘ (5 ↘ 3) = 2 · 3 ↘ 5. It follows that 3↘1 = 2 (mod 5) so

we may multiply by 2 to find the unique solution x = 2 · 7 = 4 (mod 5).
↭
 18 Chapter 2. Modular arithmetic

2.3 Euler’s ∀-function

We now consider the function

∀(n) = # (Z/nZ)↖ = #{1 ↔ a ↔ n| gcd(a, n) = 1} (2.3)

called Euler’s ∀-function.

↭Example 2.5 If we want to find ∀(6) we have to count how many of 1, 2, 3, 4, 5 are coprime to 6.
But this is is exactly 1, 5, so ∀(6) = 2. ↭

It is obvious that ∀(1) = 1. It follows from Example 2.3 that if p is a prime ∀(p) = p ↘ 1.
More generally we have

∀(pn ) = pn ↘ pn↘1 = pn (1 ↘ p↘1 ). (2.4)

To see this we note that we are counting all the numbers 1, 2, . . . , pn except for those that have
a factor in common with pn . But if gcd(a, pn ) > 1 then using that p is a prime we see that
gcd(a, p) > 1 which means that p divides a. Hence the numbers we are excluding are exactly
p, 2p, 3p, . . . , pn and the claim follows.

Theorem 2.3.1 — Euler. Assume gcd(x, n) = 1. Then x∀(n) = 1 (mod n).

Proof. From basic algebra we have Lagrange’s theorem which implies that for a finite group G we
have g#G = 1. Applying this to G = (Z/nZ)↖ gives the result by (2.1) and (2.3). ↭

Corollary 2.3.2 — Fermat’s little theorem. Let p be a prime. Then a p = a (mod p) for every
a ↑ Z.

Proof. For p | a both sides are zero and the claim is trivial. For p ⊋ a we have gcd(a, p) = 1 and
Euler’s theorem and (2.4) gives that a p↘1 = 1 (mod p). Multiplying by a gives the result. ↭

We note that the above proof is somewhat anachronistic. Historically Lagrange’s theorem was
a generalization of Fermat’s little theorem. For a more elementary proof of Euler’s theorem we
can argue as follows: Since gcd(x, n) = 1 multiplication by x gives a permutation of the elements
G = {a mod n|gcd(a, n) = 1}. It follows that

∃ ax = ∃ a (mod n).
a↑G a↑G

Since gcd(∃a↑G a, n) = 1 it follows from Bezout’s theorem that there exists an integer b such that
b ∃a↑G a = 1 (mod n). Multiplying by this b finishes the proof of Theorem 2.3.1 .

2.3.1 The Chinese remainder theorem

In order to find the values of Euler’s ∀-function on general integers we need the Chinese remainder
theorem.
Theorem 2.3.3 — The Chinese remainder theorem. Let a1 , . . . al ↑ Z and let n1 , . . . , nl be
pairwise coprime. Then the system of l equations

x = ai (mod ni ), i = 1, . . . , l

has an integer solution. This solution is unique modulo n1 · · · nl .

2.3 Euler’s ∀-function 19

Proof. For l = 1 the claim is clear: Choose x = a1 . Assume l = 2 and consider the equation in t
given by
a1 + n1 t = a2 (mod n2 ).
As gcd(n1 , n2 ) = 1 Proposition 2.2.1 ensures that there is a solution to this. Indeed we may take
t = (a2 ↘ a1 )n↘1
1 (mod n2 ). Letting x = a1 + n1t we find that this solves the two equations. Assume
two solutions x, y. Then subtracting them we find that x ↘ y = 0 (mod ni ). Then by Proposition
1.2.6 (iii) we have that n1 n2 | x ↘ y which shows uniqueness modulo n1 n2 .
Assume now that the theorem holds for a given l. Then we want to show that it holds also for
l + 1. So assume we have a solution to
x = ai (mod ni ), i = 1, . . . , l
Then we want to show that we can find a solution to
y = ai (mod ni ), i = 1, . . . , l + 1
We consider now the equation
x + tn1 n2 · · · nl = al+1 (mod nl+1 ) (2.5)
As gcd(n1 · · · nl , nl+1 ) = 1 Proposition 2.2.1 ensures that there is a solution to this. Indeed we may
take t = (al+1 ↘ x)(n1 · · · nl )↘1 (mod nl+1 ). Letting y = x + tn1 n2 · · · nl we find that this solves all
l + 1 equations. Uniqueness is proved like the case l = 2. ↭

↭Example 2.6 The Chinese mathematician Sun Tzu asked in a late 3rd century book for the
smallest solution to the equations
x = 2 (mod 3)
x = 3 (mod 5)
x = 2 (mod 7).
Using Theorem 2.3.3 we see immediately that a solution exist. Recalling the proof we see that in
order to solve the two first equations we solve, in t the equation
2 + t · 3 = 3 (mod 5).
We easily find that t = 2 solves this, and hence 2 + 2 · 3 = 8 is a solution of the two first equations.
To get a solution of all three equations we need to solve in t the equation
8+t ·3·5 = 2 (mod 7).
Since 15 = 1 (mod 7) we find that t = ↘6 = 1 (mod 7) solves the equation, and x = 8 + 1 · 15 = 23
solves all three equations. Since all solution are of the form x = 23 + k · 3 · 5 · 7 (and all integers of
this form are indeed solutions), this is also the smallest solution. ↭

R Note that the proof given for the Chinese remainder theorem above is constructive. A shorter
non-constructive proof can be given as follows: Consider
& : Z/n1 · · · nl Z ⇒ Z/n1 Z ↖ · · · Z/nl Z
(2.6)
c mod n1 · · · nl ↙⇒ (c mod n1 , . . . , c mod nl )
which is well-defined. It is also injective, for if c mod ni = 0 for all i = 1, . . . l , then by
Proposition 1.2.6 (iii) we have c mod n1 · · · nl = 0. Since the domain and the codomain have
the same number of elements this map must also be surjective, which is a reformulation of
the Chinese remainder theorem.
 20 Chapter 2. Modular arithmetic

Lemma 2.3.4 Let m, n be coprime integers. The mapping between groups

& : (Z/mnZ)↖ ⇒ (Z/mZ)↖ ↖ (Z/nZ)↖

c mod mn ↙⇒ (c mod m, c mod n)

is a bijection.

Proof. Notice that the map is independent of choice of representative. Note also that if c mod mn ↑
(Z/mnZ)↖ then gcd(c, mn) = 1. It follows that gcd(c, n) = 1 since gcd(c, n) | gcd(c, mn) = 1. The
same argument shows that gcd(c, m) = 1. It follows that &(c mod mn) ↑ (Z/mZ)↖ ↖ (Z/nZ)↖ so
the map is indeed well-defined.
As & is the restriction to (Z/mnZ)↖ of the bijection & from (2.6) it follows that & is injective.
To see that it is surjective we have to show that if &(c mod mn) ↑ (Z/mZ)↖ ↖ (Z/nZ)↖ then
c mod mn ↑ (Z/mnZ)↖ . But assume that a prime p | gcd(c, mn). Then by Euclid’s lemma (Lemma
1.4.1) we have p | m or p | n. But this means that p | gcd(c, m) = 1 or p | gcd(c, n) = 1 which
cannot be the case. So no such prime exists, and we have gcd(c, mn) = 1 which shows that
c mod mn ↑ (Z/mnZ)↖ . Hence & is surjective, which finishes the proof. ↭

In fact a bit more is true. One can show that & is a group isomorphism. Indeed & is a ring
isomorphism (we have not defined what this means) but since we do not need it we settle for the
above statement. We need it to be able to conclude the following:

Corollary 2.3.5 Let m, n be coprime integers. Then ∀(mn) = ∀(m)∀(n).

Proof. This follows immediately from Lemma 2.3.4, and the definition of ∀. ↭

Combining Corollary 2.3.5 with (2.4) we find immediately that

∀(n) = n ∃(1 ↘ p↘1 ). (2.7)

p|n

2.4 Primitive roots modulo n.

Recall that if g is an element of a group G then the order of g, ord(g), is the smallest natural number
n such that gn is the neutral element of the group. By Lagrange theorem the order of a group
element divides the group order #G. We know also that if gm equals the neutral element in G then
ord(g) | m as can be proved by Euclidean division.
Definition 2.4.1 Let n be a natural number. An integer a ↑ Z is called a primitive root modulo
n if a mod n ↑ (Z/nZ)↖ has order ∀(n).

↭ Example 2.7 Recall Example 2.5. We have (5 mod 6)2 = 25 mod 6 = 1 mod 6. It follows that
5 mod 6 has order 2 = ∀(6). I.e. 5 is a primitive root modulo 6. ↭

Note that if a is a primitive root mod n then by the definition of ∀(n) we have that (Z/nZ)↖ is
cyclic with a mod n being a generator. It is a natural question to ask whether to a given n primitive
roots modulo n exist. We will prove that if n is prime this is indeed the case. In order to prove this
we need to study roots of polynomials:

2.4.1 Roots of polynomials.

Consider the polynomial f (x) = x2 ↘ 1 ↑ (Z/8Z)[x]. It is straightforward to verify that this has
roots 1, 3, 5, 7 mod 8. Hence this is an example of a degree 2 polynomial with 4 roots. If we are
working over a field polynomials cannot have such an abundance of roots.
2.4 Primitive roots modulo n. 21

Proposition 2.4.1 Let k be a field and let 0 ↓= f ↑ k[x] be a polynomial over k. Then f has at most
deg( f ) roots.
We note that f (x) = x2 ↘ 2 ↑ (Z/3Z)[x] has no roots in Z/3Z since modulo 3 we have f (0) =
↘2, f (1) = ↘1, f (2) = 2.

Proof. The proof is induction in deg( f ). For polynomials of degree 0, i.e. constants, the claim is
clear. Assume now that the claim holds for polynomials of degree at most n. Let

f (x) = an+1 xn+1 + · · · a1 x1 + a0 ↑ k[x]

be a polynomial of degree n + 1. If there are no roots in k we are done. So assume % ↑ k is a root.

Then

f (x) = f (x) ↘ f (%) = an+1 (xn+1 ↘ % n+1 ) + · · · a1 (x1 ↘ %)

Since xi ↘ % i = ∀i↘1 j i↘1↘ j (x ↘ %) this implies that f (x) = (x ↘ %)g(x) where deg(g) ↔ n.
j=0 x %
If ∋ ↓= % is a root of f then 0 = (∋ ↘ %)g(∋ ) and since ∋ ↘ % ↓= 0 we may multiply by its
inverse (since k is a field) and find g(∋ ) = 0. By induction hypothesis this can be true for at most n
different ∋ and it follows that f has at most n + 1 roots. ↭

Recall that if p is a prime then F p = Z/pZ is a field.

Proposition 2.4.2 Let p be a prime and d a divisor of p ↘ 1. Then f (x) = xd ↘ 1 ↑ F p [x] has exactly
d roots.

Proof. Write p ↘ 1 = dl, and consider e(x) = x p↘1 ↘ 1 ↑ F p [x]. By Euler’s theorem (Theorem
2.3.1) all non-zero elements of F p are roots of this polynomial, i.e. it has p ↘ 1 different roots. We
notice also the factorization

e(x) = (xd )l ↘ 1 = (xd ↘ 1)((xd )l↘1 + (xd )l↘2 + · · · + 1) = f (x)g(x),

where g(x) ↑ F p [x] has degree p ↘ 1 ↘ d. By Proposition 2.4.1 f has at most d roots and g has at
most p ↘ 1 ↘ d roots but since their product has p ↘ 1 different roots f must have at least d roots
and g must have at least p ↘ 1 ↘ d roots which proves the claim. ↭

Lemma 2.4.3 Let G be a group. Assume g1 , g2 ↑ G are commuting elements with coprime finite
orders n1 ,n2 . Then their product g1 g2 has order n1 n2 .

Proof. Let n = ord(g1 g2 ). Since g1 and g2 commutes (g1 g2 )n1 n2 = (gn11 )n2 (gn22 )n1 = 1 so n | n1 n2 .
On the other hand we have gn1 gn2 = 1. Raising this to the n2 ’th power and using gn22 = 1 we find
gnn
1 = 1 so n1 | nn2 . Since n1 and n2 are coprime we get from Proposition 1.2.6 (iv) that n1 | n. A
2

similar argument shows that n2 |n, which then by Proposition 1.2.6 (iii) implies that n1 n2 | n. Hence
we have n = n1 n2 . ↭

We are now ready to prove the main result of this section.

Theorem 2.4.4 Primitive roots modulo p exist for every prime number p.

Proof. By the fundamental theorem of arithmetic we can factor ∀(p) = p ↘ 1 = pl11 · · · plkk into a
product of powers of distinct primes. If we can show that for every i = 1, . . . k, we can find an
li
element ai of F↖
p with order pi , then by successive use of Lemma 2.4.3 we find that a = a1 a2 . . . ak
has order ∀(p) which proves that there exists a primitive root modulo p.
To show that there exists an elements of order plii , we observe that by Proposition 2.4.2 we see
li
that there are plii ↘ plii ↘1 elements of order plii since the roots of x pi ↘ 1 = 0 which are not roots of
 22 Chapter 2. Modular arithmetic
l
li ↘1 pi
x pi ↘ 1 = 0 have order plii : For such a root ai satisfies ai i = 1 so ord(ai ) | plii i.e. ord(ai ) = pli for
li ↘1
some 0 ↔ l ↔ li . But if l < li then ai is a root of x pi ↘ 1 = 0 which we have assumed it is not.
This finishes the proof. ↭

p of order ∀(p) = #F p we conclude the

Since a primitive root modulo p induces an element in F↖ ↖

following corollary:

Corollary 2.4.5 Let p be a prime. Then F↖

p is cyclic.

Theorem 2.4.4 settles the question of the existence of primitive roots modulo primes. There are
no primitive roots modulo 8 (Exercise 2.2), so some restriction on n needs to be assumed. It turns
out that primitive roots modulo n exists precisely if n = 2, 4, pe , or 2pe where p is any odd prime
and e ↑ N. We shall not prove this but please consult [JJ98, Theorem 6.7] for an accessible proof.
Proposition 2.4.6 Let n be a natural number and assume that there exist primitive roots modulo n.
Then ∀(∀(n)) of the numbers 1, 2, . . . , n ↘ 1 are primitive roots modulo n.

Proof. If a is a primitive root modulo n then a (mod n) is a generator of (Z/nZ)↖ . We see the
number we are looking for equals the number of 1 ↔ r ↔ ∀(n) where ar (mod n) is a generator of
(Z/nZ)↖ . But ar (mod n) is a generator precisely if for every 1 ↔ c ↔ ∀(n) the equation ary = ac
(mod n) has a solution. This happens precisely if ry = c (mod ∀(n)) has a solution. But by
Proposition 2.2.1 this happens precisely if gcd(r, ∀(n)) | c for all c which happens precisely if
gcd(r, ∀(n)) = 1. Hence we are counting the number of elements in the set

{1 ↔ r ↔ ∀(n)| gcd(r, ∀(n)) = 1}

which is exactly ∀(∀(n)). ↭

R We remark that the proof of Proposition 2.4.6 shows that if a is a primitive root modulo n then
set of all primitive roots are the integers b such that b = ar mod n for some gcd(r, ∀(n)) = 1.

↭ Example 2.8 We want to find all primitive roots modulo 7. Recall that ∀(7) = 6, so we are
looking for all natural numbers a such that a mod 7 has order 6, or said differently that a mod 7
is a generator for (Z/7Z)↖ . Note that 32 = 2 (mod 7), 33 = 6 (mod 7) so 3 mod 7 does not have
order 1,2, or 3. Since the order is a divisor of the order of the group. The group order is 6 so we
may conclude that 3 mod 7 has order 6 and is therefore a generator. By the proof of Proposition
2.4.6 the element 3r mod 7 is a generator precisely if gcd(r, 6) = 1 which happens precisely for
r = 1, 5 (mod 6). Note that 35 = 5 (mod 7).
Therefore 3,5 are the only primitive roots modulo 7 which are less than 6. Note that that this
agrees with ∀(∀(7)) = ∀(6) = ∀(2)∀(3) = 2.
Hence a is a primitive root modulo 7 if and only if a = 3 (mod 7) or a = 5 (mod 7). ↭

2.4.2 Artin’s conjecture

Conjecture 2.4.7 [Artin’s conjecture] Let a ↑ Z\{↘1} with a ↓= b2 . Then there are infinitely
many primes p such that a is a primitive root modulo p
This is a long-standing and important conjecture. On the one hand we do not know a single a
for which there are infinitely many primes p such that a is a primitive root modulo p. On the other
hand we know – due to Heath-brown [Hea86] – that it is true whenever a is a prime with at most
two exceptions. In particular it is true for either a = 2, 3, or 5 but we do not know which of the
 2.5 Local obstructions 23

three. Heath-brown also showed that it holds whenever a is square-free (i.e. a being a product of
different primes) with at most 3 exceptions.
Hooley showed [Hoo67] that Artin’s conjecture follows from a generalization of the Riemann
hypothesis.

2.5 Local obstructions

When we want to determine whether a specific diophantine equation has integer solutions this can
sometimes be ruled out by clever congruence considerations.
↭ Example 2.9 Consider the Diophantine equation

x5 ↘ x2 + x ↘ 3 = 0,

i.e. we are looking for integer roots of the polynomial f (x) = x5 ↘ x2 + x ↘ 3. If such a root exist we
can reduce it modulo n (where n is any integer) and we will have that x satisfies f (x) = 0 (mod n).
In this case it turns out to be convenient to consider n = 4. We can then verify that f (0) = 1,
f (1) = 2, f (2) = 3 and f (3) = 2, in particular these numbers are all non-zero modulo 4, and hence
no such integer solution can exist. We say that there is a local obstruction to f (x) = 0 having
integer solutions.
Note that it is straightforward to verify that f (x) has real roots as f (x) ⇒ ! as x ⇒ !, and
f (x) ⇒ ↘! as x ⇒ ↘!, so by the intermediate value theorem f (x0 ) = 0 for some real x0 . ↭

↭ Example 2.10 Consider the Diophantine equation

3 = x 2 + y2 .

It is easy to verify that any square x2 is either 0 or 1 modulo 4. Hence any expression x2 + y2 must
be either 0, 1, or 2 modulo 4. But since 3 is 3 modulo 4 this Diophantine equation does not have a
solution. Notice that this argument generalizes to proving that the equation

p = x 2 + y2 (2.8)

does not have solutions whenever p is equal to 3 modulo 4. We will later in Theorem 6.1.3 that if p
is a prime which is not equal to 3 modulo 4 then (2.8) does indeed have a solution. ↭

Local obstructions are useful for proving that there are no solutions to a Diophantine equation.
In other cases there are no local obstructions (e.g. if the Diophantine equation has solutions there
can be no local obstruction). There are families of Diophantine equations where the existence of
both solutions modulo pn for every prime power and a real solution suffices to conclude that the
Diophantine equation has an integer solution. Such a result is called a local to global principle.

2.6 Exercises for Chapter 2

Exercise 2.1 Prove Proposition 2.1.1.
Exercise 2.2 Show that there are no primitive roots modulo 8.
Exercise 2.3 Show that there are no primitive roots modulo 2n for any n → 3.
Exercise 2.4 Find all primitive roots modulo 17.
Exercise 2.5 — Freshman’s dream. Let a, b be integers and let p be a prime. Prove that
(a + b) p = a p + b p (mod p).
Exercise 2.6 Determine if x5 = 2 (mod 2003) has a solution. Note that 2003 is a prime.
Exercise 2.7 Prove that the Diophantine equation f (x) = 0 has no solution when f (x) is one of
the following: a) x3 ↘ x + 1, b) x3 + x2 ↘ x + 1, c) x3 + x2 ↘ x + 3.
24 Chapter 2. Modular arithmetic

Exercise 2.8 Seven pirates try to share a stolen pile of identical diamonds equally between
themselves. Unfortunately, six diamonds are left over, and in the fight over them, one pirate is
thrown overboard and gets eaten by sharks. The remaining six pirates, still unable to share the
diamonds equally since two are left over, again fight, and another is killed. When the remaining
five share the diamonds, one diamond is left over, and it is only after yet another pirate is thrown
overboard that an equal sharing is possible. What is the minimum number of diamonds that the
pirates have stolen?
Exercise 2.9 For which values n is ∀(n) odd? Show that there exists integers n with ∀(n) =
2, 4, 6, 8, 10, 12 but not 14.
Exercise 2.10 Find the smallest integer n such that ∀(n)/n ↔ 1/4
Exercise 2.11 Show that if n > 4 is composite then (n ↘ 1)! = 0 mod n.
Exercise 2.12 Assume a = ↘1 or that a is a perfect square. Show that a is not a primitive root
modulo p for any prime p > 3. Determine whether a is a primitive root modulo 3. Compare with
Artin’s Conjecture 2.4.7.
Exercise 2.13 (Hard) Let p be an odd prime. Let g be a primitive root modulo p. Prove that either
g or g + p is a primitive roots modulo p2 . In particular this shows that primitive roots modulo p2
exists One can show that primitive roots modulo pe exist for any e → 1. See e.g. [JJ98, Thm 6.7].
Exercise 2.14 Find all integer solutions to each of the equations

3x = 4 (mod 123)
5x = 23 (mod 123)
5x = 234 (mod 2002).