Trophy Hunting

in the
Infinite Jungle
of
Finitude

Janne Junnila
 Compiled on December 3, 2015

© 2014–2015 Janne Junnila

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike

4.0 International License1

1
[Link]
Foreword 6

i number theory 8
1 Algebraic structure of u� 9
1.1 Commutative rings 9
1.2 Ideals and quotient rings 11
1.3 Euclidean domains 13
1.4 Unique factorization 17
1.5 Primes and factoring in u� 20
1.6 Ring homomorphisms 22
1.7 Chinese remainder theorem 23

2 Working modulo u� 26
2.1 Euler’s totient function 26
2.2 Structure of the unit group 27
2.3 Primitive roots 29
2.4 Squares and square roots 30

3 More about primes 39

3.1 Miller–Rabin primality test 39
3.2 Counting prime numbers 41

4 Gaussian integers 44
4.1 Structure of u�[u�] 44
4.2 Sums of squares 46
4.3 Pythagorean triples 47

5 Continued fractions 49
5.1 Definitions and examples 49
5.2 Best rational approximations 55
5.3 Quadratic irrationals 61

6 Pell’s equation
√ 67
6.1 Rings u�[ u�] √ 67
6.2 Calculating the CF-expansion of u� 68
7 Arithmetic functions 72
7.1 Dirichlet ring 72
7.2 Möbius inversion 73

ii algebra 77
1 Groups 78
1.1 Basic definitions 78
1.2 Group actions 84
1.3 Conjugacy classes 85
2 Permutations and ordered sets 87
2.1 Permutation group u�u� 87
2.2 Ordered sets and inversions 90
2.3 Conjugates and commuting elements 91
3 Linear recurrences 93
3.1 Basic theory 93
3.2 Generating functions 95
3.3 Components of the recursion and closed formulas 97

iii combinatorics 98
1 Generating functions 99
1.1 Formal power series 99
1.2 Analytic functions 100
1.3 Solving recurrence relations and sums 102
2 Combinatorial species 106
2.1 Definition 106
2.2 Combinatorial equality, embeddings and coverings 107
2.3 Associated generating functions 107
2.4 Operations on species 108
2.5 Basic species 110
2.6 Derived species 112
3 Pólya theory 116
3.1 Colored species 116
3.2 Quotient species 119
iv game theory 124
1 Impartial games 125
1.1 Nimbers 125
1.2 Sum games 126

Index 127
foreword

Dear fellow problem solvers, coders and mathemati-

cians,
Welcome to this hunting trip into the jungle of mathematical
objects. This time we will be venturing to the section of the forest
where most of these creatures are discrete and finite.
Although a vast majority of the things we encounter are huge
and dangerous beasts that we so far have no hope of defeating, the
tropical forest itself is immensely beautiful. Every now and then
we meet some reasonably sized species, even cute ones, that we
can tame or shoot down. When this happens, we collect them as
hunting memoirs to be recalled when we next time meet something
similar. In this book several of these trophies will be presented.
One of the target audiences of the book are competitive pro-
grammers hoping to learn mathematical theory that would help
them during contests. For them every competition is a hunting
trip of its own, and on top of the hunting memoirs of knowledge,
different kind of trophies such as glory and recognition are awarded
to those who win. Of course, for most of them, the most important
part is the problem solving itself and the social context around it.
In any case, to make a contact with this group, the focus will be on
problems that have algorithmic solutions and C++-snippets will be
provided for the various algorithms developed.
Another group that would perhaps like to take part on this
expedition are mathematicians that are interested in the compu-
tational side of things. Everything is written with mathematical
rigour, so these people should find themselves at home.
The choice of topics has mostly been influenced by what I
myself have run into. This means that there is a lot of stuff that has
appeared on Project Euler, for instance. I have intentionally not
covered basic algorithms or techniques that appear in competitive
programming, so if you want to learn about shortest paths, segment
trees, binary search or dynamical programming, I have collected
some reading suggestions at the end of the book.
One of the goals of the book is to look for methods and general
theories that makes solutions to various problems look streamlined
when approached from the right angle. Sometimes in this jungle
 7

there is nothing as fun as hitting a fly with an elephant gun, and it

is my aim to help you identify those guns.
As a prerequisite the reader should know a little bit of math-
ematics so that reading mathematical text feels comfortable. In
particular the reader should be familiar with basic set theory and
logic used for everyday mathematical discourse.
Now, go pack your jungle hat and machete, I wish you a fruitful
safari!

Janne Junnila
 number theory

P
Classical number theory deals with properties of integers. The set
of all integers is usually denoted by the symbol u�, and the set of
all non-negative integers is denoted by u�.
In this first part of the book we will approach classical number
theory with modern methods. When digested, ring theory provides
a unified way of thinking about many topics that traditionally were

A
hard problems of their own. This is why we will introduce the basics
of commutative rings at the same time as we navigate through the
foundations of elementary number theory.
The algebra developed will serve as a foundation for further
topics where such tools become indispensable. The methods will be
used to reason about diophantine equations (Pythagorean triples,
Pell’s equation, etc.) by extending the ring of integers and exam-

R
ining the equations in these extensions.

T
I
 algebraic structure of u�

1
In this chapter we will focus on the algebraic structure of the in-
tegers. In other words we will look at the interplay of addition
and multiplication, exploring topics such as greatest common divi-
sors or prime numbers. Many of these topics may already be quite
familiar to most of the readers. Therefore the emphasis is on a co-
herent and powerful point of view based on notions from abstract
algebra. To accomplish this, we will introduce some basic theory of
commutative rings as we go.

1.1 commutative rings

Let’s dive straight into it.

Definition 1.1 A set u� together with binary operations + and ⋅ form a commu-
tative ring if the following properties hold:

associativity − for all u�, u�, u� ∈ u�,

u� + (u� + u�) = (u� + u�) + u�,

u� ⋅ (u� ⋅ u�) = (u� ⋅ u�) ⋅ u�

identity elements − there exist elements 0 ∈ u� and 1 ∈ u� such that for all u� ∈ u�,

u� + 0 = 0 + u� = u�
u� ⋅ 1 = 1 ⋅ u� = u�

additive inverses − for every u� ∈ u� there exists an element −u� ∈ u� such that

u� + (−u�) = 0

distributivity − for all u�, u�, u� ∈ u�,

u� ⋅ (u� + u�) = u� ⋅ u� + u� ⋅ u�,

(u� + u�) ⋅ u� = u� ⋅ u� + u� ⋅ u�

commutativity − for all u�, u� ∈ u�,

 Commutative rings 10

u� + u� = u� + u�,
u� ⋅ u� = u� ⋅ u�

A couple of syntactical notes are in order:

− We often omit the multiplication symbol ⋅ and write u�u� instead

of u� ⋅ u�.

− Usually we write u� − u� instead of u� + (−u�).

It is easy to see that the integers under the usual addition and
multiplication form a commutative ring. Other examples include
the rational (u�), real (u�) and complex (u�) numbers.
One difference between u� and the other three rings mentioned
is the following: An element u� ∈ u� is called invertible (or a unit)
if there exists an element u� ∈ u� such that u�u� = 1. Clearly the only
invertible integers are 1 and −1. Contrast to that, in the rings u�,
u� and u� all elements except 0 are invertible.

Definition 1.2 A non-zero (i.e. u� ≠ {0}) commutative ring where every non-zero
element is invertible is called a field.

Thus u�, u� and u� are all fields.

Definition 1.3 A non-zero commutative ring u� is an integral domain if for all

u�, u� ∈ u� the equality u�u� = 0 implies that u� = 0 or u� = 0.

In other words, a non-zero ring u� is an integral domain if and only

if the product of two non-zero elements is non-zero.

Exercise 1.4 Show that a field is an integral domain.

Exercise 1.5 Show that u� is an integral domain if and only if it has the following
cancellative property: if u�, u�, u� ∈ u� and u� ≠ 0, then the equality
u�u� = u�u� implies that u� = u�.

We haven’t yet had an example of a ring that is not an integral do-

main. Let us therefore close the section with the following exercise.
 Ideals and quotient rings 11

Exercise 1.6 Let u� = {0, 1, u�, u�} be a ring of 4 elements such that 1 + 1 = u�.
Show that such a ring exists and is unique and that it is not an
integral domain.

1.2 ideals and quotient rings

We will next describe ideals, which are a way to extend the notion
of divisibility. Assume that u� and u� are two integers that are both
divisible by some integer u� ≠ 0. Then also u� + u� is divisible by
u�. Moreover you cannot remove this factor by multiplying: u�u� and
u�u� are still going to be divisible by u� for any integer u�. These two
properties are abstracted away into the definition of an ideal.

Definition 1.7 Let u� be a commutative ring. A subset u� ⊂ u� is called an ideal if

− for all u�, u� ∈ u� we have u� + u� ∈ u�,

− for all u� ∈ u� and u� ∈ u� we have u�u� ∈ u�.

Example 1.8 The set {…, −12, −6, 0, 6, 12, …} is an ideal in u�. It is generated
by 6, and a number is divisible by 6 if and only if it lies in this set.

Definition 1.9 We let

⟨u�1 , …, u�u� ⟩ ≔ {u�1 u�1 + … + u�u� u�u� : u�1 , …, u�u� ∈ u�}

denote the ideal generated by u�1 , …, u�u� ∈ u�. An ideal generated

by a single element is called principal.

Definition 1.10 An integral domain in which every ideal is principal is called a

principal ideal domain (or PID).

Exercise 1.11 What is ⟨3, 5⟩ in u�?

We will see in the next section that u� is a PID. Every field is also
a PID, in fact look at the following exercise.

Exercise 1.12 Show that ideals in fields are boring.

 Ideals and quotient rings 12

Let u�, u� ∈ u�. If u� ∈ ⟨u�⟩, we say that u� divides u�, which we also
write as u� | u�. This is the same as saying that there exists u� ∈ u�
such that u� = u�u�. If u� is an integral domain and u� ≠ 0, such u� is
unique when it exists. (Why?)
One of the reasons we are interested in ideals is that we can
form new rings by considering the elements modulo u� for some ideal
u�.

Definition 1.13 Let u� ⊂ u� be an ideal. Two elements u�, u� ∈ u� are said to be equiv-
alent modulo u� if u� − u� ∈ u�. Let u�/u� denote the set of equivalence
classes [u�] under this relation. Then u�/u� can be made into a ring
by defining [u�] + [u�] = [u� + u�] and [u�] ⋅ [u�] = [u� ⋅ u�]. Rings obtained
this way are called quotient rings.

Exercise 1.14 Show that the definition makes sense. First show that u� ∼ u� ⇔
u� − u� ∈ u� really is an equivalence relation. Then show that the def-
initions of addition and multiplication do not depend on the choice
of representatives.

It is customary to write u� ≡ u� (mod u�) if u� and u� belong to the

same equivalence class modulo u�. In the case u� is a principal ideal
generated by u� ∈ u�, we also write u� ≡ u� (mod u�).
A principal ideal ⟨u�⟩ Let u� ≥ 1. The ideal ⟨u�⟩ in u� defines a quotient ring u�/u�u�
in a ring u� can also consisting of the u� elements {[0], [1], …, [u� − 1]}. Two integers are
be written as u�u�. equivalent modulo ⟨u�⟩ if and only if they give the same remainder
upon division by u�. In C++ the representative of u� modulo u� in
the range 0, …, u� − 1 can thus be obtained by calculating a%m, as-
suming that u� is non-negative. If u� is negative, it can be calculated
as a%m + m.
There are two important special types of ideals that we have
yet to discuss.

Definition 1.15 An ideal u� ⊂ u� is a prime ideal if

• u�u� ∈ u� implies u� ∈ u� or u� ∈ u�,

• u� ≠ u�.

An element u� ∈ u� is called a prime element if ⟨u�⟩ is a prime ideal.

 Euclidean domains 13

Example 1.16 In u� the number 5 is a prime element since if u�u� is divisible by 5,

then either u� or u� is divisible by 5. Note that also −5 is a prime
element.
In fact the set of prime elements in u� is given by u� ∪ (−u�),
where

u� = {2, 3, 5, 7, 11, 13, 17, …}

is the set of prime numbers, which are the positive prime ele-
ments.

Theorem 1.17 An ideal u� is a prime ideal if and only if u�/u� is an integral domain.

Proof. Exercise. □

Definition 1.18 An ideal u� ⊂ u� is a maximal ideal if u� ≠ u� and there does not

exist ideal u� such that u� ⊊ u� ⊊ u�.

Theorem 1.19 An ideal u� ⊂ u� is a maximal ideal if and only if u�/u� is a field.

Proof. Assume first that u� is a maximal ideal. Let [u�] ∈ u�/u�. Assume,
to obtain a contradiction, that there does not exist [u�] ∈ u�/u� such
that [u�] ⋅ [u�] = [1]. Consider the ideal ⟨[u�]⟩ ⊂ u�/u�. It is not the
whole u�/u� because [1] ∉ ⟨[u�]⟩. Let u� = {u� ∈ u� : [u�] ∈ ⟨[u�]⟩}. Then
u� is an ideal and u� ⊊ u� ⊊ u�, which is a contradiction.
Assume then that u�/u� is a field. Suppose that u� ⊊ u� ⊊ u� for
some ideal u�. Then there exists u� ∈ u� ∖ u�. Because u�/u� is a field,
[u�] ∈ u�/u� has an inverse [u�] ∈ u�/u� meaning that u�u� − 1 ∈ u� ⊂ u�.
But this means that 1 ∈ u�, so u� = u�, a contradiction. □

Let us end the section by noting that since fields are integral do-
mains, every maximal ideal is a prime ideal by the previous theo-
rems.

1.3 euclidean domains

Euclidean domains are rings for which there exists a Euclidean al-
gorithm. For the Euclidean algorithm to work, it is necessary that
division yields remainders of decreasing size. In an arbitrary ring
 Euclidean domains 14

we have to abstract away the notion of size, so we arrive to the

following definition.

Definition 1.20 An integral domain u� is a Euclidean domain if there exists a

function u�∶ u� → u� such that for all u� ∈ u� and u� ∈ u� ∖ {0} we can
find u�, u� ∈ u� for which

u� = u�u� + u�

and u�(u�) < u�(u�).

Theorem 1.21 u� is a Euclidean domain.

Proof. In the definition of Euclidean domain we can simply take u�(u�) =

|u�|. Indeed, if u� ∈ u� and u� ≠ 0, then we can write u� = u�u� + u�,
where u� is the quotient under division u�/u� and u� is the remainder,
which has a smaller absolute value than u�. □

Definition 1.22 Let u�, u� ∈ u�. An element u� ∈ u� is called a greatest common

divisor (gcd) of u� and u� if u� | u� and u� | u� and for any other such
u�′ we have u�′ | u�.
Dually, an element u� ∈ u� is called a least common multiple
(lcm) of u� and u� if u� | u�, u� | u� and for any other such u�′ we have u� | u�′ .

Example 1.23 In u� the numbers 5 and −5 are greatest common divisors of the
numbers −15 and 35. These are actually the only greatest common
divisors of the two numbers and they differ by multiplication by −1.
The least common multiples of the numbers −15 and 35 are −105
and 105.

Theorem 1.24 If u� is an integral domain, then two greatest common divisors u�

and u�′ of two elements u� and u� satisfy u� = u�u�′ for some unit u� ∈ u�.
The same holds for least common multiples.

Proof. Exercise. □

In the case of u�, it is customary to choose gcd(u�, u�) and lcm(u�, u�)
to be the non-negative variants.
 Euclidean domains 15

We have the following connections from greatest common divi-

sors and least common multiples to ideals. You should try to prove
these.

− Ideals u� and u� are said to be coprime if u� + u� = u�. Here

u� + u� = {u� + u� : u� ∈ u�, u� ∈ u� }, which is also an ideal.

− In a PID the ideal ⟨u�⟩+⟨u�⟩ is generated by any greatest common

divisor of u� and u�. If ⟨u�⟩+⟨u�⟩ = u�, the greatest common divisors
of u� and u� are units and we say that they are coprime.

− If u� and u� are coprime, then [u�] is invertible in the quotient ring

u�/⟨u�⟩ and vice versa.

− If u� and u� are two ideals, so is u� ∩ u�. In a PID the ideal ⟨u�⟩ ∩ ⟨u�⟩
is generated by any least common multiple of u� and u�.

Example 1.25 One can check that ⟨6⟩ + ⟨15⟩ = ⟨3⟩ and that ⟨6⟩ ∩ ⟨15⟩ = ⟨30⟩.

Let’s get back to Euclidean domains.

Theorem 1.26 If u� is a Euclidean domain, then every pair of elements u�, u� ∈ u�∖{0}
has a greatest common divisor u� ∈ u� and there exist u�, u� ∈ u� such
that

u�u� + u�u� = u�. (1.1)

This equation is sometimes called Bezout’s identity.

Proof. Let u�0 = u� and u�1 = u�. Then we can find a sequence of elements
u�1 , u�2 , …, u�u� and u�2 , u�3 , …, u�u� such that

u�0 = u�1 u�1 + u�2 ,

u�1 = u�2 u�2 + u�3 ,
⋮
u�u�−3 = u�u�−2 u�u�−2 + u�u�−1
u�u�−2 = u�u�−1 u�u�−1 + u�u� ,
 Euclidean domains 16

where u�u� = 0 and u�(u�u�−1 ) < u�(u�u�−2 ) < … < u�(u�2 ) < u�(u�1 ).
Let u� ≔ u�u�−1 . Then u� divides u�u�−2 , and it also divides u�u�−3
because u�u�−3 = u�u�−2 u�u�−2 + u�u�−1 . Continuing this reasoning induc-
tively up the equation chain we see that u� divides every u�u� , including
u�0 = u� and u�1 = u�.
Conversely any common divisor u�′ of u� and u� must divide each
u�u� , so in particular u�′ | u�. This means that u� is a greatest common
divisor. Solving u�2 = u�0 − u�1 u�1 , substituting it to the next equa-
tion and solving u�3 and continuing like this, we will end up with a
representation (1.1). □

The considerations so far show that in the case of u� we can find a

well-defined greatest common divisor of any two integers u�, u� as long
as at least one of them is non-zero. Just pick the positive one and
denote it gcd(u�, u�). Thus for example gcd(15, 35) = 5. Moreover,
the proof above can be turned into an algorithm that computes the
gcd as well as numbers u�, u� ∈ u� so that (1.1) is satisfied.

Algorithm 1.27 (Extended Euclidean algorithm) The following calculates the great-
est common divisor u� of u� and u� as well as u� and u� such that
u�u� + u�u� = u�.

void eea(int64_t a, int64_t b, int64_t &d,

int64_t &x, int64_t &y) {
int64_t u=1, v=0, m, n, q, r;
x=0, y=1;
d = b;
while(a != 0) {
q=d/a; r=d%a;
m=x-u*q; n=y-v*q;
d=a; a=r;
x=u; y=v;
u=m; v=n;
}
}

The existence of a Euclidean algorithm is one of the greatest thing

about Euclidean domains. From theoretical point of view the fol-
lowing is also nice.
 Unique factorization 17

Theorem 1.28 Any Euclidean domain is a PID.

Proof. Let u� be a Euclidean domain, u� its size function and u� ⊂ u� an

ideal. Choose u� ∈ u� ∖ {0} for which u�(u�) is minimal. Then clearly
⟨u�⟩ ⊂ u�. On the other hand if u� ∈ u�, we can find elements u�, u� ∈ u�
such that u� = u�u� + u� and u�(u�) < u�(u�). Notice that u� ∈ u�, so we
must have u� = 0 and therefore u� ∈ ⟨u�⟩. Thus u� = ⟨u�⟩. □

Now we finally see that all the ideals of u� are of the form ⟨u�⟩ for
some u� ∈ u�.
Let us close the section with the following longish (but impor-
tant if you haven’t seen it before) exercise.

Exercise 1.29 An equation of the form u�u� + u�u� = u� where u�, u�, u� ∈ u� is called a
linear diophantine equation. Assume that u�, u�, u� are non-zero.

− Give a necessary and sufficient condition under which there exist

integers u� and u� that satisfy the equation.

− Give a parametrization for all the solutions.

− Implement a program solving the equation.

1.4 unique factorization

Our next aim is to show that every u� ∈ u� has a unique factorization

into prime elements. Indeed, this is the case in the more general
setting of so called unique factorization domains, of which PIDs are
a special case.

Definition 1.30 A non-zero non-unit element u� ∈ u� is irreducible if it is not a

product of two non-invertible elements. A non-zero non-unit ele-
ment that is not irreducible is called reducible.

The term composite In u� the irreducible elements are the same as the prime elements.
seems to be non- This is not the case for all commutative rings in general, although
standard in ring for integral domains prime elements are irreducible. In u� reducible
theory. I like it elements are also called composite. We will use the same term
in the context of also in unique factorization domains that will be defined shortly.
UFDs, however.
 Unique factorization 18

Theorem 1.31 In an integral domain a prime element is irreducible.

Proof. Exercise. □

The happy thing is that the converse holds in principal ideal do-
mains, and more generally in unique factorization domains (which
will be defined soon).

Theorem 1.32 In a PID an ideal generated by an irreducible element is maximal.

Proof. Let u� ∈ u� be irreducible. Let u� ≠ u� be an ideal such that ⟨u�⟩ ⊂ u�.

Then because u� is a PID, u� is of the form u� = ⟨u�⟩, where u� is
necessarily not a unit. But this means that u� = u�u� for some u� ∈ u�,
which must be a unit since u� is irreducible. It follows that the two
ideals coincide, so ⟨u�⟩ is maximal. □

It is an immediate corollary that in PIDs primes and irreducible el-

ements are the same. Indeed, if u� is irreducible, then ⟨u�⟩ is maximal
and thus prime.
We should also note that this means that in a PID any quotient
ring u�/⟨u�⟩ is a field if and only if u� is prime/irreducible.

Definition 1.33 An integral domain u� is a unique factorization domain, or

UFD, if any element u� ∈ u� can be written in the form

u� = u�u�1 u�2 …u�u� ,

where u�1 , …, u�u� are irreducible and this product is unique up to

reordering and multiplying the elements by units.

Theorem 1.34 Every PID is a UFD.

Proof. Let us start by showing that any u� ∈ u� is a product of finitely many

irreducibles.
First notice that u� has the property that any ascending chain

u�1 ⊂ u�2 ⊂ u�3 ⊂ …

of ideals must be constant from some point on. Indeed, because

∞
the chain is ascending, the set u� = ⋃u�=1 u�u� is an ideal. Thus it
 Unique factorization 19

is generated by some element u� ∈ u�u� for large enough u�. Then

u�u� = u�u� for u� ≥ u�.
Let u� ∈ u�. If u� is irreducible we are done. Otherwise we can
write u� = u�0 u�1 where neither of u�0 , u�1 is a unit. We recurse to
u�0 and u�1 and they are either both irreducible, or for example u�1
is reducible and we get numbers u�10 , u�11 such that u�1 = u�10 u�11 .
Assume, towards a contradiction, that we continue expanding the
terms and that the process never ends. Then there exists a binary
sequence u� such that

⟨u�⟩ ⊂ ⟨u�u�1 ⟩ ⊂ ⟨u�u�1 u�2 ⟩ ⊂ ⟨u�u�1 u�2 u�3 ⟩ ⊂ …

As we saw above, this chain must settle, so at some point u�u�1 u�2 …u�u�
and u�u�1 u�2 …u�u�+1 generate the same ideal. This means that u�u�1 u�2 …u�u� =
u�u�u�1 u�2 …u�u�+1 for some unit u�, which is a contradiction. Thus the
expanding of terms ends, and every u� ∈ u� admits a factorization
into irreducibles.
We will conclude the proof by showing that the factorization is
unique. Assume that u� = u�u�1 u�2 …u�u� = u�u�1 u�2 …u�u� where u�1 , …, u�u�
and u�1 , …, u�u� are irreducibles and u� and u� are units. Because u�1
divides u�1 u�2 …u�u� , and because u�1 is a prime, there must exist u�u� such
that u�1 | u�u� . Since u�u� is irreducible, we see that when we cancel u�1
and u�u� , we are left with a unit. We can therefore reduce to the
case where there are 1 less factors on both sides and continue by
induction. □

Theorem 1.35 Every irreducible element in a UFD is prime.2

Proof. Let u� ∈ u� be an irreducible element and consider the ideal ⟨u�⟩.

Assume that u�u� ∈ ⟨u�⟩. Then u�u� = u�u� for some u� ∈ u�. Writing u�, u�
and u� in terms of irreducibles u�1 …u�u� , u�1 …u�u� and u�1 …u�u� , we have
for some unit u� that

u�u�1 …u�u� u�1 …u�u� = u�1 …u�u� u�.

2 One might ask why we proved this for PIDs in the first place. The reason is
that we used the result in the proof that a PID is a UFD.
 Primes and factoring in u� 20

By unique factorization one of the u�1 …u�u� u�1 …u�u� must equal u� mul-
tiplied by a unit. If it is one of the u�u� s, then u� ∈ ⟨u�⟩, otherwise
u� ∈ ⟨u�⟩. Thus ⟨u�⟩ is a prime ideal and u� is a prime element. □

1.5 primes and factoring in u�

It is time to take a break from the algebraic mumbo jumbo and see
how what we have established can be used in the setting of u�.
Since u� is a PID, we know that the prime elements are the
same as the irreducibles. Suppose that we want to check if u� ∈ u�
is a prime. Without loss of generality we can assume that u� ≥ 2.
Since u� is a UFD, we can write
u� u�
u� = u�1 1 …u�u�u�

where u�1 < … < u�u� are positive primes and u�1 , …, u�u� ≥ 1. This
is called the prime factorization of u�. If u� was composite, we
would either have u�1 ≥ 2, in which case u�12 ≤ u�, or we would
have u�1 = 1 and u� ≥ 2, in which case u�12 < u�1 u�√
2 ≤ u�. Thus every
composite u� has a prime factor of size at most ⌊ u�⌋. This leads to
the following simple algorithm for checking whether a given number
is prime.

Algorithm 1.36 (Trial division)

bool is_prime(int64_t m) {
for(int64_t i=2;i*i<=m;i++) {
if(m % i == 0) return false;
}
return true;
}
√
The running time of the algorithm is u�( u�). It should be noted
that (much) more efficient tests exist.

Let us next consider the problem of listing the primes up to some

number u�.
 Primes and factoring in u� 21

Algorithm 1.37 (Sieve of Eratosthenes) The idea is to start from 2 and rule out
composite numbers whenever new primes are found. Indeed, first
we mark 4, 6, 8, … as composites. Then we move on to 3 and mark
3, 6, 9, 12, 15, … Since we have already marked 4, we skip it and
move to 5, which is our third prime. This is repeated until we
reach u�.

vector<int64_t> sieve(N+1,0);

for(int64_t p=2;p<=N;p++) {
if(sieve[p] == 0) {
for(int64_t i=p;i<=N;i+=p) {
sieve[i] = p;
}
}
}

The algorithm above stores in sieve[m] the largest prime factor

of u�. This will be useful next when we consider factoring num-
bers. Using some asymptotic results on the distribution of primes,
it is not too hard to show that the complexity of the algorithm is
u�(u� log log u�).

Let’s get straight on to factoring.

Algorithm 1.38 (Factoring using a sieve) Assume that we have built a factor sieve
up to u� and want to factor u� ≤ u�. This is easily done as follows.

typedef pair<int64_t, int64_t> P;

vector<P> factors;

while(m != 1) {
int64_t p = sieve[m];
int64_t a = 0;
while(m%p == 0) {
m/=p;
a++;
}
factors.push_back(P(p, a));
}
 Ring homomorphisms 22

In the end factors will contain a pair (u�u� , u�u� ) for each prime factor
u�
u�u�u� of u�.

1.6 ring homomorphisms

Definition 1.39 Let u� and u� be two commutative rings. A map u�∶ u� → u� is called
a ring homomorphism if u�(0) = 0, u�(1) = 1 and for all u�, u� ∈ u�
we have

u�(u� + u�) = u�(u�) + u�(u�), and

u�(u�u�) = u�(u�)u�(u�).

Exercise 1.40 Show that the map u�∶ u� → u�2×2 given by

u� u�
u�(u� + u�u�) = ( )
−u� u�

is a ring homomorphism from the complex numbers to the real 2×2

matrices.

Ring homomorphisms are important for the general theory of rings.

For example if u� is an ideal in u�, then the map u�u� ∶ u� → u�/u� given
by u�u� (u�) = [u�] is a ring homomorphism.

Definition 1.41 Given a ring homomorphism u�∶ u� → u�, the set of elements mapping
to 0 under u� is denoted by Ker u� and called the kernel of u�.

For example the kernel of the map u�u� above is simply u�.

Theorem 1.42 Let u�∶ u� → u� be a ring homomorphism. Then Ker u� is an ideal and
˜ u�/Ker u� → u�
there exists a unique injective ring homomorphism u�∶
˜
such that u� = u� ∘ u�Ker u� .

Proof. Exercise. □

Note that as a special case of the above theorem if Ker u� = {0}

then u� is injective. If a ring homomorphism u� is a bijection, we say
that it is a ring isomorphism.
 Chinese remainder theorem 23

Exercise 1.43 Show that the inverse mapping u� −1 of a ring isomorphism is also a
ring isomorphism.

If there exists an isomorphism between two rings u� and u�, then

we say that u� and u� are isomorphic. One should note that in
terms of ring theory isomorphic rings are indistinguishable; all their
algebraic properties are the same.
The following definition and theorem make

Definition 1.44 Let u�∶ u� → u� be a ring homomorphism. The image of u� is the set
Im u� ≔ u�(u�).

Theorem 1.45 The image of a ring homomorphism u�∶ u� → u� is a subring of u�.

The rings u�/Ker u� and Im u� are isomorphic, and an isomorphism
is given by the map u�˜ in Theorem 1.42.

Proof. Exercise. □

1.7 chinese remainder theorem

Definition 1.46 If u� and u� are two commutative rings, then we can form their
product ring u� × u� by taking all the tuples (u�, u�) with u� ∈ u� and
u� ∈ u� and defining the ring operations component wise, i.e.

(u�, u�) + (u�′ , u�′) = (u� + u�′ , u� + u�′),

(u�, u�) ⋅ (u�′ , u�′) = (u� ⋅ u�′ , u� ⋅ u�′)

for all u�, u�′ ∈ u�, u�, u�′ ∈ u�.

It is easy to see that the 0 in a product ring is (0, 0) and the 1 is

(1, 1). Product rings are not integral domains (unless one of the
factors is the zero-ring and the other one is an integral domain)
since (0, 1) ⋅ (1, 0) = (0, 0). An element (u�, u�) is a unit if and only
if u� is a unit in u� and u� is a unit in u�.

Definition 1.47 Let u� and u� be ideals in u�. Their product ideal u�u� is the ideal
generated by all products u�u�, u� ∈ u� and u� ∈ u�, i.e.
 Chinese remainder theorem 24

u�u� ≔ {u�1 u�1 u�1 + … + u�u� u�u� u�u� : 1 ≤ u� ≤ u�, u�u� ∈ u�, u�u� ∈ u�, u�u� ∈ u� }.

The chinese remainder theorem gives us a natural link between

products of coprime ideals and products of quotient rings.

Theorem 1.48 Let u� and u� be two coprime ideals of a commutative ring u�. Then
u� ∩ u� = u�u� and there exists a ring isomorphism

u�∶ u�/u�u� → u�/u� × u�/u� .

Proof. Let us first show that u� ∩ u� = u�u�. If u� ∈ u�u�, then it is of the form
u� = u�1 u�1 u�1 + … + u�u� u�u� u�u� , where u�u� ∈ u�, u�u� ∈ u� and u�u� ∈ u�. It is
clear that such an element belongs both to u� and u�. If u� ∈ u� ∩ u�,
then since u� + u� = u�, we have u� + u� = 1 for some u� ∈ u�, u� ∈ u�, and
thus u� = u�u� + u�u� ∈ u�u�.
Consider the map u�∶ u� → u�/u� × u�/u� given by

u�(u�) = (u�u� (u�), u�u� (u�))

for all u� ∈ u�. It is clear that Ker u� = u� ∩ u� = u�u�. Thus the claim
will follow from the factorization theorem once we show that u� is
surjective. Let u�, u� ∈ u� be arbitrary and set u� = u�u� + u�u� where
u� ∈ u� and u� ∈ u� are such that u� + u� = 1. Then u�u� (u�) = u�u� (u�) and
u�u� (u�) = u�u� (u�). Thus the arbitrary element (u�u� (u�), u�u� (u�)) belongs
to Im u� and u� is surjective. □

It is easy to see that by induction the above result can be generalized

to u� ideals u�1 , …, u�u� that are pairwise coprime, i.e. u�u� + u�u� = u� for
all u� ≠ u�. Then we get an isomorphism betwen u�/(u�1 …u�u� ) and
u�/u�1 × … × u�/u�u� . In PIDs we have the following version:

Theorem 1.49 Let u� be a PID and u�1 , …, u�u� pairwise coprime elements of u�. Then
there exists an isomorphism

u�/⟨u�1 …u�u� ⟩ → u�/⟨u�1 ⟩ × … × u�/⟨u�u� ⟩.

Let us specialize to the case of u�. Let u�1 , …, u�u� ≥ 1 be pairwise

coprime. Assume that we are given an element in u�/u�1 u� × ⋯ ×
u�/u�u� u� in terms of u� representatives u�1 , …, u�u� ∈ u�, so that our
element is (u�u�1 (u�1 ), …, u�u�u� (u�u� )).
 Chinese remainder theorem 25

We would like to construct a representative for the correspond-

ing element in u�/(u�1 …u�u� )u�. Similarly to what was done in the
proof, it is easy to see that such an element is given by
u� = u�1 (u�2 …u�u� )u�1 + u�2 (u�1 u�3 …u�u� )u�2 + … + u�u� (u�1 u�2 …u�u�−1 )u�u�−1 ,
where u�u� is a representative for the inverse of u�u�u� (u�1 …u�u�−1 u�u�+1 …u�u� )
in u�/u�u� u�.
This inverse can be found by using the extended Euclidean
algorithm on u�u� and u�1 …u�u�−1 u�u�+1 …u�u� to find u�u� and u�u� such that
u�u� (u�1 …u�u�−1 u�u�+1 …u�u� ) + u�u� u�u� = 1.

We are ready to code this up.

Algorithm 1.50 (Chinese remainder theorem)

typedef pair<int64_t, int64_t> P;

// Given a vector of pairs (x_k, a_k),

// computes a number x such that x = x_k mod a_k
int64_t chinese_remainder(const vector<P> &repr) {
int64_t prod=1;
for(int64_t i=0;i<[Link]();i++) {
prod*=repr[i].second;
}
int64_t result=0;
for(int64_t i=0;i<[Link]();i++) {
int64_t b,c,d;
eea(repr[i].second, prod/repr[i].second, d, c, b);
result+=repr[i].first*(prod/repr[i].second)*b%prod;
result%=prod;
}
return result;
}

This concludes our study of the global structure of u�. Indeed, we

are now ready to switch our focus to the quotient rings u�/u�u�.
By the chinese remainder theorem any such ring is isomorphic
u� u�
to a ring of the form u�/u�1 1 u� × ⋯ × u�/u�u�u�u� u�, where u�1 1 ⋯u�u�u�u� is
the prime factorization of u�. This means that it is often enough
to consider the case where u� = u�u� for some prime number u� and
u� ≥ 1.
 working modulo u�

2 2.1 euler's totient function

We started our study of u� by finding the invertible elements, and

likewise our first goal here will be to figure out the group of units
of u�/u�u�. The answer will be more interesting than in the case of
u�, and the required basics of group theory can be read from the
first two chapters of Part III. The reader should take a look there
now if he or she is not familiar with groups.
We already have several important examples of groups from
the last section. If u� is any commutative ring, then (u�, +) is a
group with identity element 0. This is called the additive group
of u�. Similarly the units of u� form a group under multiplication
with 1 as the identity element. This is called the multiplicative
group or group of units of u� and we denote it by u�∗ . Also any
ideal u� ⊂ u� is a subgroup of the additive group of the ring.
For all u� ≥ 1, let u�(u�) denote the size of the group (u�/u�u�)∗ .
The function u�∶ u�+ → u�+ is called the Euler totient function. Re-
u� u�
call that if the prime factorization of u� is u�1 1 ⋯u�u�u� , then there is
an isomorphism
u�
u�/u�u� ≅ u�/u�1 1 u� × ⋯ × u�/u�u�u�u� u�.

Likewise, an element of a product ring is a unit if and only if all of

its components are units, i.e. we have the isomorphism
u�
(u�/u�u�)∗ ≅ (u�/u�1 1 u�)∗ × ⋯ × (u�/u�u�u�u� u�)∗ .

Thus we immediately see that

u�
u�(u�) = u�(u�1 1 )…u�(u�u�u�u� ).

Now let u� be a prime number. Recall that 0, 1, …, u�u� − 1 is a full

set of representatives for the ring u�/u�u� u�. The ones that represent
units are the ones that are coprime to u�u� , i.e. the ones that are not
divisible by u�. There are u�u� − u�u�−1 such numbers, so

u�(u�u� ) = (u� − 1)u�u�−1 .

 Structure of the unit group 27

This lets us calculate u� for any integer for which we know its prime
factorization.
Lagrange’s theorem for groups tells us that u�u�(u�) = 1 for all
u� ∈ (u�/u�u�)∗ . In this setting this is known as Euler’s theorem. In
the case where u� = u� is a prime number it is also called Fermat’s
little theorem, which states that u�u�−1 = 1 for all u� ∈ u�/u�u�, u� ≠ 0.

2.2 structure of the unit group

In this section we will identify the group structure of (u�/u�u� u�)∗

where u� is a prime number and u� ≥ 1. We will start with the case
u� = 2, since 2 behaves differently to other primes.

Theorem 2.1 Let u� ≥ 1, then

{ u�1 ,
⎧ if u� = 1,
u�
(u�/2 u�) ≅ u�2 ,
⎨
∗
if u� = 2,
{
⎩ u�2 × u�2u�−2 , if u� ≥ 3.

Proof. The cases u� = 1 and u� = 2 are clear by inspection. Let u� ≥ 3 and

note that u�(2u� ) = 2u�−1 . It is therefore enough to check that {−1, 1}
and {1, 5, 52 , …, 52 −1 } are two subgroups with trivial intersection
u�−2

and that the second group has 2u�−2 elements.

Let us first show that the order of 5 is 2u�−2 . To do this, it
suffices to show that 52 ≡ 1 and 52 ≢ 1. By repeatedly
u�−2 u�−3

squaring, we see that there exist odd numbers u�0 , …, u�u�−2 such
that
0
52 = 1 + u�0 ⋅ 22 ,
1
52 = (1 + u�0 ⋅ 22 )2 = 1 + u�1 ⋅ 23 ,
2
52 = (1 + u�1 ⋅ 23 )2 = 1 + u�2 ⋅ 24 ,
⋮
u�−3
52 = 1 + u�u�−3 ⋅ 2u�−1 ,
u�−2
52 = 1 + u�u�−2 ⋅ 2u� ,
 Structure of the unit group 28

which proves the claim.

Finally it is clear that 5u� ≢ −1 for all u�, because 5u� ≡ 1
(mod 4). □

Notice in particular that the group (u�/2u� u�)∗ is not cyclic for any
u� ≥ 3 because every element has order at most 2u�−2 .
Let us next consider the case where u� > 2. We will begin by
showing that (u�/u�u�)∗ is cyclic. First two small lemmas.

Theorem 2.2 Let u� be a field and u� be a polynomial of degree u� with coefficients

from u�. Then u� has at most u� roots in u�.

Proof. Exercise. □

Theorem 2.3 Let u� be a finite abelian group. If u� is the least common multiple
of the orders of the elements in u�, then u� contains an element of
order u�.
u� u�
Proof. Let u�1 1 …u�u�u� be the prime factorization of u�. Then there exist
u�
u�˜1 , …, u�˜u� ∈ u� such that u�u� u� divides the order of u�˜u� . Define u�u� =
u�u�
ord(˜
u� )/(u� ) u�
u�˜u� u� u�
. Then each u�u� has order u�u� u� . Clearly the subgroups
generated by u�u� intersect only at {1}, for an element belonging to
u�
the intersection of ⟨u�u� ⟩ and ⟨u�u� ⟩ has order that divides both u�u� u� and
u�
u�u� u� . Therefore u� contains a subgroup isomorphic to ⟨u�1 ⟩×⋯×⟨u�u� ⟩,
which is a cyclic group of order u�. □

Theorem 2.4 Let u� be an odd prime number. Then (u�/u�u�)∗ ≅ u�u�−1 .

Proof. Let u� be the least common multiple of the orders of the elements
in (u�/u�u�)∗ . Then since there exists an element of order u� and
because its order divides u� − 1, we must have u� ≤ u� − 1.
On the other hand consider the polynomial u� (u�) = u�u� − 1.
Every element of (u�/u�u�)∗ is a root of u� because their orders divide
u�. The number of roots is at most u�, so we must have u� − 1 ≤ u�.
This means that u� = u� − 1 and the group must be cyclic. □

Finally, let us tackle the general case (u�/u�u� u�)∗ for odd prime u� and
u� ≥ 1.
 Primitive roots 29

Theorem 2.5 Let u� be an odd prime and u� ≥ 1. Then (u�/u�u� u�)∗ ≅ u�(u�−1)u�u�−1 .

Proof. The case u� = 1 was proved above. Let u� ≥ 2. We can use a similar
method as we used with u� = 2. There we were able to start with
5 and repeatedly squared it, but here we will have to be a little bit
more careful. Let u� be a generator for (u�/u�u�)∗ . Then we claim
that either u�u�−1 or (u� + u�)u�−1 is of the form 1 + u�0 u�, where u�0 is
not divisible by u�. Assume that u�u�−1 is not of this form. Then by
the binomial theorem

(u� + u�)u�−1 = u�u�−1 + (u� − 1)u�u�−2 u� + …,

where the rest of the terms are divisible by u�2 . Now by assumption
u�u�−1 = 1 + u�u� with u� divisible by u�, so we see that (u� + u�)u�−1 is
of the wanted form. The rest of the argument goes as with u� = 2,
but instead of squaring we raise the previous number to power u�
repeatedly. Finishing the proof is an exercise. □
u� u�
Let us collect the results of this section. If u� = u�1 1 …u�u�u� , then
u� u�
(u�/u�u�)∗ ≅ (u�/u�1 1 u�)∗ × ⋯ × (u�/u�u�u� u�)∗ , which is cyclic if and
only if u� is one of 2, 4, u�u� , 2u�u� where u� is an odd prime and u� ≥ 1.

2.3 primitive roots

Let u� be such that (u�/u�u�)∗ is cyclic. Often in calculations it

is handy to have a generator for this group. Such generators are
also called primitive roots. No known algorithm exists that can
deterministically find a generator.
We can however reduce the problem to finding a generator for
prime u�. The proof that (u�/u�u� u�)∗ is cyclic showed that if u� is a
generator for u�, then either u� or u� + u� is a generator for u�u� . For
u� = 2u�u� we have the following.

Theorem 2.6 Let u� be an odd prime number and u� ≥ 1. If u� is a generator

for (u�/u�u� u�)∗ , then (1, u�) is a generator for (u�/2u�)∗ × (u�/u�u� u�)∗ ≅
(u�/2u�u� u�)∗ .

Proof. This is clear. □

Squares and square roots 30

Thus if we think of u� as an integer (a representative for an element

of (u�/u�u� u�)∗ ), then the odd one among u� or u� + u�u� represents a
generator for (u�/2u�u� u�)∗ .
Let us consider now the case where u� = u� is a prime and
suppose we want to check whether u� is a generator. Then we should
have ord(u�) = u� − 1. To rule out all other possible orders, we must
u� u�
rule out all divisors of u�−1. Let u�1 1 …u�u� u� be the prime factorization
of u� − 1. Every proper divisor of u� − 1 is divisible by one of the u�
numbers u�−1 u�−1
u� , …, u� . Thus u� is a primitive root if and only if for
1 u�
u�−1
all u� we have u� ≠ 1. This can be checked reasonably fast with
u�u�

exponentiation by squaring.

2.4 squares and square roots

This section concludes the study of the structure of u�/u�u� and

will focus on solving the equation u�2 = u� for a given u� ∈ u�/u�u�.
We will first derive the law of quadratic reciprocity that can be
used to determine when a solution exists, and then consider an
algorithm for actually finding the u�. If such an u� exists, u� is called a
quadratic residue modulo u�. Otherwise it is called a quadratic
non-residue. We will also just say that u� is a square in u�/u�u�.
So when is u� a square modulo u�? By Chinese remainder theo-
u� u�
rem it is clear that if u� has the prime factorization u�1 1 …u�u�u� , then
u�u�
u� must be a square in each of u�/u�u� . Thus it is enough to consider
the case where u� = u�u� for some prime number u� and u� ≥ 1.
Let us start with the case where u� = u� is a prime number.
If u� = 2, then clearly both 0 and 1 are squares, so let us assume
that u� is an odd prime. All the squares in u�/u�u� are given by
2
0, 12 , 22 , …, ( u�−1
2 ) , since u� = (−u�) for all u� ∈ u�/u�u�. Thus
2 2

there are u�+1

2 squares in u�/u�u�. Notice also that the product of two
squares is a square and that the inverse of a square is a square.
In particular if we consider the u�−1
2 non-zero squares, they form a
subgroup of (u�/u�u�) . The set of non-squares is the other coset, the
∗

quotient group must be isomorphic to u�2 , and we have shown the

following:
 Squares and square roots 31

Theorem 2.7 Let u� be a prime number and u�, u� ∈ (u�/u�u�)∗ . Then

− if u� and u� are both squares or non-squares, u�u� is a square,

− if one of u� and u� is a square and the other one is a non-square,

u�u� is a non-square.

To state the law of quadratic reciprocity, we will first define Jacobi

symbols as follows.

Definition 2.8 Let u� ≥ 1 be an odd number and u� ∈ (u�/u�u�)∗ . Consider the map
u�u� ∶ (u�/u�u�)∗ → (u�/u�u�)∗ given by u�u� (u�) = u�u�. The Jacobi symbol
( u�u� ) is defined to be equal to sgn(u�u� ), the sign of the permutation
u�u� .

The following result relating the Jacobi symbol to squares modulo

u� is known as Zolotarev’s lemma.

Theorem 2.9 Let u� be an odd prime and u� ∈ (u�/u�u�)∗ . Then

u� 1, if u� is a square,
( )={
u� −1, if u� is a non-square.

Proof. Because sgn is a homomorphism on permutations, the map

u�∶ u� ↦ u�u� ↦ sgn(u�u� )

is a homomorphism between (u�/u�u�)∗ and the group of two elements

u�2 . Notice that if u� is a generator for (u�/u�u�)∗ , then u�u� is a cycle
of length u� − 1 and therefore has sign −1. This means that u� is
a surjection. It follows that (u�/u�u�)∗ /Ker u� is isomorphic to u�2 .
Since there is only one subgroup of order u�−1 2 in the cyclic group of
order u� − 1, Ker u� must coincide with the subgroup of squares. □

The following, known as Euler’s criterion, is a way of calculating

the Jacobi symbol when the bottom argument is an odd prime.
u�−1
u�
Theorem 2.10 Let u� be an odd prime. Then ( u� ) ≡ u� 2 (mod u�).
 Squares and square roots 32

u�−1
Proof. Let u� ∈ (u�/u�u�)∗ . Clearly u� 2 = ±1 because u�/u�u� is a field. The
u�−1
map u�∶ u� ↦ u� (modu�) can therefore thought of as a homomor-
2

phism (u�/u�u�)∗ → u�2 . It is a surjection because if u� is a generator

u�−1
for (u�/u�u�)∗ , then u� 2 = −1. Thus the kernel of u� is the unique
subgroup of order u�−1 u�
2 on which ( u� ) = 1. □
u�
We will next consider how to calculate ( u� ) efficiently for any odd
coprime numbers u� and u�. Let’s first prove the law of quadratic
reciprocity.

Theorem 2.11 Let u� and u� be odd coprime numbers. Then

u� u� u�−1 u�−1
( ) ( ) = (−1) 2 ⋅ 2 .
u� u�

Proof. Identify each of the rings u�/u�u�, u�/u�u� and u�/u�u�u� with the nat-
ural numbers {0, 1, …, u� − 1}, {0, 1, …, u� − 1} and {0, 1, …, u�u� − 1}
respectively. Then we can give each of the rings a total order in-
duced by the usual order on natural numbers.
Next consider the ring u�/u�u� × u�/u�u�. We can give it two
different total orders:

− The u�-major order <u� where (u�, u�) <u� (u�′ , u�′) if and only if
u� < u�′ or u� = u�′ and u� < u�′ .

− The u�-major order <u� where (u�, u�) <u� (u�′ , u�′) if and only if
u� < u�′ or u� = u�′ and u� < u�′ .

Now there exist unique maps u�u� , u�u� ∶ u�/u�u� × u�/u�u� → u�/u�u�u�
that are isomorphisms from the orders <u� and <u� respectively to
the order defined on u�/u�u�u�. These maps are given by

u�u� (u�, u�) = u�u� + u� and u�u� (u�, u�) = u� + u�u�.

Let u�∶ u�/u�u�u� → u�/u�u�×u�/u�u� be the canonical ring isomorphism

and define two permutations u�u� and u�u� on u�/u�u� × u�/u�u� by
setting u�u� = u� ∘ u�u� and u�u� = u� ∘ u�u� . We have

u�u� (u�, u�) = (u�u� + u�, u�) and u�u� (u�, u�) = (u�, u� + u�u�).
 Squares and square roots 33

The sign of the permutation u�u� is the same as the sign of the
permutation u� ↦ u�u� + u� on u�/u�u� because u� is odd and u�u� is
constant in u�/u�u�. The permutation u� ↦ u�u� + u� is the composition
of the two permutations u� ↦ u�u� and u� ↦ u� + u�. The first one has
u� u�
sign ( u� ) and the second one has sign 1, so sgn(u�u� ) = ( u� ) and
similarly sgn(u�u� ) = ( u�
u� ).
Consider now the permutation u� = u�−1 u�
∘ u�u� = u�u�−1 ∘ u�u� .
The sign of u� is the product of the signs of u�u� and u�u� , which
u�
is ( u� ) ( u�
u� ). We will now double count this sign. Notice that u�
is the unique isomorphism between the total orders <u� and <u� .
To count the sign of the permutation u�, it is enough to count the
number of inversions with respect to the order <u� . By definition
we are looking for the number of pairs (u�, u�), (u�′ , u�′) such that

(u�, u�) <u� (u�′ , u�′) and u�(u�, u�) >u� u�(u�′ , u�′).

Now u�(u�, u�) >u� u�(u�′ , u�′) is equivalent with (u�, u�) >u� (u�′ , u�′), so
by the definition of <u� and <u� we must have u�′ < u� and u� < u�′ .
There are (u� 2 )( 2 ) solutions to these inequalities, so
u�

u� u� u�(u�−1) u�(u�−1) u�−1 u�−1

( ) ( ) = sgn(u�) = (−1) 2 2 = (−1) 2 2 ,
u� u�

which concludes the proof. □

What about ( u�
u� ) when u� is even? The following gives a starting
point.

Theorem 2.12 Let u� ≥ 1 be odd. Then

2 u�2 −1
( ) = (−1) 8 .
u�

Proof. Consider the permutation u�2 ∶ u� ↦ 2u� of (u�/u�u�)∗ . Let us identify

u�/u�u� with the set {0, 1, …, u� − 1} and give it the usual total order
inherited from u�. We can then calculate the sign of u�2 by counting
inversions. For 1 ≤ u� ≤ u�−1 2 the permutation simply takes u� to
u�+1
2u� and for 2 ≤ u� ≤ u� − 1 it takes u� to 2u� − u�. Clearly there
 Squares and square roots 34

u�−1
are no inversions for pairs (u�, u�) in the ranges 1 ≤ u� < u� ≤ 2 or
u�+1
2 ≤ u� < u� ≤ u� − 1. If 1 ≤ u� ≤ u�−1 u�+1
2 and 2 ≤ u� ≤ u� − 1, then
2u� > 2u� − u� if and only if u� ≤ u� + u�−1
2 . Thus we have
u�−1 u�−1
2 2 u�−1 u�+1
u� − 1 u� + 1 2 2 u�2 − 1
∑(u� + − + 1) = ∑ u� = =
u�=1
2 2 u�=1
2 8
u�2 −1
inversions in total, giving sgn(u�2 ) = (−1) 8 . □
The final piece in the repertoire for Jacobi symbols is that it is
completely multiplicative in both the top argument and the bottom
argument.
Theorem 2.13 Let u� ≥ 1 be odd and u�, u� ∈ (u�/u�u�)∗ . Then we have

u�u� u� u�
( ) = ( )( ).
u� u� u�

Similarly if u�, u� ≥ 1 are odd and u� ∈ (u�/u�u�u�)∗ , then

u� u� u�
( ) = ( )( ),
u�u� u� u�

where on the right hand side we have identified u� with its im-
ages in (u�/u�u�)∗ and (u�/u�u�)∗ under the canonical quotient maps
u�/u�u�u� → u�/u�u� and u�/u�u�u� → u�/u�u�.
Proof. The first claim is trivial by the definition of Jacobi symbol.
The second claim follows from the first one by picking odd
representatives for u� and using the law of quadratic reciprocity.
□

We are now in the position where we can calculate ( u�

u� ) for any
odd u� efficiently by using the following method:
1. If u� is larger than u�, reduce it to the range 1 ≤ u� ≤ u� − 1.
u� ′
2. If u� is even, reduce ( u� 2 u�
u� ) to ( u� ) ( u� ) where u� is odd by using
′

the multiplicativity.
 Squares and square roots 35

u� u� u�2 −1
3. Any term of the form ( 2u� ) equals ( u�2 ) = (−1)u� 8 .

4. For terms of the form ( u� u� ) with both u� and u� odd we can use
the law of quadratic reciprocity to swap the places of u� and u�,
u�−1 u�−1
multiply by (−1) 2 2 and start over from step 1.

We already know how to efficiently check for any prime u�

whether u� ∈ u�/u�u� is a square (either use Euler’s criterion or the
above algorithm to calculate the Jacobi symbol). What is left to do
to answer completely when u� is a square modulo u� is considering
prime powers. Let us start with powers of two.

Theorem 2.14 The only squares modulo 4 are 0 and 1. Let u� = 2u� with u� ≥ 3.
Then u� is a square modulo u� if and only if it is of the form 4u� (8u�+1)
for some u� ≥ 0 and u� ∈ u�.

Proof. Exercise. □

For odd prime powers we have the following.

Theorem 2.15 Let u� be an odd prime and u� ≥ 1. Then u� ∈ u�/u�u� u� is a square if

and only if u� is 0 or it is of the form u� = u�u� u�, where u� is a square
in (u�/u�u�)∗ and u� ≥ 0 is even.

Proof. Exercise. □

Having classified which numbers have square roots modulo u�, it is

now time to start thinking about how to find them. It is enough to
work in the case where u� = u�u� is a prime power.
Let us first assume that u� = 2u� for some u� ≥ 3 and that
u� = 8u� + 1 is odd. By induction we may assume that we have
already solved u�2 = u� in u�/2u�−1 u�. Pick a representative of u� in
u�/2u� u�, and consider u�2 and (u� + 2u�−2 )2 = u�2 + 2u�−1 u�. They are
different since u� is odd, and one of them must be u�. The base case
where u� = 3 is trivial, just choose u� = ±1 or u� = ±3. Starting
from these, the method gives four distinct square roots for each u�
when u� ≥ 3. If u� is of the general form 4u� (8u� + 1), then we can first
 Squares and square roots 36

solve the square root of (8u� + 1) and multiply the obtained number
by 2u� to get a square root of u�.
Similar ‘lifting’ works also for odd prime powers. Assume that
u� = u�u� , u� is not divisible by u�, and we have already solved u�2 = u� in
u�/u�u�−1 u�, pick a representative of u� in u�/u�u� u� and let u� be such that
u�2 +u�u�u�−1 = u� in u�/u�u� u�. Then (u�+u�2−1 u�−1 u�u�−1 )2 = u�2 +u�u�u�−1 ,
so u� + u�2−1 u�−1 u�u�−1 is our solution in u�/u�u� u�. In total there will
be two solutions in this case since there are two solutions in u�/u�u�.
Thus all that is left is to handle the base case u� = u�, where u�
is an odd prime. In the case u� ≡ 3 (mod 4) this is easy.

Theorem 2.16 If u� ≡ 3 (mod 4) and ( u�u� ) = 1, then the solutions to u�2 = u� are
u�+1
given by ±u� 4 .

Proof. Exercise. □

When u� ≡ 1 (mod 4) no general formula is known. We will de-

scribe below the so called Tonelli–Shanks algorithm for calculating
a solution in this case.
Let u� be an odd prime and assume that u� is a square modulo
u�. Tonelli–Shanks begins by writing u� − 1 as u� − 1 = 2u� u�, where u� is
odd. Let u� ∈ (u�/u�u�)∗ be a non-square generator for the subgroup
of order 2u� . Such a generator can be found by picking a non-square
u� (by testing numbers randomly – half of the candidates are non-
square and thus this should take on average 2 tries) and setting
u�−1
u� = u�u� . (Note that (u�u� )2 = u� 2 = −1, so u� must have order 2u� .)
u�−1

Then u�u� lies in the subgroup generated by u�, and we can thus write

u�u�+1 = u�u�u� = u�u�u�

for some integer u�. Because u� is a square, also u�u� must be a square,
implying that u� must be even. Thus if we are capable of solving the
discrete logarithm problem in the 2u� element subgroup of (u�/u�u�)∗ ,
u�+1 u�
then u� 2 u�− 2 is the square root we are after and we are done.
So here is the algorithm. We will set u�0 = u�u� and u�0 = u�.
On each step u� ≥ 0 our goal is to recursively solve the discrete
logarithm problem u�u�u� = u�u� for u�(u�) . We assume that the order of
(u�)
 Squares and square roots 37

u�u� is 2u�u� for some u�u� ≥ 0, that u�u� lies in the subgroup generated by
u�u� and that u�(u�) will be even, so that we may write it in binary as
(u�) (u�) (u�)
u�(u�) = u�1 21 + u�2 22 + … + u�u�u� −1 2u�u� −1 .

Now if u�u� = 1, we are done since we can simply take u�(u�) = 0.

Otherwise we must have u�u� ≥ 2 and therefore we can let u�u� be the
smallest integer in the range 0 < u�u� < u�u� such that u�2u� u� = 1. Then
u�

(u�) (u�)
(u�) u�u� u�1 2u�u� +1 +…+u�u� 2u�u� −1
1 = u�u�u� 2
= u�u� u� −u�u� −1
,
(u�) (u�)
so we must have u�1 = … = u�u�u� −u�u� −1 = 0. Similarly since u�2u� u�
u� −1
≠ 1,
we must have
(u�)
(u�) u�u� −1 u�u�u� −u�u� 2u�u� −1
1 ≠ u�u�u� 2
= u�u� ,
(u�)
so u�u�u� −u�u� = 1. This means in particular that
(u�) (u�)
u�u� −u�u� u�u� 2u�u� −u�u� +1 +…+u�u� −1 2u�u� −1
u�u�−2 u�u� = u�u� u� −u�u� +1 u�
,

so if we let u�u�+1 ≔ u�u�−2 u�u� and u�u�+1 ≔ u�u�2 , then we may

u�u� −u�u� u�u� −u�u�

(u�+1) (u�+1) (u�) (u�+1)

recursively solve for and set
u�1 , …, u�u�u� −1 = u�u� for 1 ≤ u�u�u� −u�u� +u�
u� ≤ u�u� − 1 to obtain the solution for u� .
(u�)

In the context of Tonelli–Shanks, instead of keeping around

the digits u�(u�) we simply update a variable that will contain the
square root in the end. This variable, which we may call u�, is first
u�+1
initialized to u� ≔ u� 2 . Then at the end of u�th step we multiply it
by u�u�−2 u� u� , which takes care of the digit of u�(0) that we found on
u� −u� −1

(0) (0) (0) u�+1

this step. In the end u� will be equal to u�−(u�1 +u�2 2+…+u�u�−1 2 ) u� 2 ,
u�−2

which is what we wanted.

Finally notice that we don’t have to keep the generator u� itself
around, only its inverse. This leads us to the following code.

Algorithm 2.17 (Tonelli–Shanks)

int64_t tonelli_shanks(int64_t a, int64_t p)

Squares and square roots 38

{
if(p % 4 == 3) {
return power_mod(a, (p+1)/4, p);
}
int64_t odd=p-1;
int64_t s=0;
while(odd%2 == 0) {
odd/=2;
s++;
}
int64_t g=2;
while(g < p) {
if(power_mod(g, (p-1)/2, p) == p-1) break;
g++;
}
g = power_mod(g, odd, p);
int64_t tmp=power_mod(a, (odd - 1)/2, p);
int64_t x=tmp*tmp%p*a%p;
int64_t r=tmp*a%p;
while(x != 1) {
int64_t t=1;
int64_t tmp=x*x%p;
while(tmp != 1) {
tmp=tmp*tmp%p;
t++;
}
tmp=power_mod(g, (1 << (s-t-1)), p);
r=r*tmp%p;
g=tmp*tmp%p;
x=x*g%p;
s=t;
}
return r;
}
 more about primes

3
In this chapter we will look at a few problems specifically related
to the primes in u�, such as testing whether a number is prime or
counting the number of primes less than some given number u�.

3.1 miller–rabin primality test

In this section we will present a simple method for checking whether

a given number is prime. The algorithm is probabilistic, and there-
fore only tells us that a number is probably prime.
There are also fast It should however be noted that the Miller–Rabin test can
deterministic primal- easily be made into a deterministic test for ‘small’ ranges, and at
ity tests for general the end of the section we will present a variation, which can without
ranges, for example fail decide the primality of any number in the range 1, …, 264 .
the AKS primal- Let us now describe the test. Assume that u� is an odd prime
ity test. These al- number and let u� ∈ (u�/u�u�)∗ . Then the order of u� must divide
gorithms are how- u� − 1, which we can write in the form u� − 1 = 2u� u� where u� is odd.
Then u�2 u� = 1 for some smallest u� in the range 0 ≤ u� ≤ u�. If u� ≥ 1,
u�
ever out of the
then we see that the element u� = u�2 u� satisfies the polynomial
u�−1
scope of this book.
equation u�2 = 1 in the field u�/u�u�. This equation has −1 and 1 as
its roots and since u� is not 1, we must have u� = −1. Therefore one
of the following happens: Either

− u�u� = 1, or

= −1 for some 0 ≤ u� ≤ u� − 1.
u�
− u�2 u�

Conversely if neither of these happen, u� is not a prime. This is the

basis for the Miller–Rabin test. The numbers u� that fail the test
are called witnesses of compositeness for u�.

Algorithm 3.1 (Miller–Rabin primality test) Let u� be the number we want to test
for primality. We will randomly choose elements u� ∈ (u�/u�u�)∗ and
see if both of the conditions above fail. In this case we will know
that u� is not a prime. Otherwise after suitably many elements u�
have been tested, we will conclude that u� is probably a prime.
Notice that if u� ∈ u�/u�u� and u� does not belong to the multi-
plicative group, then u� will automatically fail the test, so we can
simply choose our u� from the range 2 ≤ u� ≤ u� − 1.
Miller–Rabin primality test 40

bool is_witness(uint64_t a, uint64_t evenpart,

uint64_t oddpart, uint64_t p) {
// We have to use 128-bit integers to be able to
// multiply two 64-bit ones.
//
// power_mod(a, k, p) calculates a^k modulo p
// doing exponentiation by squaring
uint128_t u = power_mod(a, oddpart, p);
if(u == 1) {
return false;
}
for(uint64_t j=1;j<evenpart;j*=2) {
if(u == p-1) return false;
u*=u; u%=p;
}
return true;
}

const int64_t NUMBER_OF_WITNESSES = 10;

bool is_prime_miller_rabin(uint64_t p) {
uint64_t oddpart=p-1;
uint64_t evenpart=1;
while(oddpart%2 == 0) { evenpart*=2; oddpart/=2; }

std::default_random_engine gen;
std::uniform_int_distribution<int64_t> unif(2, p-1);

for(uint64_t i=0;i<NUMBER_OF_WITNESSES;i++)
if(is_witness(unif(gen), evenpart, oddpart, p))
return false;
return true;
}

One may ask how reliable the test is. It is possible to show that if
u� is the number of potential witnesses we test, the probability that
we claim that a composite number is prime is less than 4−u� .
We can make a deterministic version of Miller–Rabin by choos-
ing a fixed set of numbers u� to test. Indeed at [Link]
-[Link] there are precalculated sets of numbers
available that work for large ranges of numbers. In particular the
seven number set
 Counting prime numbers 41

{2, 325, 9375, 28178, 450775, 9780504, 1795265022}

is claimed to work for every number of size at most 264 . The al-
gorithm has to be modified so that we test the numbers in the set
in order, and if a number is divisible by u�, then we report that u�
is prime. The set has been chosen so that the previous numbers
would have rejected any number u� that is composite and for which
the current u� is divisible by u�, so that no false-positives occur. Be-
low is an implementation of this fast primality checking algorithm.

Algorithm 3.2 (Deterministic Miller–Rabin for 64-bit integers)

bool is_prime_miller_rabin_deterministic(uint64_t p) {
uint64_t odd=p-1;
uint64_t even=1;
while(odd%2 == 0) { even*=2; odd/=2; }

const int64_t bases[7] = {2, 325, 9375, 28178, 450775,

9780504, 1795265022};

for(uint64_t i=0;i<7;i++) {
uint64_t a = bases[i]%p;
if(a == 0) return true;
if(is_witness(a, even, odd, p)) return false;
}

return true;
}

3.2 counting prime numbers

Let u� ≥ 1 be a real number and define the prime-counting func-

tion u� by setting

u�(u�) = |{1 ≤ u� ≤ u� : u� is a prime number}.

In this section we will present a variant of the Meissel–Lehmer

algorithm that can calculate u�(u�) in u�(u�2/3+u� ) time and space. It is
possible to reduce the space requirement to u�(u�1/2+u� ), but we have
decided to keep things simple here. An optimized implementation
 Counting prime numbers 42

can be found for example in the Haskell library arithmoi or in

sage.
The algorithm is based on the following simple but clever
inclusion-exclusion scheme. Let us denote the number of positive
integers at most u� and not divisible by any of the u� first primes by
u�(u�, u�). Furthermore denote by u�u� (u�, u�) the number of integers at
most u� and having exactly u� prime factors all of which are strictly
greater than the u�th prime u�u� . Then we clearly have
∞
∑ u�u� (u�, u�) = u�(u�, u�).
u�=0
√
On the other hand if we let u� = u� and u� = u�(⌊ 3 u�⌋), then we have
u�u� (u�, u�) = 0 for u� ≥ 3, u�0 (u�, u�) = 1 and u�1 (u�, u�) = u�(u�) − u�. It
follows that

u�(u�) = u�(u�, u�) + u� − 1 − u�2 (u�, u�).

To calculate u�2 (u�, u�) we may use the formula

u� √ √ √
2u�2 (u�, u�) = ∑ (u�( ) − u�(⌊ 3 u�⌋)) + u�(⌊ u�⌋) − u�(⌊ 3 u�⌋),
√ √ u�
⌊ 3 u�⌋<u�≤⌊ u�⌋
u� a prime

which
√ follows from the fact that every number u�u� ≤ u� with u�, u� >
3
u� will be counted
√ twice√ in the sum, except when u� = u�, which
the term u�(⌊ u�⌋) − u�(⌊ u�⌋) corrects.
3

The function u�(u�, u�) on the other hand satisfies the recursion
u�
u�(u�, u�) = u�(u�, u� − 1) − u�( , u� − 1).
u�u�

The algorithm is completed by calculating u�(u�,√u�) using this recur-

√
sion and memoizing the values u�(u�, u�) for u� ≤ 3 u� and u� ≤ u�( 3 u�).

Algorithm 3.3 Here is an implementation of a function primes_pi that calculates

the number of primes according to the method outlined above.

uint64_t phi(vector<vector<int64_t>> &memo,

Counting prime numbers 43

const vector<int64_t> &primes,

uint64_t m, uint64_t k) {
if(k == 0) return m;
if(m < [Link]() && k < memo[m].size()) {
if(memo[m][k] != -1) return memo[m][k];
int64_t res=phi(memo, primes, m, k-1) -
phi(memo, primes, m/primes[k-1], k-1);
memo[m][k]=res;
return res;
}
return phi(memo, primes, m, k-1) -
phi(memo, primes, m/primes[k-1], k-1);
}

uint64_t primes_pi(uint64_t limit) {

if(limit < 2) return 0;
uint64_t limit2=sqrtl(limit);
uint64_t limit3=cbrtl(limit);
uint64_t limit23=limit/limit3;
vector<int64_t> sieve(limit23+1, 0);
vector<int64_t> pi(limit23+1,0);
vector<int64_t> primeslow;
vector<int64_t> primeshigh;
for(int64_t p=2;p<=limit23;p++) {
pi[p]=pi[p-1];
if(sieve[p] == 0) {
pi[p]++;
if(p <= limit3) primeslow.push_back(p);
else if(p <= limit23) primeshigh.push_back(p);
for(int64_t i=p;i<=limit23;i+=p) sieve[i]=p;
}
}
uint64_t P2=pi[limit2] - pi[limit3];
for(uint64_t i=0;i<[Link]();i++) {
P2+=pi[limit/primeshigh[i]] - pi[limit3];
}
P2/=2;
vector<vector<int64_t>> memo(limit3,
vector<int64_t>(limit3,-1));
return phi(memo, primeslow, limit, pi[limit3]) +
pi[limit3] - 1 - P2;
}
 gaussian integers

4
In this chapter we will use the ring theory we have developed in the
context of Gaussian integers. Gaussian integers are numbers of
the form u� + u�u�, where u� and u� are integers. The set of all Gaussian
integers is denoted by u�[u�]. They are useful for many tasks in
classical number theory, mainly because they allow factoring u�2 +u�2
as (u� + u�u�)(u� − u�u�).

4.1 structure of u�[u�]

The Gaussian integers are reasonably well-behaved, since like inte-

gers, they form a Euclidean domain.

Theorem 4.1 u�[u�] is a Euclidean domain.

Proof. Define u�∶ u�[u�] → u� by setting u�(u� + u�u�) = |u� + u�u�|2 = u�2 + u�2 . We
must show that for any u�, u� ∈ u�[u�], u� ≠ 0, there exist u�, u� ∈ u�[u�]
such that

u� = u�u� + u�, u�(u�) < u�(u�).

To do this, notice that is enough to show that there exists u� ∈ u�[u�]

such that
u�
∣ − u�∣ < 1.
u�

Notice that there But it is clear that this happens, because if we choose u� to be
may be up to four a nearest Gaussian integer to u�u� in the complex plane, then its
nearest Gaussian in- distance to u�
cannot be more than half of the diagonal of the unit
u�
tegers for a given √
2
complex number. square, which is 2 < 1. □
Here it is enough to
It follows immediately that many of the good properties we are used
choose one of them.
to while working with integers apply to Gaussian integers too. In
particular they are a PID and a UFD.
Let u� (u�) = |u�|2 for all u� ∈ u�[u�]. The function u� ∶ u�[u�] → u�
is called a norm. Its main property is that u� (u�u�) = u� (u�)u� (u�).
Therefore if u� ∈ u�[u�] is a unit, we must have
 Structure of u�[u�] 45

1 = u� (1) = u� (u�u�−1 ) = u� (u�)u� (u�−1 ),

which means that u� (u�) = u� (u�−1 ) = 1. Hence the only possible

units in u�[u�] are {1, u�, −1, −u�}, and one easily checks that these
actually are units. Thus u� ∈ u�[u�] is a unit if and only if u� (u�) = 1.
The next big question is what are the primes in u�[u�]. For this
we have the following.

Theorem 4.2 Let u� ∈ u�[u�]. Then u� a prime element if and only if it is one of the
following up to multiplication by a unit:

− 1 + u�,

− u� + u�u�, where u�, u� ∈ u� and u�2 + u�2 is a prime number that is 1

modulo 4, or

− u�, where u� ∈ u� is a prime number that is 3 modulo 4.

Proof. Assume first that u� = 1 + u�. Then u� is irreducible since if u� = u�u�

with u�, u� ∈ u�[u�], we must have 2 = u� (u�) = u� (u�)u� (u�), which
implies that either u� (u�) or u� (u�) must be 1, so either u� or u� is a
unit.
Similarly assume that u� = u� + u�u�, where u�2 + u�2 is a prime in u�
that is 1 modulo 4. Then if u� = u�u�, we must have u�2 + u�2 = u� (u�) =
u� (u�)u� (u�), so that either u� (u�) or u� (u�) is 1, meaning that u� or u� is
a unit.
Thirdly assume that u� = u�, where u� ≡ 3 (mod 4). Then u� is
irreducible since if u� = u�u� with non-units u�, u� ∈ u�[u�], we must have
u� 2 = u� (u�)u� (u�), so u� = u� (u�) = u� (u�). Notice that u� (u�) is a sum
of two squares in u�. This is however not possible since squares are
either 0 or 1 modulo 4, and u� (u�) = u� is 3 modulo 4.
Assume then that u� ∈ u�[u�] is a prime and write u� = u� + u�u�
u�
with u�, u� ∈ u�. Let u�1 1 …u�u�u�u� be the prime factorization of u� (u�) =
(u� + u�u�)(u� − u�u�) in u�. We see that u� = u� + u�u� must divide one of u�u� .
Then it follows that u� (u�)|u� (u�u� ), so either u� (u�) = u�u� or u� (u�) = u�u�2 .
If u� (u�) = u�2 + u�2 = u� with u� ∈ u� a prime, then either u� = 2
or u� ≡ 1 (mod 4), giving the first and second options on the list.
If u� (u�) = u� 2 with u� ∈ u� a prime, then notice that u� (u�) | u� (u�),
so u� = u�/u� is a Gaussian integer with norm 1, i.e. a unit. Thus
Sums of squares 46

u� = u�u� and also u� is a prime in u�[u�]. This means that we cannot

have u� = 2. We also cannot have u� ≡ 1 (mod 4) because then
u�2 ≡ −1 (mod u�) has a solution, which means that u� divides
u�2 + 1 = (u� + u�)(u� − u�). If u� were prime in u�[u�], one of u�u� + u�u� or
u�
u�− u�u� would be in u�[u�], but this is clearly not the case. The only
option left is that u� ≡ 3 (mod 4), and this is the third option on
the list. □

Another way to look at the result is that integer primes change

when looked in u�[u�], so that

− 2 becomes a unit times (1 + u�)2 , i.e. associated to a square of a

Gaussian prime,

− primes u� that are 1 modulo 4 split into two Gaussian primes

u� + u�u� and u� − u�u� such that (u� + u�u�)(u� − u�u�) = u�,

− primes u� that are 3 modulo 4 stay primes in u�[u�].

4.2 sums of squares

The classification of primes in u�[u�] immediately leads to a classifi-

cation of the numbers u� ∈ u� that are sums of two squares. Indeed,
let u� ≥ 1 and assume that its prime factorization is
u� u� u� u�
2u�0 u�1 1 …u�u� u� u�1 1 …u�u� u� ,

where u� are primes that are 1 modulo 4 and u� are primes that
are 3 modulo 4. The number u� is a sum of squares if and only if
there exists u� ∈ u�[u�] such that u� (u�) = u�u� = u�. But by unique
factorization this means that u� must have a factor 1 + u� occuring
u�0 times, a split factor occuring u�u� times for 1 ≤ u� ≤ u� and u�u�
occuring u�u� /2 times for 1 ≤ u� ≤ u�. This is possible if and only if all
u�u� are even.
It is also easy to count the number of ways an integer u� can
be expressed as a sum of squares. Let
u� u� u� u�
u� = 2u�0 u�1 1 …u�u� u� u�1 1 …u�u� u� ,
Pythagorean triples 47

where u�u� are primes that are 1 modulo 4 and u� are primes that
are 3 modulo 4. Let u�(u�) be the number of ways to write u� =
u�2 + u�2 where u�, u� ∈ u�. Then if one of u�u� is odd, we must have
u�(u�) = 0. Otherwise we must consider all possible ways of writing
u� /2
u� = (u� + u�u�)(u� − u�u�). Now in any case u� + u�u� must have u�u� u� as a
factor, so there is no choice involved there. Similarly it must have
(1 + u�)u�0 as a factor. Let u� + u� = u�u� for some 1 ≤ u� ≤ u�. To have
u�
u�u� u� in the prime factorization of (u� + u�u�)(u� − u�u�), we can choose
(u�u� + u�u� u�)u� (u�u� − u�u� u�)u� with u� + u� = u�u� to be a factor of u� + u�u�. Here
we have written u�u� = (u�u� + u�u� u�)(u�u� − u�u� u�) and the exponents u� and
u� can be chosen in u�u� + 1 different ways for each u�. Finally we can
multiply our number by any of the 4 units, which gives us in total

0, if any u�u� is odd,

u�(u�) = {
4(u�1 + 1)…(u�u� + 1), otherwise

ways.

4.3 pythagorean triples

A triple (u�, u�, u�) of positive integers is called a Pythagorean triple

if u�2 + u�2 = u�2 . The name Pythagorean triple comes from the
fact that u�, u� and u� can be thought of as the sides of a right-
angled triangle satisfying Pythagorean theorem. The most famous
example of a Pythagorean triple is (3, 4, 5).
A Pythagorean triple is called primitive if gcd(u�, u�, u�) = 1.
All non-primitive triples can be obtained from a unique primitive
triple by multiplying u�, u� and u� by a common constant. Therefore
we will next focus on how to generate primitive triples.
Assume that u�2 + u�2 = u�2 and gcd(u�, u�, u�) = 1. We can factor
the equation in u�[u�] to get

(u� + u�u�)(u� − u�u�) = u�2 .

Now notice that u� + u�u� and u� − u�u� are coprime. Indeed, if this was
not the case, then 2u� = (u� + u�u�) + (u� − u�u�) and u� + u�u� would have
a common factor. Because u� and u� are coprime, this implies that
 Pythagorean triples 48

2 = −u�(1 + u�)2 and u� + u�u� have a common factor. In particular we

see that u� − u�u� has factor 1 − u�, so u� is divisible by 2. But this is not
possible because then u� and u� are odd, which makes u�2 + u�2 ≡ 2
(mod 4) and u�2 ≡ 0 (mod 4).
It follows that u� + u�u� and u� − u�u� are squares times a unit,

u� + u�u� = u�(u� + u�u�)2 = u�(u�2 − u�2 + 2u�u�u�).

Now we may notice that (u� + u�u�)(u� − u�u�) = (u�2 + u�2 )2 , so u� =

u�2 + u�2 . Without loss of generality we may pick u� = 1, so that
u� = u�2 − u�2 and u� = 2u�u�. Then to satisfy gcd(u�, u�, u�) = 1, we
must have gcd(u�, u�) = 1 and exactly one of u�, u� must be odd.
Thus we have shown the following.

Theorem 4.3 The primitive Pythagorean triples are of the form

u� = u�2 − u�2 , u� = 2u�u�, u� = u�2 + u�2 ,

where 1 ≤ u� ≤ u� − 1, gcd(u�, u�) = 1, and exactly one of u�, u� is

odd.

There is also an alternative way to generate primitive Pythagorean

triples that is useful because it does not require checking for copri-
mality or parity of numbers. This method starts from the triple
(3, 4, 5) and then recursively produces new triples by applying the
following three linear transformations:

1 2 2 −1 2 2 1 −2 2
⎛
⎜2 1 2⎞⎟, ⎛
⎜−2 1 2⎞
⎟, ⎛
⎜2 −1 2⎞
⎟
⎝2 2 3⎠ ⎝−2 1 3⎠ ⎝2 −2 3⎠

The proof that this works is left as an exercise.

 continued fractions

5 5.1 definitions and examples

Suppose that u� is a real number and let u�0 ≔ u�. If u�0 is not an
integer, then we may write

u�0 = u�0 +
1
,
u�1
1
where u�0 = ⌊u�0 ⌋ and u�1 = u� −⌊u� > 1. If u�1 is not an integer,
0 0⌋
then we may continue and write
1
u�1 = u�1 + ,
u�2
1
where u�1 = ⌊u�1 ⌋ and u�2 = u�1 −⌊u�1 ⌋ > 1. Continuing like this we get
the (formal) equality
1
u� = u�0 + 1
,
u�1 + 1
u�2 + …

where the right hand side is called a continued fraction with

coefficients u�0 , u�1 , u�2 , …. We will use the shorthand notation
1
[u�0 , u�1 , u�2 , …] ≔ u�0 + 1
u�1 + 1
u�2 + …

to write continued fractions. The number of coefficients can be

either finite or infinite.
By the continued fraction expansion of a real number u� we
mean the continued fraction obtained by using the above procedure.
In particular u�u� are all integers, and for all u� ≥ 1 we have u�u� > 0.

Exercise 5.1 Show that if u� is not an integer and the continued fraction expan-
sion of u� is finite, then the last coefficient of the expansion is at
least 2.
 Definitions and examples 50

At this point continued fractions are just formal objects defined by

the coefficients u�u� , which we can in general assume to be arbitrary
real numbers. If the continued fraction is finite it is straightforward
to assign a value to it, assuming that the expression makes sense
(meaning that there is no division by 0). It is less clear how we
should interpret an infinite continued fraction, but we will soon
show that if we truncate it to a finite number of coefficients then
the sequence of such truncations converges if we assume that all of
the coefficients are integers. We can then say that the value of the
infinite continued fraction is the limit of its truncations.

Theorem 5.2 The continued fraction expansion of a real number u� has finitely
many coefficients if and only if u� is rational.

Proof. It is clear that if the expansion of u� has finitely many coefficients

then u� is rational. Let us thus assume that there exists a rational
number whose continued fraction expansion has infinitely many
terms. Then in particular there exists such a rational number u�u�
with the smallest possible denominator u� > 0. Now the first step in
the expansion procedure is
u� u� 1
=⌊ ⌋+ ,
u� u� u�
1
u�
u� −⌊ u� ⌋

so it follows that the continued fraction expansion of

1 u�
u�
=
u� − ⌊ u�u� ⌋ u� − u� ⌊ u�u� ⌋

has infinitely many terms. Note however that 0 ≤ u� − u� ⌊ u�u� ⌋ < u�,
which is a contradiction. □

Let [u�0 , u�1 , u�2 , …] be a continued fraction. Then its u�th conver-
gent is defined to be the continued fraction [u�0 , u�1 , u�2 , …, u�u� ]. If
the coefficients u�0 , …, u�u� are integers, it is a rational number and
we will use the convention that its numerator and denominator (in
lowest terms) are denoted by u�u� and u�u� respectively.
 Definitions and examples 51

Theorem 5.3 The u�u� and u�u� satisfy the recursion relations

u�u� = u�u� u�u�−1 + u�u�−2 ,

u�u� = u�u� u�u�−1 + u�u�−2 ,

for all u� ≥ 0 when we set

u�−2 ≔ 0, u�−2 ≔ 1, u�−1 ≔ 1, u�−1 ≔ 0.

Proof. Our first claim is that if u�u� and u�u� are defined via the given recur-
sion relations, then u�u�u� = [u�0 , u�1 , …, u�u� ]. The proof will proceed by
u�
induction on the length of the continued fraction and we do not as-
sume that u�0 , u�1 , …, u�u� are integers. It is clear that the claim holds
for all continued fractions of length 1. Assume that the recursion
relations hold for all continued fractions of length u�. Then we can
bunch together the last two coefficients of the continued fraction
[u�0 , u�1 , …, u�u� ] and write it as [u�0 , u�1 , …, u�u�−2 , u�u�−1 + u�1 ], which is
u�
now a continued fraction of length u�. It has the same initial seg-
ment [u�0 , u�1 , …, u�u�−2 ] as [u�0 , u�1 , …, u�u� ] does, so the convergents up
to u�u�u�−2 are equal for them. By induction [u�0 , u�1 , …, u�u�−2 , u�u�−1 + u�1 ]
u�−2 u�
is given by
1
(u�u�−1 + u�u� )u�u�−2 + u�u�−3 u�u� (u�u�−1 u�u�−2 + u�u�−3 ) + u�u�−2
=
(u�u�−1 + 1 u�u� (u�u�−1 u�u�−2 + u�u�−3 ) + u�u�−2
u�u� )u�u�−2 + u�u�−3
u�u� u�u�−1 + u�u�−2
= ,
u�u� u�u�−1 + u�u�−2

which shows that the claim holds for continued fractions of length
u� + 1.
The second claim is that u�u� and u�u� are coprime integers if
u�0 , u�1 , …, u�u� are integers. That u�u� and u�u� are integers is obvious
from the recursion. The coprimality follows from the next theorem.
□

Theorem 5.4 The numbers u�u� and u�u� satisfy u�u� u�u�−1 − u�u�−1 u�u� = (−1)u�−1 for all
u� ≥ −1.
 Definitions and examples 52

Proof. It is trivial to check that u�−1 u�−2 − u�−2 u�−1 = 1. Assume then that
u� ≥ 0 and that the claim holds for u� − 1. We have

u�u� u�u�−1 − u�u�−1 u�u� = (u�u� u�u�−1 + u�u�−2 )u�u�−1 − u�u�−1 (u�u� u�u�−1 + u�u�−2 )
= − (u�u�−1 u�u�−2 − u�u�−2 u�u�−1 ) = (−1)u�−1 ,

so the claim also holds for u�. We are done by induction. □

An important corollary of this theorem is the following.

Theorem 5.5 The convergents of any infinite continued fraction [u�0 , u�1 , u�2 , …]
with integer coefficients such that u�u� > 0 for u� ≥ 1 converge to
some number u�. Moreover every even convergent is strictly less
than u�, every odd convergent is strictly larger than u�, and the
distance to u� goes to 0 monotonically.

Proof. We can rewrite the equation in Theorem 5.4 as

u�u� u�u�−1 (−1)u�−1

− = .
u�u� u�u�−1 u�u�−1 u�u�

Since u�u� → ∞ monotonically, this shows that the convergents os-

cillate with amplitude going monotonically to 0. □

Continued fractions can be thought of as another way of repre-

senting real numbers, a little bit like the decimal number sys-
tem. Like in the decimal system, the representation is essentially
unique. With decimal numbers the non-uniqueness comes in the
form 1 = 0.999…, and with continued fractions it comes in the
form 1 = 0 + 11 . To get a unique representation with the decimal
numbers we can prohibit infinite sequence of nines, and similarly
with continued fractions we may require that the last coefficient is
not 1, except if the last coefficient is also the first one.

Definition 5.6 We say that [u�0 , u�1 , …] is in the canonical form if

 Definitions and examples 53

− u�0 , u�1 , … are integers,

− u�u� > 0 for all u� ≥ 1, and

− if there are finitely many coefficients, the last coefficient is at

least 2.

Theorem 5.7 There is a bijective correspondence between the real numbers and
continued fractions in the canonical form given by the mapping
from a number to its continued fraction expansion.

Proof. From Theorem 5.2 we already know that the rational numbers and
finite continued fractions in the canonical form are in a one-to-one
correspondence.
Recall from the proof Let u� be an irrational number. By the definition of the
of Theorem 5.3 that continued fraction expansion and the convergent recursion we have
the convergent re-
cursion works also
u�u� u�u�+1 + u�u�−1
u� = [u�0 , u�1 , …, u�u� , u�u�+1 ] =
for non-integers. u�u� u�u�+1 + u�u�−1

for some real number u�u�+1 > 1. From Theorem 5.4 it follows that

u�u� u� u� − u�u� u�u�−1 1

∣u� − ∣ = ∣ u�−1 u� ∣< .
u�u� u�u� (u�u� u�u�+1 + u�u�−1 ) u�u� (u�u� + u�u�−1 )

The right-hand side tends to 0 as u� goes to ∞. This shows that

there is an injection from the irrational numbers to the infinite
continued fractions in the canonical form.
It remains to show that the if two infinite fractions in the
canonical form have the same value, their coefficients are equal.
1
Notice that if u� = [u�0 , u�1 , …], then ⌊u�⌋ = u�0 and u�1 = u�−⌊u�⌋ =
[u�1 , u�2 , u�3 , …]. Thus by running the continued fraction expansion
process on u� we see that the coefficients u�0 , u�1 , … are uniquely de-
termined. □

It is sometimes also useful to think about the numerator and de-

nominator of a general finite continued fraction [u�0 , u�1 , u�2 , …, u�u� ] as
polynomials in the coefficients u�0 , …, u�u� . We will let u� (u�0 , u�1 , …, u�u� )
denote the numerator and u�(u�0 , u�1 , …, u�u� ) the denominator. It is
 Definitions and examples 54

easy to see (compare Theorem 5.3) that both u� and u� satisfy the
recursion relations

u� (u�0 , …, u�u� ) = u�u� u� (u�0 , …, u�u�−1 ) + u� (u�0 , …, u�u�−2 ),

u�(u�0 , …, u�u� ) = u�u� u�(u�0 , …, u�u�−1 ) + u�(u�0 , …, u�u�−2 )

with u� () = 1, u�() = 0, u� (u�0 ) = u�0 and u�(u�0 ) = 1. Using these it

is also straightforward to show by using induction that

u�(u�0 , u�1 , …, u�u� ) = u� (u�1 , u�2 , …, u�u� ).

Quite interestingly the following property also holds.

Theorem 5.8 We have u� (u�0 , u�1 , …, u�u� ) = u� (u�u� , u�u�−1 , …, u�0 ).

Proof. It is easy to check that the claim holds when u� = 0, 1, 2, 3. Assume

that u� ≥ 4 and that we have shown the claim up to u� − 1. Then
by induction we have

u� (u�0 , …, u�u� ) = u�u� u� (u�0 , …, u�u�−1 ) + u� (u�0 , …, u�u�−2 )

= u�u� u� (u�u�−1 , …, u�0 ) + u� (u�u�−2 , …, u�0 )
= u�0 u�u� u� (u�u�−1 , …, u�1 ) + u�u� u� (u�u�−1 , …, u�2 )
+ u�0 u� (u�u�−2 , …, u�1 ) + u� (u�u�−2 , …, u�2 )
= u�0 u�u� u� (u�1 , …, u�u�−1 ) + u�0 u� (u�1 , …, u�u�−2 )
+ u�u� u� (u�2 , …, u�u�−1 ) + u� (u�2 , …, u�u�−2 )
= u�0 u� (u�1 , …, u�u� ) + u� (u�2 , …, u�u� )
= u�0 u� (u�u� , …, u�1 ) + u� (u�u� , …, u�2 )
= u� (u�u� , …, u�0 ),

so the claim also holds for u�. □

As a word of warning, the same obviously does not hold for u�.
Instead, we have

u�(u�0 , …, u�u� ) = u� (u�1 , …, u�u� ) = u� (u�u� , …, u�1 ) = u�(u�, u�u� , …, u�1 )

Best rational approximations 55

for any u�.

5.2 best rational approximations

One important application of continued fractions is in finding best

rational approximations to real numbers. If u� is a real number,
then u�u� (where u� > 0) is a best rational approximation to u� if
u�′ u�
for all fractions u�′ ≠ u� with 0 < u�′ ≤ u� we have

u� u�′
∣u� − ∣ < ∣u� − ′ ∣ .
u� u�

All such best rational approximations can be found by looking at

the convergents and semiconvergents of the continued fraction ex-
pansion of u�. A semiconvergent of a continued fraction [u�0 , u�1 , …]
is a rational expression of the form
u�u�−1 u� + u�u�−2
,
u�u�−1 u� + u�u�−2

where 0 < u� < u�u� and u� ≥ 1. Notice that the case u� = 0 corre-
sponds to the convergent u�u�u�−2 and the case u� = u�u� corresponds to
u�−2

the convergent u�u�u� . It is easy to check that the rest of the semicon-
u�
vergents lie between these two extremes and get closer to u� as u�
increases. Notice that like convergents, semiconvergents are always
irreducible fractions. (Why?)

2/1
3/2
4/3
13/10 22/17 31/24 40/31 49/38 58/45 125/97 192/149 259/201 326/253

67/52
9/7
5/4
1/1

Figure 5.1 The convergents (red) and semiconvergents (blue) of

326
253 = [1, 3, 2, 6, 1, 4], sorted by denominator size
 Best rational approximations 56

Figure 5.1 illustrates the behaviour of convergents and semiconver-

gents. In fact the best rational approximations of 326
253 can be shown
to be its convergents and the semiconvergents 32 , 54 , 40 49 192
31 , 38 , 149 and
259
201 . This is a special case of the following theorem.

Theorem 5.9 Let u� be a real number with continued fraction expansion [u�0 , u�1 , …].
All best rational approximations to u� are given by

− the convergents of [u�0 , u�1 , …],

u�u�−1 u�+u�u�−2 u�u�
− the semiconvergents u�u�−1 u�+u�u�−2 such that 2 < u� < u�u� , and

u�u�−1 u�2u� +u�u�−2

− in the case u�u� is even, the semiconvergent is also a
u�u�−1 u�2u� +u�u�−2
best rational approximation if and only if

u�u�−1 u�2u� + u�u�−2 u�u�−1

∣ − u�∣ < ∣ − u�∣ .
u�u�−1 u�2u� + u�u�−2 u�u�−1

Proof. Our road to QED is the following:

(1) We start by proving that all best rational approximations are

convergents or semiconvergents.
u�u�−1 u�+u�u�−2
(2) Next we prove that any semiconvergent u�u�−1 u�+u�u�−2 with 1 ≤
u�u�
u� < 2 is not a best rational approximation by showing that

u�u�−1 u� u� + u�u�−2
∣ − u�∣ < ∣ u�−1 − u�∣ .
u�u�−1 u�u�−1 u� + u�u�−2
u�u�−1 u�+u�u�−2
(3) Finally we prove that all semiconvergents u�u�−1 u�+u�u�−2 with u� >
u�u�
2 are best rational approximations by showing that

u�u�−1 u�u�2+1 + u�u�−2 u�u�−1

∣ − u�∣ < ∣ − u�∣ .
u�u�−1 u�u�2+1 + u�u�−2 u�u�−1
Best rational approximations 57

Because the semiconvergents get closer to u� as u� increases and

because their denominators grow monotonically, all of them
must be best rational approximations by part (1).

To prove (1), notice that any best rational approximation u�u� that is
not a convergent or semiconvergent lies between two of them. Let
u�u� u� + u�u�−1 u�u� (u� + 1) + u�u�−1
and
u�u� u� + u�u�−1 u�u� (u� + 1) + u�u�−1

be two such (semi)convergents with either u� ≥ 1 and 0 ≤ u� < u�u�+1

or u� = 0 and 1 ≤ u� < u�1 . We will now show that u�u� (u� + 1) +
u�u�−1 < u�, which gives us the needed contradiction since the second
(semi)convergent is closer to u� than u�u� is. Clearly

u� u� u� + u�u�−1 u�
∣ − u� ∣= ,
u� u�u� u� + u�u�−1 u�(u�u� u� + u�u�−1 )

where u� = |u�(u�u� u� + u�u�−1 ) − u�(u�u� u� + u�u�−1 )|. On the other hand

u� u� u� + u�u�−1 u� (u� + 1) + u�u�−1 u�u� u� + u�u�−1
∣ − u� ∣ < ∣ u� − ∣
u� u�u� u� + u�u�−1 u�u� (u� + 1) + u�u�−1 u�u� u� + u�u�−1
|u�u� u�u�−1 − u�u�−1 u�u� |
=
(u�u� (u� + 1) + u�u�−1 )(u�u� u� + u�u�−1 )
1
= .
(u�u� (u� + 1) + u�u�−1 )(u�u� u� + u�u�−1 )

Because u� ≥ 1, we have
1 1
< ,
u�(u�u� u� + u�u�−1 ) (u�u� (u� + 1) + u�u�−1 )(u�u� u� + u�u�−1 )

from which the claim follows.

u�u�
To show (2), notice that u�u� lies on the same side of u� as
u�u�−1 u�+u�u�−2 u�u�−1
u�u�−1 u�+u�u�−2 ,
while u�u�−1 lies on the opposite side, so it is enough
to show that
u�u�−1 u� + u�u�−2 u�u� u� u� 1
∣ − ∣ > ∣ u�−1 − u� ∣ = .
u�u�−1 u� + u�u�−2 u�u� u�u�−1 u�u� u�u�−1 u�u�
Best rational approximations 58

A short calculation reveals that the left hand side is equal to

u�u� − u�
,
(u�u�−1 u� + u�u�−2 )u�u�

and after simplifying we are left with the inequality

u�u� u�
u� < − u�−2 ,
2 2u�u�−1

which is clearly true since u� < u�2u� implies that u� ≤ u�2u� − 12 .

Finally we must show (3). We will assume that the continued
fraction has coefficient u�u�+1 , which implies that it is enough to show
that
u�u�−1 u� + u�u�−2 u�u�+1 u� u�
∣ − ∣ < ∣ u�−1 − u�+1 ∣ .
u�u�−1 u� + u�u�−2 u�u�+1 u�u�−1 u�u�+1

Otherwise we can compare to u� = u�u�u� directly, and the argument is

u�
similar to part (2) and is left for the reader to check. Now, a short
calculation shows that right hand side is
u�u�+1
u�u�−1 u�u�+1

and that the left hand side is

u�u� u�u�+1 − u�u�u�+1 + 1
.
(u�u�−1 u� + u�u�−2 )u�u�+1
u�u� +1
Setting u� = 2 we get after simplifying that

1 1 u�
> − u�−2 ,
2 2u�u�+1 2u�u�−1

which is clearly true. □

There is also a stronger way a rational number can be a best ap-
proximation. We say that u�u� (where u� > 0) is a best rational ap-
u�′ u�
proximation of the second kind if for all u�′ ≠ u� with 0 < u�′ ≤ u�
we have
 Best rational approximations 59

|u�u� − u�| < |u�′ u� − u�′ |.

Notice that this is indeed a stronger property than being a best

rational approximation of the first kind, since it implies that
u� u�′ u�′ u�′
∣u� − ∣ < ∣u� − ′ ∣ ≤ ∣u� − ′ ∣ .
u� u� u� u�

One can also check that it is a strictly stronger property by noticing

for example that 13 is a best rational approximation of the first kind
but not of second kind to 25 .

Theorem 5.10 Every best rational approximation of the second kind is a conver-
gent. Also the converse holds, except for the trivial case u� = u�0 + 12
for some integer u�0 .
1
Proof. The converse does not hold for u� = u�0 + 2 because u�0 and u�0 + 1
are equidistant from u� and both have denominator 1.
Let us first show that every best rational approximation of the
second kind is a convergent. We know by Theorem 5.9 that it is
either a convergent or semiconvergent, so it is enough to rule out
the possibility of it being a semiconvergent. Assume thus that the
semiconvergent u�u�u�−1 u�+u�u�−2
(where 0 < u� < u�u� ) is a best rational
u�−1 u�+u�u�−2
approximation of the second kind. We will show that

|u�u�−1 u� − u�u�−1 | ≤ |(u�u�−1 u� + u�u�−2 )u� − (u�u�−1 u� + u�u�−2 )|,

which gives us a contradiction. Notice that it is enough to show

that
u�u� u�
∣u�u�−1 − u�u�−1 ∣ ≤ ∣(u�u�−1 u� + u�u�−2 ) u� − (u�u�−1 u� + u�u�−2 )∣ ,
u�u� u�u�
u�u� u�u�−1
since u�u� is on the opposite side of u� from u�u�−1 and on the same side
u�u�−1 u�+u�u�−2 1
as u�u�−1 u�+u�u�−2 . Now the left hand side is u�u� and a short calculation
shows that the right hand side is u�u�u�−u� , which proves the claim.
u�
Let us now show the converse. That is, every convergent is
a best rational approximation of the second kind (apart from the
 Best rational approximations 60

trivial case). By the first part it is enough to check that each

convergent is a better approximation than the previous one. That
is,

|u�u� u� − u�u� | < |u�u�−1 u� − u�u�−1 |.

u�u�
If u� = u�u� , we are done. Otherwise we can instead of u� compare to
u�u�+1
u�u�+1 . Notice that

u�u�+1 1
|u�u� u� − u�u� | ≤ ∣u�u� − u�u� ∣ =
u�u�+1 u�u�+1
u�u�+1 u�
≤ = ∣u�u�−1 u�+1 − u�u�−1 ∣
u�u�+1 u�u�+1
≤ |u�u�−1 u� − u�u�−1 |.
u�u�+1
If u� = u�u�+1 it follows that u�u�+1 ≠ 1 and the inequality in the center
u�u�+1
is strict. If u� ≠ u�u�+1 then the first and last inequalites are strict by
oscillation. □

Finally we would like to present the following theorem that lets us

in some cases infer that if a given rational number is a good enough
approximation, it must actually be a convergent.
u�
Theorem 5.11 Let u� be a real number and assume that the rational number u�
satisfies
u� 1
∣u� − ∣ < 2 .
u� 2u�
u�
Then u� is a convergent of the continued fraction expansion of u�.
u�
Proof. By Theorem 5.10 it is enough to check that u� is a best rational
u� u�
approximation of the second kind. Assume that u� ≠ u� and

|u�u� − u�| ≤ |u�u� − u�| .

Then we have
 Quadratic irrationals 61

u� 1 1
∣u� − ∣ ≤ |u�u� − u�| < .
u� u� 2u�u�

On the other hand

1 u� u� 1 1 u� + u�
≤∣ − ∣< + = 2 ,
u�u� u� u� 2u�u� 2u�2 2u� u�

which implies that u� < u�. □

5.3 quadratic irrationals

Let u�, u�, u� be integers satisfying u� ≠ 0 and u�2 − 4u�u� > 0. Then the
quadratic equation u�u�2 + u�u� + u� = 0 has two real solutions given
by
√
−u� ± u�2 − 4u�u�
u� = .
2u�

If u�2 −4u�u� is not a square, then both of these solutions are irrational
and such irrational numbers are called quadratic irrationals.
Let u� be a quadratic irrational. Then u� is a root of some
polynomial u�u� 2 + u�u� + u� with integer coefficients. The other root of
this polynomial is denoted by u� and is called the conjugate of u�.
Notice that the definition of the conjugate does not depend on the
choice of the polynomial since any such polynomial is divisible by
the minimal polynomial of u�.
√
Theorem 5.12 Let u� be a square √free integer and let u�( u�) denote the numbers √
of the form u� + u� u� with u�, u� ∈ u�. Define conjugation in u�( u�)
√ √ √
by u� + u� u� = u� − u� u�. Then u�( u�) is a field consisting of the
rational numbers and those quadratic irrationals u� for which the
square free part of u�2 − 4u�u� equals u� whenever u�u�2 + u�u� + u� = 0 for
some u�, u�, u� ∈ u�. For quadratic irrationals the conjugation coincides
with the conjugation defined above, and√it satisfies u� + u� = u� + u�,
u�u� = u�u� and u�−1 = u�−1 for all u�, u� ∈ u�( u�).

Proof. Exercise. □
 Quadratic irrationals 62

A continued fraction of the form [u�0 , u�1 , …, u�ℓ , u�1 , …, u�u� ] where the
block u�1 , …, u�u� of coefficients repeats ad infinitum is called pe-
riodic. The main goal of this section is to prove the following
alternative characterization of quadratic irrationals.

Theorem 5.13 A real number u� is a quadratic irrational if and only if its continued
fraction expansion is periodic.

The full proof of this will require a couple of steps. We will first
prove a corresponding theorem for purely periodic continued frac-
tions and reduced quadratic irrationals. The proof is then finished
by a bootstrapping argument that lets us reduce the general case
to this case. A continued fraction is said to be purely periodic
if it is of the form [u�0 , u�1 , …, u�u�−1 ] and a quadratic irrational u� is
called reduced if it satisfies u� > 1 and −1 < u� < 0.

Theorem 5.14 A continued fraction is purely periodic if and only if it is the ex-
pansion of a reduced quadratic irrational.

Proof. Let us first show that a purely periodic continued fraction is a

reduced quadratic irrational.
Let u� = [u�0 , u�1 , …, u�u�−1 ] be a purely periodic continued frac-
tion with convergents u�u� /u�u� . Then in particular we have
u�u�u�−1 + u�u�−2
u� = [u�0 , u�1 , …, u�u�−1 , u�] = ,
u�u�u�−1 + u�u�−2

which shows that u� is a root of the equation

u�u�−1 u�2 + (u�u�−2 − u�u�−1 )u� − u�u�−2 = 0. (5.1)

Similarly if we reverse the coefficients and let u� = [u�u�−1 , …, u�0 ],

then

u� = [u�u�−1 , u�u�−2 , …, u�0 , u�]

u�u� (u�u�−1 , …, u�0 ) + u� (u�u�−1 , …, u�1 )
=
u�u�(u�u�−1 , …, u�0 ) + u�(u�u�−1 , …, u�1 )
u�u� (u�0 , …, u�u�−1 ) + u� (u�1 , …, u�u�−1 )
=
u�u� (u�u�−2 , …, u�0 ) + u� (u�u�−2 , …, u�1 )
Quadratic irrationals 63

u�u� (u�0 , …, u�u�−1 ) + u�(u�0 , …, u�u�−1 )

=
u�u� (u�0 , …, u�u�−2 ) + u�(u�0 , …, u�u�−2 )
u�u�u�−1 + u�u�−1
= .
u�u�u�−2 + u�u�−2

Thus u� is a root of the equation

u�u�−2 u�2 + (u�u�−2 − u�u�−1 )u� − u�u�−1 = 0.

Dividing both sides by −u�2 shows that −1/u� is a root of (5.1) and
thus −1/u� = u�. Because u� > 1 and u� > 1 (since there can be no
zeros in their continued fractions), this shows that u� is a reduced
quadratic irrational.
Assume then that u� is a reduced quadratic irrational. We want
to show that its continued fraction expansion is purely periodic.
First notice that for a given non-square integer u� > 0 there are only
finitely many different reduced quadratic irrationals that satisfy a
quadratic equation u�u� 2 + u�u� + u� = 0 with u� > 0 and u�2 − 4u�u� = u�.
To see this, we can use Vieta’s formulas to write u� = −u�u� − u�u� and
u� = u�u�u� where u� and u� are the roots of the polynomial. If u� is a
reduced √ quadratic irrational, it follows that u� = u� (u�−u�)
2 2
> u�2 , so
|u�| ≤ u�. Because u� and u� have different signs, u� = u�2 − 4u�u� ≥ u�2 ,
√ 2
so |u�| ≤ u�. Finally |u�| = |u�4|u�| −u�|
≤ u�4 . Thus the coefficients
u�, u�, u� are bounded and therefore there are only finitely many such
equations, thus also finitely many reduced quadratic irrationals.
Let u�0 ≔ u� and choose u�0 , u�0 , u�0 ∈ u� so that u�0 u�20 +u�0 u�0 +u�0 =
1
0. Set u� ≔ u�02 − 4u�0 u�0 . Define the sequence u�u� ≔ u� −⌊u� for
u�−1 u�−1 ⌋
building the continued fraction. Notice that if we choose

u�u� = ⌊u�u�−1 ⌋2 u�u�−1 + ⌊u�u�−1 ⌋u�u�−1 + u�u�−1 ,

u�u� = 2⌊u�u�−1 ⌋u�u�−1 + u�u�−1 ,
u�u� = u�u�−1 ,

then u�u� u�2u� + u�u� u�u� + u�u� = 0 and by induction

u�u�2 − 4u�u� u�u� = u�u�−1

2
− 4u�u�−1 u�u�−1 = u�.
 Quadratic irrationals 64

1
By Theorem 5.12 we have u�u� = u� −⌊u� and we see that −1 <
u�−1 u�−1 ⌋
u�u� < 0, so u�u� is reduced. The sequence u�u� must be periodic by
the observations above, and therefore also the continued fraction
expansion of u� is periodic.
It remains to show that the expansion is purely periodic. We
can do this by showing that if u�u�+1 = u�u�+1 for some u�, u�, then
u�u� = u�u� . Starting from indices where the periodicity holds this lets
us work backwards to the beginning, showing that the periodicity
holds all the time. Notice that u�u�+1 = u�u�+1 implies that u�u� −
⌊u�u� ⌋ = u�u� − ⌊u�u� ⌋. Thus u�u� ≡ u�u� (mod 1). It is therefore
enough to show that if u� is a quadratic irrational, then there is
exactly one u� such that u� + u� is a reduced quadratic irrational.
This is however clear since the conjugate of u� + u� is u� + u�, which
lies in the interval (−1, 0) for exactly one u�. □

We are now ready to prove the general case.

Proof. (Proof of Theorem 5.13) Let us first show that a periodic continued
fraction is a quadratic irrational.
Let u� = [u�0 , u�1 , …, u�ℓ , u�1 , …, u�u� ] and write u� = [u�1 , …, u�u� ].
Then by Theorem 5.14 we know that u� is a quadratic irrational. It
is easy to see using Theorem 5.12 that
u�ℓ u� + u�ℓ−1
u� =
u�ℓ u� + u�ℓ−1

is also a quadratic irrational.

Assume then that u� is a quadratic irrational. Define the se-
1
quence u�0 ≔ u�, u�u� ≔ u� −⌊u� . It is enough to show that there
u�−1 u�−1 ⌋
exists u� such that u�u� is a reduced quadratic irrational. Notice that
for u� ≥ 1 we have u�u� > 1, so we just have to show that for some
large enough u� we have −1 < u�u� < 0. Now for every u� we have
u�u�−1 u�u� + u�u�−2
u� = ,
u�u�−1 u�u� + u�u�−2

where u�u�−1 , u�u�−2 , u�u�−1 , u�u�−2 are integers. Thus by Theorem 5.12
we also have
 Quadratic irrationals 65

u�u�−1 u�u� + u�u�−2

u� = ,
u�u�−1 u�u� + u�u�−2

which we can solve for u�u� to get

u�u�−2
u� u� − u�u�−2
u�u� = − u�−2 ⎛
⎜ ⎞
⎟.
u�u�−1 u� − u�u�−1
⎝ u�u�−1 ⎠

Notice that the fraction in the parentheses has limit 1 since it tends
to u�−u�
u�−u� . By the way the continued fractions converge it is alternately
greater and less than 1 when u� is large enough. Choose some u� for
which it is less than 1. Because the factor u�u�u�−2 is always less than
u�−1
1, we have that −1 < u�u� < 0, which finishes the proof. □

Let us close this section with a short look at the structure of√the
continued fraction expansions of numbers √ of the form u� = u�.
The conjugate of u� is simply u� = − u�, so it is √ not a reduced
√
quadratic irrational. However the number u� = ⌊ u�⌋ + u� is
reduced and thus we can write the continued fraction expansion of
u� as [u�0 , u�1 , …, u�u� ]. Now we clearly have
√
u� = [u�0 − ⌊ u�⌋, u�1 , …, u�u� , u�0 , u�1 , …, u�u� , u�0 ]
√
and u�0 = 2⌊ u�⌋, so the continued fraction expansion of u� is of the
form

u� = [u�0 , u�1 , …, u�u� , 2u�0 ].

In fact a little bit more can be said.

√
Theorem 5.15 The continued fraction expansion of u� is of the form
√
u� = [u�0 , u�1 , …, u�u� , 2u�0 ],

where u�1 , …, u�u� is a palindrome.

Proof. Only the fact that u�1 , …, u�u� is a palindrome is new. Let us use the
same notation as above. In the proof of Theorem 5.14 we saw that
the continued fraction [u�u� , u�u�−1 , …, u�0 ] corresponds to the number
Quadratic irrationals 66

−1 1√ 1
u� = √
u�−⌊ u�⌋
, which is simply u�1 ≔ u�−⌊u�⌋ , so it has the continued
fraction [u�1 , …, u�u� , 2u�0 ]. Thus we see that u�1 = u�u� = u�u� , …, u�u� =
u�1 = u�1 . □
 pell’s equation

6
The diophantine equation

u�2 − u�u�2 = 1 (6.1)

where u� ≥ 2 is a non-square integer is called Pell’s equation.

It can be shown that there are infinitely many solutions to
(6.1), all of which can be obtained from the so called fundamental
solution. The fundamental solution in turn
√ can be found by looking
at the continued fraction expansion of u�. In general the theory
of Pell’s equation is largely about quadratic irrationals and their
continued fractions.
√
6.1 rings u�[ u�]

Let u�√≥ 2 be a non-square integer. Then the numbers of √ the form

u� + u� u� (u�, u� ∈ u�) form a ring√ that we denote by u�[ u�]. This
ring has a natural norm u� ∶ u�[ u�] → u� given by
√
u� (u� + u� u�) = u�2 − u�2 u�.

As was the case for the norm of the Gaussian integers defined in
Chapter √ 4, one can easily check that u� (u�u�) = u� (u�)u� (u�) √
for all
u�, u� ∈ u�[ u�]. It is also easy to check that a number u� ∈ u�[ u�] is
a unit if and only if u� (u�) = ±1.
These observations show√that solving (6.1) boils down to find-
ing the group of units in u�[ u�] and among√those units the ones
that have norm 1. We say that a unit u� + u� u� is non-trivial if
u� ≠ 0 and positive if u� > 0 and u� > 0. Notice that all non-trivial
units can be obtained from the positive units by changing the signs
of u� and u�.
√ √
Theorem 6.1 All positive units in u�[ u�] are of the form u�u� + u�u� u�, where u�u�
and u�u� are the numerator and denominator of some convergent u�u�u�
√ u�

of the continued fraction expansion of u�.

√ √
Proof. Let u� + u� u� be a positive unit in u�[ u�]. Then we have
√ √
|u� − u� u�‖u� + u� u�| = |u�2 − u�2 u�| = 1,
 √
Calculating the CF-expansion of u� 68

and in particular
√ 1 1
|u� − u� u�| = √ <
u� + u� u� 2u�

because u� > u�. The claim now follows from Theorem 5.11. □

√
6.2 calculating the cf-expansion of u�

In this section we will present√an algorithm for calculating the con-

tinued fraction expansion of u�. Besides giving us a way to even-
tually code a solver for the Pell’s equation, the algorithm will also
allow us to deduce a few extra properties about the continued frac-
tion expansion.
In general the algorithm generates the continued √ fraction ex-
u� + u�
pansion of a quadratic irrational of the form u� , where u�, u�
and u� are integers, u� > 0 is a non-square and u� divides u� 2 − u�.
The number u� will stay constant during the algorithm. Initialize
√
u� + u�
u�0 ≔ , u�0 ≔ ⌊u�0 ⌋ , u�0 ≔ u� , u�0 ≔ u�.
u�

Define the subsequent numbers by

1
u�u� ≔ ,
u�u�−1 − u�u�−1
u�u� ≔ ⌊u�u� ⌋,
u�u� ≔ u�u�−1 u�u�−1 − u�u�−1 ,
u� − u�u�2
u�u� ≔ .
u�u�−1

By definition we have u� = [u�0 , u�1 , …]. It is easy to check by using

induction that √ the following invariants hold:
u�u� + u�
− u�u� = u� ,
u�

− u�u� and u�u� are integers, and

 √
Calculating the CF-expansion of u� 69

− u�u� divides u�u�2 − u�.

√
Assume from now on that u� = u� and that we have u�0 =
0, u�0 = 1. We showed at the end of Section 5.3 that u�u� is a
reduced quadratic irrational when u� ≥ 1. In particular it follows
that u�u� −u�u� > 1, so u�u� > 0. This implies that u�u� can be calculated
using integer arithmetic by
√ √
u�u� + u� u�u� + ⌊ u�⌋
u�u� = ⌊ ⌋=⌊ ⌋.
u�u� u�u�

The following theorem gives an important connection between the

algorithm and Pell’s equation.

Theorem 6.2 For all u� ≥ 0 we have

u�u�2 − u�u�u�2 = (−1)u�+1 u�u�+1 .

Proof. We have
√ u�u� u�u�+1 + u�u�−1
u� =
u�u� u�u�+1 + u�u�−1
√
u�u�+1 + u�
u�u�+1 u�u� + u�u�−1
= √
u�u�+1 + u�
u�u�+1 u�u�
+ u�u�−1
√
u�u�+1 u�u� + u�u�u� + u�u�+1 u�u�−1
= √ .
u�u�+1 u�u� + u�u�u� + u�u�+1 u�u�−1

This implies that

√ √
u�(u�u�+1 u�u� + u�u�+1 u�u�−1 ) + u�u�u� = u�u�u� + u�u�+1 u�u� + u�u�+1 u�u�−1 .

Equating coefficients on both sides gives

u�u�+1 u�u� + u�u�+1 u�u�−1 = u�u�

u�u�+1 u�u� + u�u�+1 u�u�−1 = u�u�u�

Multiplying the first equation by u�u� and the second one by u�u� and
subtracting gives us
 √
Calculating the CF-expansion of u� 70

u�u�2 − u�u�u�2 = u�u�+1 (u�u�−1 u�u� − u�u�−1 u�u� ) = (−1)u�+1 u�u�+1 .

Notice that in particular u�u�2 − u�u�u�2 = ±1 if and only if u�u�+1 = 1.

√
On the other hand if u�u�+1 = 1, then u�u�+1 = √ u�u�+1 + u�, and
since
√ u�u�+1 √ is reduced, we must have u�u�+1 = ⌊ u�⌋ and u�u�+1 =
⌊ u�⌋ + u�. In particular u� + 1 must be at the end of the period
of the continued fraction. The converse also holds obviously.
We are ready to prove the following.
√
Theorem 6.3 The units in u�[ u�] √ are generated by a single positive fundamen-
tal unit u�u� + u�u� u� that is obtained from the u�th convergent√ of
the continued fraction expansion [u�0 , u�1 , …, u�u� , 2u�0 ] of u�.
√
Proof. We want to show that any unit is of the form ±(u�u� + u�u� u�)u� ,
where u� ∈ u�. It is enough
√ to show that all the positive units are of
the form (u�u� + u�u� u�)√u� with u� ≥ 1.
Assume√ that u� + u� u� is a positive unit that is not of the form
(u�u� + u�u� u�)u� . Then there exists u� ≥ 0 such that
√ √ √
(u�u� + u�u� u�)u� < u� + u� u� < (u�u� + u�u� u�)u�+1 .
√
Multiplying by (u�u� − u�u� u�)u� = (u� +u�1 √u�)u� it follows that
u� u�

√ √ √
1 < (u� + u� u�)(u�u� − u�u� u�)u� < u�u� + u�u� u�.
√ √ √
Let u� + u� u� ≔ (u� + u� √u�)(u�u� − u�u� u�)u� . It is clearly a unit.
Moreover
√ we have u� + u� u� > 1, so the inverse satisfies 0 < u� −
u� u� < 1. Adding these two inequalities gives us 2u� > 1, which √
implies that u� ≥ 1. Similarly u� > u�−1
√
u�
≥ 0, so u� ≥ 1. Thus u� + u� u�
√
is a positive unit, strictly smaller than u�u� + u�u� u�, which is a
contradiction. □

As a final point before we present a piece of code for finding the

fundamental unit we note the following.
 √
Calculating the CF-expansion of u� 71

√
Theorem 6.4 The first time 2u�0 = 2⌊ u�⌋√appears as a coefficient of the con-
tinued
√ fraction expansion of u� marks the end of the period of
u� = [u�0 , u�1 , …, u�u� , 2u�0 ].
√
u� + u�
√ √
u� + u�
Proof. Because is reduced, we have that u� < u�. Thus ≤
√ √ u� u�
⌊ u�⌋ + u�, which gives us
√
u� + u� √
u�0 = ⌊ ⌋ ≤ 2⌊ u�⌋
u�
√
with equality
√ if and
√ only if u� = ⌊ u�⌋ and u� = 1. We know that
u�u�+1 = ⌊ u�⌋ + u� ends the period so we are done. □
√
Algorithm 6.5 The following algorithm finds the fundamental unit in u�[ u�], where
we assume that u� is a non-square.

// Returns a fundamental unit for Z[sqrt(D)], i.e.

// the smallest positive pair (p, q) such that
// p^2 - D q^2 = +- 1
pair<int64_t,int64_t> fundamental_unit_of_Z_sqrt_D(int64_t D) {
int64_t a0=isqrt(D); // floor(sqrt(D))
int64_t a=a0;
int64_t P=0, Q=1;
int64_t pn1=1, qn1=0;
int64_t pn=a0, qn=1;
while(a != 2*a0) {
P=Q*a - P;
Q=(D - P*P)/Q;
a=(P + a0)/Q;
int64_t tmp=pn;
pn=pn*a + pn1; pn1=tmp;
tmp=qn;
qn=qn*a + qn1; qn1=tmp;
}
return make_pair(pn1, qn1);
}
 arithmetic functions

7
An arithmetic function is simply a function u�+ → u�, where u�
is the set of complex numbers. An arithmetic function u� is called
multiplicative if
− u�(1) = 1, and

− u�(u�u�) = u�(u�)u�(u�) whenever u� and u� are coprime.

The function u� is called completely multiplicative if the second
condition holds for all u� and u�.

7.1 dirichlet ring

If u� and u� are two arithmetic functions, we may define their con-

volution by

(u� ∗ u�)(u�) = ∑ u�(u�)u�(u�/u�).

u�|u�

One easily checks that convolution is associative, commutative, and

distributes over the usual pointwise addition of functions. More-
over, one can notice that the function
1, if u� = 1,
u�(u�) = {
0, otherwise

acts as a multiplicative identity for the convolution operation. This

means that the arithmetic functions form a ring, the so called
Dirichlet ring.
The units in Dirichlet ring are the functions for which u�(1) ≠ 0.
Indeed, if u� is such an function, then one can check that its inverse
can be defined recursively by
1 −1
u� −1 (1) ≔ , u� −1 (u�) ≔ ∑ u�(u�/u�)u� −1 (u�).
u�(1) u�(1)
u�|u�,u�<u�

Every multiplicative function is clearly a unit in the Dirichlet ring

because u�(1) = 1 by definition. In fact more holds.

Theorem 7.1 The multiplicative functions are a subgroup of the unit group of
the Dirichlet ring.
 Möbius inversion 73

Proof. Exercise. □

To be able to conveniently work in the Dirichlet ring, it is handy

to know some arithmetic functions and their relations. Here is a
collection of a few common ones.
function inverse definition
u� u� 1 when u� = 1, 0 otherwise
u� u� identically 1 for all u� ≥ 1
u� – the number of distinct prime factors of u�
u� u� (−1)u�(u�) if u� is squarefree, 0 otherwise
Id Id u� identity function, u� for all u� ≥ 1
Idu� Idu� u� the u�th power function u� ↦ u�u�
u�u� u� ∗ (Idu� u�) the sum of u�th powers of divisors of u�
u� u� ∗ (Id u�) the order of (u�/u�u�)∗
Table 7.1 Arithmetic functions
The reader is encouraged to try to prove at least a few of the
function–inverse function pairings.

7.2 möbius inversion

The basic version of the Möbius inversion formula is simply the

following: If u� = u� ∗ u� where u� is invertible, then u� = u� ∗ u�−1 . Or
more explicitly: If

u�(u�) = ∑ u�(u�/u�)u�(u�),
u�|u�

then

u�(u�) = ∑ u�−1 (u�)u�(u�/u�).

u�|u�

This is most often used in the case that u� = u� and u�−1 = u� when
we are interested in u� but u� is easier to calculate.
Another version of this is the following: If u� is an invertible
arithmetic function, then
 Möbius inversion 74

u�
u�(u�) = ∑ u�(u�)u�(⌊u�/u�⌋),
u�=1

implies
u�
u�(u�) = ∑ u�−1 (u�)u�(⌊u�/u�⌋).
u�=1

The proof of this is left as an exercise. Again the typical case is

u� = u�, u�−1 = u�, for which we present the following algorithm.

Algorithm 7.2 (Fast Möbius inversion) Suppose that we want to calculate u�(u�),
and that we know how to calculate
u�
u�(u�) ≔ ∑ u�(⌊u�/u�⌋),
u�=1

in u�(1) time. A simple u�(u�) algorithm to calculate u�(u�) would

then be to calculate first u�(u�) for 1 ≤ u� ≤ u� and then use the
u�
Möbius inversion formula to calculate u�(u�) = ∑u�=1 u�(u�)u�(⌊u�/u�⌋).
We can however avoid calculating the values of the Möbius
function explicitly, and ultimately do better by noting that
u�
u�(u�) = u�(u�) − ∑ u�(⌊u�/u�⌋)
u�=2
u� ⌊u�/2⌋
= u�(u�) − ∑ u�(⌊u�/u�⌋) − u�(⌊u�/2⌋) + ∑ u�(⌊u�/(2u�)⌋)
u�=3 u�=2

= u�(u�) − u�(⌊u�/2⌋) − ∑ u�(⌊u�/u�⌋).

3≤u�≤u�,u� odd
√
Because there are only about 2 u� different numbers ⌊u�/u�⌋, we can
calculate u�(⌊u�/u�⌋) recursively for all u� in u�(u�3/4 ) time.

// Calculates f(n) = (g * mu)(n)

int64_t moebius_inversion(int64_t (*g)(int64_t),
const int64_t n) {
const int64_t sqrtn = integer_sqrt(n);
// low[k] = f(k)
Möbius inversion 75

vector<int64_t> low(sqrtn+1, 0);

// high[k] = f(floor(n/(2*k + 1)))
vector<int64_t> high(sqrtn/2+1, 0);

for(int64_t m=0;m<=sqrtn;m++) {
low[m] = g(m) - g(m/2);
int64_t x = 3;
while(x <= m) {
int64_t nextx = m/(m/x) + 1;
if(nextx%2 == 0) nextx++;
low[m] -= (nextx - x)/2 * low[m/x];
x = nextx;
}
}
for(int64_t i=sqrtn/2;i>=0;i--) {
int64_t denom = 2*i + 1;
int64_t m = n/denom;
high[i] = g(m) - g(m/2);
int64_t x = 3;
while(x <= m) {
int64_t nextx = m/(m/x) + 1;
if(nextx%2 == 0) nextx++;
if(m/x <= sqrtn) {
high[i] -= (nextx - x)/2 * low[m/x];
} else {
high[i] -= (nextx - x)/2 * high[denom*x/2];
}
x=nextx;
}
}
return high[0];
}

It should
√ be noted that same kind of tricks (noting that there are
about 2 u� different numbers ⌊u�/u�⌋ etc.) work for calculating many
sums that are not strictly speaking Möbius inversions.
u�
Let us denote u�u� (u�) = ∑u�=1 u�(u�) for any arithmetic function
u�. Notice that if u� = u� ∗ u�, then we have
u�
u�u� (u�) = ∑ u�(u�)u�u� (⌊u�/u�⌋).
u�=1
 Möbius inversion 76

This can be used to calculate many summatory functions of arith-

metic functions for which we can find well-behaved u� and u�.

Example 7.3 Recall that the Euler totient function u� satisfies u� = Id ∗u�. There-
fore
u� u� ⌊ u�u� ⌋ (⌊ u�u� ⌋ + 1)
u�u� (u�) = ∑ u�(u�)u�Id (⌊u�/u�⌋) = ∑ u�(u�) ,
u�=1 u�=1
2
u�
so u�u� (u�) = ∑u�=1 u�(u�) can be calculated in u�(u�3/4 ) time by using
the fast Möbius Inversion algorithm given above with the function
u�(u�) = u�(u�+1)
2 .
 algebra

P
In this second part we will discuss additional topics in algebra.

A
R
T
II
 groups

1
One way to think about group theory is to say that it is the study
of invertible transformations, or symmetries and how they compose
to form new symmetries. For example the rotations of the plane
form a group, and combining a 30° rotation with a 45° rotation
yields a 75° rotation.
Symmetries always have an inverse transform; in the above
case a −30° (or 330°) rotation would cancel the 30° rotation. The
trivial symmetry that does not change anything is called the iden-
tity element of the group.
See [Link] Another example of a group could be given by all the possible
.[Link]/wiki transformations on the Rubik’s Cube. The cube has 6 sides, each
/Rubik's_Cube_group of which can be turned by 90°. The different combinations of these
for more information turns form a group with 227 ⋅314 ⋅53 ⋅72 ⋅11 distinct transformations,
on this specific group. which is also the number of possible states of the Rubik’s Cube.

1.1 basic definitions

The definition of an abstract group is as follows.

Definition 1.1 A set u� together with a binary operation ∘ is a group if the fol-
lowing three properties hold:
associativity − for all u�, u�, u� ∈ u�, u� ∘ (u� ∘ u�) = (u� ∘ u�) ∘ u�

identity element − there exists an element u� ∈ u� such that u� ∘ u� = u� ∘ u� = u� for all

u� ∈ u�

inverses − for all u� ∈ u� there exists an element u� −1 ∈ u� such that u� ∘u� −1 =

u�−1 ∘ u� = u�

A group (u�, ∘) is called commutative or abelian if ∘ is commu-

tative, i.e. u� ∘ ℎ = ℎ ∘ u� for all u�, ℎ ∈ u�.
We will from now on stop using the symbol ∘ explicitly and just
write u�ℎ in place of u� ∘ ℎ. If the group is commutative, we can also
write the group operation additively (u� + ℎ). In the multiplicative
notation it is often natural to use 1 to denote the identity u� and
similarly we usually use 0 when we work with the additive notation.
 Basic definitions 79

The reader is probably already familiar with many abelian

groups. For example each of u�, u�, u�, u� are groups under addi-
tion. Moreover in each of the last three all non-zero elements form
a group under multiplication. All of these examples are actually
special cases of the following: In Part I we defined commutative
rings, and each such ring hosts two important groups. First the
ring itself is a group under addition, and secondly the units of the
ring form a group under multiplication. In particular for any u� ≠ 0
the additive group of the ring u�/u�u� is an example of a finite abelian
group.

Example 1.2 The dihedral group u�u� is the group of rotational and reflectional
There are two com- symmetries of a regular polygon with u� sides. We have illustrated
peting notations for the results of applying the symmetries in u�6 to a colored hexagon
dihedral groups: The in Figure 1.1. The first row of hexagons are simply the 6 possible
alternative would de- rotations, and the second row is obtained by reflecting the hexagons
note the group u�u� on the first row about a vertical line.
by u�2u� since there
are 2u� elements.

Figure 1.1 The action of u�6 on a colored hexagon.

In general the elements of u�u� can be given as 1, u�, u�2 , …, u�u�−1 and
Here u� ≔ 2u� is u�, u�u�, u�u�2 , …, u�u�u�−1 , where u� is a rotation by u� /u� radians and u� is a
the perimeter of fixed reflection. The multiplication in u�u� is then uniquely defined
the unit circle. by the rules u�2 = 1, u�u� = 1 and u�u�u� = u�−1 .

Definition 1.3 Let u� be a group. Then u� ⊂ u� is a subgroup of u� if u� is closed

under the group operation and taking inverses.

For example in the case of u�6 the sets {1, u�, u�2 , …, u�5 }, {1, u�} and
{1, u�u�} are subgroups – a patient reader can try listing all of them.

Definition 1.4 Let u� be a subgroup of u�. Then the sets of the form
 Basic definitions 80

u�u� ≔ {u�ℎ : ℎ ∈ u�}

where u� ∈ u� are called left cosets of u�. Similarly the sets of the
form u�u� are called right cosets.

It is easy to check that the distinct left cosets u�u� are disjoint and
partition u� (same obviously holds for right cosets). In fact they
correspond to the equivalence classes of the equivalence relation
u� ∼u� u� which we can define by

u� ∼u� u� ⇔ u�u� = u�u� ⇔ u�−1 u� ∈ u�.

The set of left cosets of u� in u� is denoted by u�/u� and the set of

right cosets is denoted by u�\u�.
For example the left cosets of u� = {1, u�u�} in u�6 are
− u� = u�u�u� = {1, u�u�},

− u�u� = u�u� = {u�, u�},

− u�2 u� = u�u�5 u� = {u�2 , u�u�5 },

− u�3 u� = u�u�4 u� = {u�3 , u�u�4 },

− u�4 u� = u�u�3 u� = {u�4 , u�u�3 }, and

− u�5 u� = u�u�2 u� = {u�5 , u�u�2 }.

One can notice that all of the cosets have |u�| elements. This
is clear because u�ℎ = u�ℎ′ if and only if ℎ = ℎ′ . Together with the
fact that the cosets partition u� we have shown Lagrange’s theorem.

Theorem 1.5 Let u� be a finite group and u� ⊂ u� a subgroup. Then |u�| divides
|u�|.

In general the left and right cosets of a subgroup can differ. For
example the right cosets of {1, u�u�} in u�6 are {1, u�u�}, {u�, u�u�2 },
{u�2 , u�u�3 }, {u�3 , u�u�4 }, {u�4 , u�u�5 }, {u�5 , u�}, which are not the same as the
left cosets we listed above. This motivates the following definition.

Definition 1.6 A subgroup u� ⊂ u� for which u�u� = u�u� for every u� ∈ u� is called a
normal subgroup of u�.
 Basic definitions 81

Notice that in the case when u� is commutative, every subgroup is

normal. Normal subgroups are important because they can be used
to define quotient groups.

Definition 1.7 Let u� be a normal subgroup of u�. Then u�/u� can be made into
a group by defining u�u� ∘ u�′ u� = (u�u�′)u�. The inverse of u�u� is
thus u�−1 u� and the identity is u�. Such groups are called quotient
groups.

The reader should check that the definition makes sense, i.e. that
the multiplication is well-defined and that the obtained object ac-
tually is a group.
The subgroup u� = {1, u�2 , u�4 } is normal in u�6 with cosets
u� = {1, u�2 , u�4 }, u�u� = {u�, u�u�2 , u�u�4 }, u�u� = {u�, u�3 , u�5 } and u�u�u� =
{u�u�, u�u�3 , u�u�5 }. Thus u�6 /u� is a 4-element quotient group of u�6
whose multiplication table is listed in Table 1.1.
u� u�u� u�u� u�u�u�
u� u� u�u� u�u� u�u�u�
u�u� u�u� u� u�u�u� u�u�
u�u� u�u� u�u�u� u� u�u�
u�u�u� u�u�u� u�u� u�u� u�
Table 1.1 Multiplication
table of u�6 /{1, u�2 , u�4 }
Definition 1.8 Let u� and u�′ be two groups. A map u�∶ u� → u�′ is called a group
homomorphism if u�(u�u�′) = u�(u�)u�(u�′) for all u�, u�′ ∈ u�.

Notice that it follows that u�(1) = 1 and u�(u�−1 ) = u�(u�)−1 . One can
also easily check that the kernel of u�, i.e. the set

Ker u� ≔ {u� ∈ u� : u�(u�) = 1},

is a normal subgroup of u� and that u� is injective if and only if

Ker u� = {1}.
A bijective group homomorphism u�∶ u� → u�′ is called a group
isomorphism. In this case the inverse map u� −1 ∶ u�′ → u� is also a
group isomorphism.
 Basic definitions 82

Two groups u� and u�′ are said to be isomorphic if there exists

a group isomorphism between them. In this case the two structures
are group theoretically identical and we write u� ≅ u�′ . For example
the quotient group u�6 /{1, u�2 , u�4 } above is isomorphic with the so
called Klein four-group (denoted by u�4 ) that consists of 4 elements
1, u�, u�, u� such that u�2 = u�2 = u�2 = 1, u�u� = u�u� = u�, u�u� = u�u� = u� and
u�u� = u�u� = u�.
Given a normal subgroup u� of u� there exists a canonical sur-
jective group homomorphism u�u� ∶ u� → u�/u� given by u�u� (u�) = u�u�.
The next theorem is a fundamental factorization result for group
homomorphisms.

Theorem 1.9 Let u�∶ u� → u�′ be a group homomorphism. Then there exists a
˜ u�/Ker u� → Im u� such that u� = u�˜∘ u�
group isomorphism u�∶ Ker u� .

Proof. Since u�Ker u� is surjective, we may define u�˜ by setting

˜
u�(u�Ker u� (u�)) = u�(u�)

provided that we can show that whenever u�Ker u� (u�) = u�Ker u� (u�),
we have u�(u�) = u�(u�). But this is clear because if u� and u� belong
to the same coset, we have u� = u�u� for some u� ∈ Ker u�, so that
u�(u�) = u�(u�u�) = u�(u�)u�(u�) = u�(u�).
It remains to show that u�˜ is injective. Now if u�(u�˜
Ker u� (u�)) =
u�(u�) = 1, then u� ∈ Ker u�, so u�Ker u� (u�) = Ker u�, which means that
the kernel of u�˜ consists of the single coset Ker u�. Thus u�˜ is injective.
□

For example the group homomorphism u�∶ u�6 → u�4 given by u�(u�) =
u�, u�(u�) = u� and extending uniquely to the other elements of u�6 has
as its kernel {1, u�2 , u�4 }, and therefore u�6 /{1, u�2 , u�4 } ≅ u�4 .
A group u� is called cyclic if there exists an element u� ∈ u� such
that every element of u� can be written as u�u� for some u� ∈ u�. The
element u� is called a generator of u�. Finite cyclic groups with u�
elements are denoted by u�u� . The group u�u� is of course isomorphic
to the additive group of u�/u�u�, but we will write the operation in
u�u� multiplicatively. Thus if we want to be concrete, we can define
u�u� to consist of the u�th roots of unity in u�, that is the complex
 Basic definitions 83

numbers u� such that u� u� = 1. Thus u�u� is a cyclic subgroup of the

multiplicative group of u�. Let us lastly note that every infinite
cyclic group is clearly isomorphic to the additive group of u�.
Notice that if u� is any group and u� ∈ u�, then u� generates
a cyclic subgroup of u�. If the subgroup is finite, the size of this
subgroup is called the order of u� and written ord(u�). This gives us
the following useful result.

Theorem 1.10 Let u� be a finite group and u� ∈ u�. Then u� |u�| = 1.

Proof. Since u� is finite, ord(u�) < ∞, and by Theorem 1.5 we see that
ord(u�) divides |u�|. Moreover u�ord(u�) = 1, since u� is a generator of
a cyclic group of order ord(u�). Thus u�|u�| = (u�ord(u�) )|u�|/ord(u�) = 1.
□

We will end this section by considering direct products of groups.

Definition 1.11 If u�1 and u�2 are two groups, we can form their direct prod-
uct u� = u�1 × u�2 by considering all tuples (u�1 , u�2 ) with u�1 ∈ u�1
and u�2 ∈ u�2 and defining the group operation componentwise, i.e.
(u�1 , u�2 ) ∘ (u�1 , u�2 ) ≔ (u�1 u�1 , u�2 u�2 ).

As an example, it is easy to see that the Klein four-group is iso-

morphic with the direct product u�2 × u�2 .
We close this section with a result that is useful when we want
to try to write a group as a direct product of simpler groups.

Theorem 1.12 Let u� be a group and assume that u�1 and u�2 are two normal
subgroups of u� such that u�1 ∩u�2 = {u�}. Then u�1 u�2 is a subgroup
of u� isomorphic to u�1 × u�2 .

Proof. Notice that if u�1 ∈ u�1 and u�2 ∈ u�2 , then we have u�1 u�2 u�−1
1
u�−1
2
∈
u�1 ∩ u�2 because u�1 u�2 u�−1 1
∈ u�2 and u�2 u�−1
1
u�−1
2
∈ u�1 . Thus we see
that u�1 u�2 = u�2 u�1 .
Let us now show that u�1 u�2 is a subgroup. Clearly u� ∈
u�1 u�2 . If u�1 , u�′1 ∈ u�1 and u�2 , u�′2 ∈ u�2 , then (u�1 u�2 )(u�′1 u�2 ′) =
(u�1 u�1 ′)(u�2 u�2 ′) ∈ u�1 u�2 , so u�1 u�2 is closed under the group oper-
ation. Moreover (u�1 u�2 )(u�−1 1
u�−1
2
) = (u�1 u�−1
1
)(u�2 u�−1
2
) = u�, so u�1 u�2
is closed under taking inverses, too.
 Group actions 84

We can define a map u�∶ u�1 ×u�2 → u�1 u�2 by setting u�((u�1 , u�2 )) =
u�1 u�2 . It is a homomorphism because of the commutativity proven
in the first paragraph. It is clearly a surjection and if u�1 u�2 = u�,
then we must have u�1 = u� = u�2 , so it is also an injection and thus
an isomorphism. □

1.2 group actions

Definition 1.13 Let u� be a set and u� a group. A map ⋅∶ u� × u� → u� is a (left)

u�-action on u� if the following two axioms hold:
compatibility − u� ⋅ (u� ′ ⋅ u�) = (u�u�′) ⋅ u� for all u�, u� ′ ∈ u� and u� ∈ u�, and

identity − u� ⋅ u� = u� for all u� ∈ u�.

Given u� ∈ u�, the orbit of u� under a u�-action is u�u� ≔ {u� ⋅ u� : u� ∈

u�}. This is just all the points we can reach from u� by permuting
it with elements of u�. Orbits form a partition of u� and the set of
orbits is denoted by u�/u�.
Given u� ∈ u�, the stabilizer of u� under a u�-action is the sub-
group u�u� ⊂ u� containing all the elements that fix u�. In symbols,

u�u� ≔ {u� ∈ u� : u� ⋅ u� = u�}.

That this is indeed a subgroup follows from the compatibility axiom

of the action.
Given u� ∈ u�, the set of fixed points of u� in u� is denoted by

u� u� ≔ {u� ∈ u� : u� ⋅ u� = u�}.

If u� is a finite group and u� is a finite set, then we have the following

two useful theorems.

Theorem 1.14 (Orbit–stabilizer theorem) Let u� be a finite group and u� a finite

set. Assume that u� acts on u�. Then for all u� ∈ u� we have

|u�u�| = |u�/u�u� | = |u�|/|u�u� |.

 Conjugacy classes 85

Proof. Clearly if u� and u� are in the same coset of the stabilizer u�u� , we
must have u� ⋅ u� = u� ⋅ u�. Thus we may define a map u�∶ u�/u�u� → u�
given by u�(u�u�u� ) = u� ⋅ u�.
To prove the claim it is enough to show that u� is an injection.
Assume that u�(u�u�u� ) = u�(u�u�u� ). Then u� ⋅ u� = u� ⋅ u�. Operating by
u�−1 on both sides we get u�−1 ⋅ u� ⋅ u� = u�, so that u�−1 u� ∈ u�u� , which
implies that u�u�u� = u�u�u� . □

Theorem 1.15 (Burnside’s lemma) Let u� be a finite group and u� a finite set.
Assume that u� acts on u�. Then the number of orbits is given by
1
|u�/u�| = ∑ |u� u� |.
|u�| u�∈u�

Proof. By the orbit–stabilizer theorem we have

1 |u� | 1
|u�/u�| = ∑ = ∑ u� = ∑ |u� u� |,
u�∈u�
|u�u�| u�∈u�
|u�| |u�| u�∈u�

where the last equality follows because both sums count each pair
(u�, u�) such that u� ⋅ u� = u� exactly once. □

1.3 conjugacy classes

Let u� be a group. Two group elements u�, u�′ ∈ u� are said to be

conjugate if there exists ℎ ∈ u� such that ℎu�ℎ−1 = u�′ . It is easy
to check that this is an equivalence relation and therefore we can
partition u� into conjugacy classes where two elements belong to
the same class if and only if they are conjugate. We denote the
conjugacy class of u� ∈ u� by Cl(u�).
An orthogonal notion is that of a centralizer of an element u�
defined by

u�(u�) ≔ {u� ∈ u� : u�u� = u�u�},

that is the set of elements in u� that commute with u�, or equiva-

lently, the set of elements in u� that fix u� upon conjugation.
Conjugacy classes 86

It is helpful to notice that we can let u� act on itself by con-

jugation. That is we define u� ⋅ u� = u�u�u�−1 for all u�, u� ∈ u�. Then
conjugacy classes are the orbits and centralizers are the stabilizers
under this action.
From the orbit–stabilizer theorem we have that

|u�/u�(u�)| = | Cl(u�)|.

In particular because the conjugacy classes are disjoint, we get the

class equation
u�
|u�| = ∑ |u�/u�(u�u� )|,
u�=1

where we have picked exactly one element u�u� from each of the u�
conjugacy classes of u�.
 permutations and ordered sets

2 2.1 permutation group u�u�

Let u� be a set. A map u�∶ u� → u� that is bijective is called a

permutation of u�. In this whole chapter we are only interested
in the case where u� is finite.
Without loss of generality we may assume that u� = {1, …, u�}.
It is easy to see that the permutations on u� form a group with
composition as the group operation and the identity map Id∶ u� →
u� as the identity element. Indeed, it is clear that if u�, u� ∶ u� → u�
are two permutations, then also u� ∘ u� is a permutation. Moreover
Id ∘u� = u� = u�∘Id and u�−1 ∘u� = Id = u�∘u�−1 , so the identity element
works as expected when we take the inverse of a permutation u� to
be just its inverse map u�−1 . This group of permutations on u� is
denoted by u�u� .
The simplest way to represent a permutation u� is to just list
the images of 1, 2, …, u� under the map u�. For example if u� = 3, all
the possible permutations of u� would be (1, 2, 3), (1, 3, 2), (2, 1, 3),
(2, 3, 1), (3, 1, 2) and (3, 2, 1). From this representation it is clear
that there are u�! = 1 ⋅ 2 ⋅ … ⋅ u� permutations in total: We have u�
ways to choose the image of 1, u� − 1 ways to choose the image of
2 after the image of 1 has been chosen, u� − 2 ways to choose the
image of 3 and so on.
A cycle is a permutation u� for which there exists an element
u� ∈ u� such that all the elements moved by u� are of the form u�u� (u�)
for some u� ≥ 0. If the order of u� is u�, we say that u� is a u�-cycle.
We can use the notation

(u�u�(u�)⋯u�u�−1 (u�))

to write down u�. For example if u� = 4, then (132) would represent

a 3-cycle that maps 1 to 3, 3 to 2, 2 back to 1 and keeps 4 fixed.
It is easy to see that this notation is unique up to cyclic reordering
of the elements. The identity permutation is the only 1-cycle and
2-cycles are also called transpositions.
 Permutation group u�u� 88

It is clear that disjoint cycles commute, and one may easily no-
tice that any permutation u� can be written as a product of disjoint
cycles, uniquely up to
− the order of the cycles,

− the cyclic reorderings of cycles themselves, and

− the presence of cycles of length 1.

For example if u� = 5, the permutation (4, 3, 5, 1, 2) can be
written as (14)(235). The cycle type of u� is the multiset of lengths
of cycles appearing in the unique representation of u�, including the
cycles of length 1. For example the cycle type of the permutation
(7)(14)(235)(698) would be {1, 2, 3, 3}. This can also be written as
(1, 1, 2, 0, 0, …) where u�th coordinate gives the number of u�-cycles.
Notice that any permutation can be written as a product of
at most u� − 1 transpositions. Indeed, we can represent a cycle
(u�1 u�2 …u�u� ) as the product

(u�1 u�u� )(u�1 u�u�−1 )…(u�1 u�3 )(u�1 u�2 )

of u� − 1 transpositions.

Theorem 2.1 Assume that u�1 …u�u� = 1, where u�u� are transpositions. Then u� is
even.

Proof. Let u�, u�, u�, u� ∈ u� be distinct. Then the following equations hold:
1 (u�u�)(u�u�) = 1,

2 (u�u�)(u�u�) = (u�u�)(u�u�),

3 (u�u�)(u�u�) = (u�u�)(u�u�),

4 (u�u�)(u�u�) = (u�u�)(u�u�).
Notice that if we rewrite the product u�1 …u�u� by replacing a pair
u�u� u�u�+1 that matches the left hand side of one of (1),(2),(3) or (4)
with the corresponding right hand side, the parity of u� does not
change.
Now pick an element u� ∈ u� that appears in some of the trans-
positions in the product. By using the rules (1)–(4), we may move
 Permutation group u�u� 89

every such u� to the left-most transposition. In the end all the u�s
must disappear since the product equals the identity permutation
and we cannot be left with a single u�. If we repeat this for every el-
ement that appears in the product, we will have reduced ourselves
to the case 1 = 1 without changing the parity of the number of
transpositions in the product. □

Notice that as an easy corollary, if we write any u� ∈ u�u� as a prod-

uct of transpositions, then the number of terms in the product is
constant modulo 2. In particular we get a well-defined homomor-
phism sgn∶ u�u� → u�2 by setting sgn(u� ) = −1 for any transposition
u� and extending to products of transpositions in the natural way.
The number sgn(u�) is called the sign of the permutation u�. The
permutation u� is called even if sgn(u�) = 1 and odd if sgn(u�) = −1.
If u� = 0 or u� = 1 If u� ≥ 2, the kernel of sgn is a subgroup of index 2. This
there are no trans- subgroup contains all the even permutations and is called the al-
positions, so the ternating group of order u� and denoted u�u� .
image of sgn is From the decomposition of cycles into transpositions, it is triv-
the trivial group. ial to see that the sign of a u�-cycle is (−1)u�−1 . Thus a permutation
u� is odd if and only if there is an odd number of cycles of even
length.

Algorithm 2.2 (Sign of a permutation) The following algorithm computes the sign
of a permutation by going through the cycles and alterning the sign
based on the length of the cycle. The permutation is assumed to be
on the set {1, …, u�}, so perm[0] is ignored. The function modifies
perm in the process to keep track which cycles have been counted,
but in the end the vector should be the same as in the beginning.

int64_t sign_of_permutation(vector<int64_t> &perm) {

int64_t sgn=1;
for(int64_t i=1;i<[Link]();i++) {
if(perm[i] < 0) {
perm[i]=-perm[i];
continue;
}
int64_t j=perm[i];
while(j != i) {
sgn=-sgn;
 Ordered sets and inversions 90

perm[j]=-perm[j];
j=-perm[j];
}
}
return sgn;
}

The cycle structure of the permutation also tells the least number of
transpositions needed to express the permutation. Indeed for a per-
mutation u� = u�1 …u�u� where u�u� are cycles of lengths ℓu� respectively
and ℓ1 + … + ℓu� = u� we can write each cycle as a product of ℓu� − 1
transpositions, so in total we need (ℓ1 − 1) + … + (ℓu� − 1) = u� − u�
transpositions. We leave it as an exercise to show that this is actu-
ally optimal.

2.2 ordered sets and inversions

Definition 2.3 Let u� be a set. A binary relation ≤ is called a partial order on

u� if
reflexivity − u� ≤ u� for all u� ∈ u�,

antisymmetry − u� ≤ u� and u� ≤ u� implies u� = u� for all u�, u� ∈ u�,

transitivity − u� ≤ u� and u� ≤ u� implies u� ≤ u� for all u�, u�, u� ∈ u�.

If u� ≤ u� or u� ≤ u� for two elements u�, u� ∈ u�, we say that u� and u� are

comparable, otherwise they are incomparable. If all elements
are pairwise comparable, we say that ≤ is a total order and that
u� together with ≤ is a totally ordered set.
Assume now that u� is a finite totally ordered set and u�∶ u� → u�
is a permutation on u�. A pair (u�, u�) ∈ u� × u� is called an inversion
if u� < u� and u�(u�) > u�(u�). Using inversions we can get yet another
characterization for the sign of a permutation.

Theorem 2.4 Let u� be the number of inversions of u�. Then sgn(u�) = (−1)u� .

Proof. Without loss of generality we can assume that u� = {1, …, u�}. For
any u� ∈ u�u� let
Conjugates and commuting elements 91

u�(u�) ≔ {(u�, u�) ∈ u� × u� : u� < u�, u�(u�) > u�(u�)}

be the set of inversions of u� and similarly let

u� u� (u�) ≔ {(u�, u�) ∈ u� × u� : u� < u�, u�(u�) < u�(u�)}

be the set of pairs (u�, u�), where u� preserves the order. Consider the
map u�∶ u�u� → u�2 given by u�(u�) = (−1)|u�(u�)| . Notice that u� agrees
with sgn on transpositions, so to prove the claim, it is enough to
show that u�(u� u�) = u�(u� )u�(u�) for all u� , u� ∈ u�u� . Now

|u�(u� u�)| = |{(u�, u�) ∈ u�(u�) : (u�(u�), u�(u�)) ∈ u� u� (u� )}| +

|{(u�, u�) ∈ u� u� (u�) : (u�(u�), u�(u�)) ∈ u�(u� )}|
= |u�(u�)| − |{(u�, u�) ∈ u�(u�) : (u�(u�), u�(u�)) ∈ u�(u� )}| +
|{(u�, u�) ∈ u� u� (u�) : (u�(u�), u�(u�)) ∈ u�(u� )}|
≡ |u�(u�)| + |{(u�, u�) ∈ u�(u�) : (u�(u�), u�(u�)) ∈ u�(u� )}| +
|{(u�, u�) ∈ u� u� (u�) : (u�(u�), u�(u�)) ∈ u�(u� )}|
≡ |u�(u�)| + |u�(u� )| (mod 2),

which proves the claim. □

2.3 conjugates and commuting elements

Let u� ∈ u�u� be a permutation and let

u� = (u�1,1 u�1,2 …u�1,u�1 )…(u�u�,1 u�u�,2 …u�u�,u�u� )

be its cycle decomposition. Now if u� ∈ u�u� is any permutation, it is

straightforward to see that

u�u� u�−1 = (u�(u�1,1 )u�(u�1,2 )…u�(u�1,u�1 ))…(u�(u�u�,1 )u�(u�u�,2 )…u�(u�u�,u�u� )).

Thus we see how conjugation affects the cycle structure: We sim-

ply replace each entry u�u�,u� by u�(u�u�,u� ). From this observation the
following theorem is immeadiate.
 Conjugates and commuting elements 92

Theorem 2.5 The conjugacy classes of u�u� correspond to the different cycle types.

One way to think about conjugation in u�u� is that we are given some
new labels for u�u� , say u�1 , …, u�u� . Our permutation u� works on the
old labels 1, …, u� and u� maps the old labels u� to their corresponding
new labels u�u� . The conjugation u�u� u�−1 first converts the new labels
to the old ones, then performs u�, and finally represents the result
by using the new labels.
Let us now find the centralizer of u� ∈ u�u� . Remember that
u� ∈ u�u� commutes with u� if and only if u�u� u�−1 = u�. Let us compare
the cycle representations of the left and right hand sides. We have

(u�(u�1,1 )u�(u�1,2 )…u�(u�1,u�1 ))…(u�(u�u�,1 )u�(u�u�,2 )…u�(u�u�,u�u� )) =

(u�1,1 u�1,2 …u�1,u�1 )…(u�u�,1 u�u�,2 …u�u�,u�u� ).

Thus two elements of u�u� commute if and only if u� splits into u�

disjoint permutations u�1 , …, u�u� such that
− each u�u� fixes all elements other than u�u�,1 , …, u�u�,u�u� ,

− each u�u� maps u�u�,1 , …, u�u�,u�u� to some u�u�,1 , …, u�u�,u�u� with u�u� = u�u� ,
preserving the cyclic order.
In particular if the cycle type of u� is (u�1 , u�2 , …, u�u� ), where
u�u� is the number of u�-cycles, then there are u�1 !u�2 !…u�u� ! ways to
choose which cycles u� maps to each other and 1u�1 2u�2 …u�u�u� ways
to choose how to map each cycle while preserving the cyclic or-
der. Thus the number of elements in u�u� that commute with u� is
u�1 !u�2 !…u�u� !1u�1 2u�2 …u�u�u� .
Another way to see this would be to recall that |u�/u�(u� )| =
| Cl(u� )| and use a simple counting argument to show that the con-
jugacy class has size
u�!
.
u�1 !u�2 !…u�u� !1u�1 2u�2 …u�u�u�
 linear recurrences

3 3.1 basic theory

Let u� be a field and u� a finite dimensional u�-vector space. We let

u� ∞ denote the space of all sequences (u�u� )∞

Definition 3.1 A sequence (u�u� )∞

u�=0
u�=0
with u�u� ∈ u�.

∈ u� ∞ is a linear recursive sequence if there

exist constants u�1 , …, u�u� ∈ u� (u� ∈ u�) such that

u�u� = u�1 u�u�−1 + … + u�u� u�u�−u�

for all u� ≥ u�.

One quite slick way of getting hold of these sequences is via the
shift operator u�∶ u� ∞ → u� ∞ defined by setting u�(u�0 , u�1 , …) =
(u�1 , u�2 , …). Then u� = (u�u� )∞
u�=0
is a linear recursive sequence if
and only if there exist constants u�1 , …, u�u� such that

(u� u� − u�1 u� u�−1 − … − u�u�−1 u� − u�u� )u� = 0.

Let u� ∈ u�[u�] be a polynomial. We say that u� is a characteristic

polynomial of the sequence (u�u� )∞ u�=0
if u�(u�)u� = 0. If (u�u� )∞u�=0
is
a linear recursive sequence as above, then u�(u�) = u� − u�1 u�
u� u�−1
−
… − u�u� is a characteristic polynomial of u�, so every linear recursive
sequence has a characteristic polynomial.

Theorem 3.2 The characteristic polynomials of a linear recursive sequence (u�u� )∞

u�=0
form an ideal of u�[u�], which we will denote by u�u� .

Proof. If u� and u� are characteristic polynomials of u�, then (u� + u�)(u�)u� =

u�(u�)u� + u�(u�)u� = 0, so u� + u� is a characteristic polynomial of u�.
Similarly if u� ∈ u�[u�], then (u�u�)(u�)u� = u�(u�)u�(u�)u� = 0, so u�u� is a
characteristic polynomial of u�. □

Now because u�[u�] is a PID, there exists a unique monic polynomial

u�u� generating u�u� . We say that u�u� is the minimal polynomial of
the sequence (u�u� )∞ u�=0
. The minimal polynomial divides all other
characteristic polynomials of u�.
 Basic theory 94

Theorem 3.3 Let u� and u� be finite dimensional u�-vector spaces and assume that
u� ∶ u� → u� is a linear map. If u� ∈ u� ∞ is a linear recursive sequence,
then u� u� = (u� u�u� )∞
u�=0
∈ u� ∞ is also a linear recursive sequence.

Proof. This is clear because u�(u� u�) = u� (u�u�). □

The above theorem has sort of a converse.

Theorem 3.4 Let u� be a finite dimensional u�-vector space and u� ∈ u� ∞ . Assume

that for all linear u�∶ u� → u� the sequence u�(u�) = (u�(u�u� ))∞
u�=0
is
linear recursive. Then u� is linear recursive.

Proof. Pick a basis u�1 , …, u�u� for u� and let u�1∗ , …, u�u�∗ be the dual basis. Let
u�
u�u� = u�u�∗ (u�) and consider the intersection u� = ⋂u�=1 u�u� . We may
u�
pick a u� ∈ u� that is not zero and satisfies u�(u�)u�u�∗ (u�) = 0 for all
1 ≤ u� ≤ u�. Now clearly also u�(u�)u� = u�(u�)((u�1∗ (u�u� )u�1 )∞
u�=0
+…+
∗ ∞
(u�u� (u�u� )u�u� )u�=0 ) = 0. □

Remark 3.5 As the proof indicates, in the above theorem it is enough to check
the condition for a dual basis.

Exercise 3.6 Show that sums of linear recursive sequences are linear recursive.
(Hint: Use the above two theorems.)

We will next see our first characterization for linear recursive se-
quences. In a sense they are generated by matrices.

Theorem 3.7 Let u� be a u�-vector space and u�∶ u� → u� a linear map. Then for
any u� ∈ u� the sequence u�u� u� is linear recursive.

Proof. Let u� be the characteristic polynomial of u�. Then u�(u�)(u�u� u�) = 0

for all u� ≥ 0, which shows that u�u� u� is linear recursive. □

Remark 3.8 Notice that the characteristic polynomial of u� is also a character-

istic polynomial of the sequence u�u� u�.

Theorem 3.9 Let u� be a linear recursive sequence in some u�-vector space u�. Then
there exists a u�-vector space u�, a linear map u� → u�, u� ∈ u� and
a linear map u�∶ u� → u� such that u�u� = u�(u�u� u�) for all u� ≥ 0.
 Generating functions 95

Proof. It is enough to show this in the case where u� = u�, since in the
general case it is possible to proceed coordinate wise and embed
the obtained vector spaces and mappings in a bigger space. Now if
(u�u� )∞
u�=0
∈ u�∞ is a linear recursive sequence, it satisfies an equation
of the form u�u� = u�1 u�u�−1 +…+u�u� u�u�−u� . Pick u� = u�u� and consider
the matrix
0 1 0 0 ⋯ 0
⎛
⎜ 0 0 1 0 ⋯ 0⎞ ⎟
⎜
⎜ ⎟
⋮ ⋮ ⋮ ⋱ ⋯ ⋮⎟
u� = ⎜
⎜
⎜
⎟
⎟
⎜ 0 0 0 0 ⋱ 0⎟ ⎟
⎜
⎜0 ⎟
0 0 0 ⋯ 1⎟
⎝u�u� u�u�−1 u�u�−2 u�u�−3 ⋯ u�1 ⎠

Clearly if u�u� = (u�u� , u�u�+1 , …, u�u�+u�−1 )u� for u� ≥ 0, then u�u�u� = u�u�+1 .
We can therefore choose u� to be the projection on the first coordi-
nate. □

3.2 generating functions

In this and the following sections of the rest of this chapter we will
focus on the case where the linear recursive sequence lies in u�. In
the view of the first section this assumption is not very restrictive,
since the linear recursive sequences in higher dimensional vector
spaces are composed of one dimensional ones.
We will now look at the second characterization of linear re-
cursive sequences via generating functions.

Definition 3.10 The generating function of a sequence (u�u� )∞

u�=0
∈ u�∞ is the formal
power series
∞
u�0 + u�1 u� + u�2 u� + … = ∑ u�u� u�u� ∈ u�[[u�]].
2

u�=0

The main result of this section is the following.

 Generating functions 96

Theorem 3.11 The generating function of a sequence (u�u� )∞

u�=0
is rational if and
only if (u�u� )∞
u�=0
is linear recursive. If this is the case, then the
generating function can be written as
ℎ(u�) ℎ(u�)
u�(u�) = = ,
u�u� u�(1/u�) 1 − u�1 u� − … − u�u� u�u�

where u�(u�) = u�u� − u�1 u�u�−1 − … − u�u� is a characteristic function of

(u�u� )∞
u�=0
and

ℎ(u�) = u�0 + (u�1 − u�1 u�0 )u� + (u�2 − u�1 u�1 − u�2 u�0 )u�2 + …
+ (u�u�−1 − u�1 u�u�−2 − … − u�u�−1 u�0 )u�u�−1
u�−1 u�
= ∑ (u�u� − ∑ u�u� u�u�−u� )u�u� .
u�=0 u�=1

ℎ(u�)
Proof. Assume first that u�(u�) is a rational function with u�(0) ≠ 0. We
may without loss of generality assume that u� is of the form u�(u�) =
1 − u�1 u� − … − u�u� u�u� . Now let ℎ(u�) = ℎ0 + ℎ1 u� + … + ℎu� u�u� . We may
also assume that ℎ0 ≠ 0, because adding zeros in front of a linear
recursive sequence keeps it still linear recursive. Consider one step
of the long division:
ℎ(u�) (ℎ + u�1 ℎ0 ) + (ℎ2 + u�2 ℎ0 )u� + … + (ℎu� + u�u� ℎ0 )u�u�
= ℎ0 + u� 1 ,
u�(u�) 1 − u�1 u� − … − u�u� u�u�

where we set u�u� = 0 for u� > u�. Thus the long division maybe
modeled as a linear transformation on the space u�u�+1 which maps
(u�0 , …, u�u� ) to (u�1 + u�1 u�0 , u�2 + u�2 u�0 , …, u�u� + u�u� u�0 ). With the initial
vector (ℎ0 , …, ℎu� ) and projection on the first coordinate this gener-
ates a linear recursive sequence corresponding to the coefficients of
the power series.
Assume then that (u�u� )∞ u�=0
is a linear recursive sequence and
set u�(u�) and ℎ(u�) as in the statement of the theorem. It is enough
to check that

(1 − u�1 u� − … − u�u� u�u� )(u�0 + u�1 u� + u�2 u�2 + …) = ℎ(u�),

 Components of the recursion and closed formulas 97

which is straightforward to do. □

Rational generating functions for linear recursive sequences are use-

ful in many ways. First of all they make it easy to find recurrences
for sums of sequences. Second, by writing the generating function in
lowest terms one can find the minimal polynomial of the sequence.

3.3 components of the recursion and closed formulas

Generating functions lead us to the next stage of analyzing linear

1
recursive sequences. Consider the rational function 1−u� u�−…−u� u� .
1 u� u�
We may factor the denominator as u�1 (u�) …u�u� (u�) , where u�1 , …, u�u�
u�1 u�u�

are pairwise coprime and irreducible and u�u� ≥ 1. After this one
can do the partial fraction decomposition and obtain
1 ℎ (u�) ℎ (u�)
u� = 1 u� + … + u� u�
1 − u�1 u� − … − u�u� u� u�1 (u�) 1 u�u� (u�) u�

for some polynomials ℎu� (u�). This makes it possible to split a given
linear recursive sequence into its irreducible components. Now let
us go further and move into the splitting field of the denominator.
Then our partial fraction decomposition takes the simple form
1 ℎ1 (u�) ℎu� (u�)
u� = u� +…+ ,
1 − u�1 u� − … − u�u� u� (u� − u�1 ) 1 (u� − u�u� )u�u�

where u�1 , …, u�u� are the roots of the denominator with multiplicities
u�1 , …, u�u� . From this form it is easy to see the following:

Theorem 3.12 A sequence (u�u� )∞

u�=0
is linear recursive if and only if it can be written
as

u�u� = u�1 (u�)u�1u� + … + u�u� (u�)u�u�u� ,

where u�1 , …, u�u� are polynomials and u�1 , …, u�u� are the roots of the
minimal polynomial of u�.

An interesting consequence is that if (u�u� )∞ u�=0

and (u�u� )∞
u�=0
are linear
recursive sequences, then so is (u�u� u�u� )u�=0 .
∞
 combinatorics

P
The third part of the book will focus on counting and enumerating
things. One of the main instruments in modern combinatorics are
generating functions. We will look at them especially in the context
of so called combinatorial species. This is a theoretical framework
that makes it easy to combine simple combinatorial objects into
more complicated ones by forming equational relationships between

A
them. Information on the objects can then be distilled via their
generating functions.

R
T
III
 generating functions

1
Generating functions are simply a way of encoding sequences of
numbers that makes it easy to manipulate and analyze certain kinds
of data. They play a significant role in many areas of mathematics
such as combinatorics and number theory, and they are also a useful
tool for solving recurrences and doing various other tasks.

1.1 formal power series

We start by introducing so called formal power series.

Definition 1.1 Let u� be a fixed commutative ring. A formal power series over
u� is an expression of the form
∞
∑ u�u� u�u� = u�0 + u�1 u� + u�2 u�2 + …
u�=0

where u�u� ∈ u�.

Here the symbols u�u� carry no meaning of their own. They serve
only as a way to separate the coefficients u�u� , which for us will
usually be integers or rational numbers. This power series is also
called the (ordinary) generating function for the sequence u�u� .
Addition and multiplication are defined for formal power series
just as if they were analytic power series. Let u�(u�) and u�(u�) be
two formal power series with coefficients u�u� and u�u� respectively.
Then we define the formal power series u�(u�) ± u�(u�) by
∞
u�(u�) ± u�(u�) ≔ ∑(u�u� ± u�u� )u�u�
u�=0

and u�(u�)u�(u�) by
∞ u�
u�(u�)u�(u�) ≔ ∑ ∑(u�u� u�u�−u� )u�u� .
u�=0 u�=0

It is easy to check that the multiplication is distributive and in fact

the formal power series form a ring that will be denoted by u�[[u�]].
Analytic functions 100

∞
If u�0 is invertible in u�, then we see that u�(u�) = ∑u�=0 u�u� u�u� is
∞
invertible in u�[[u�]] and its inverse u�(u�) = ∑u�=0 u�u� u�u� is given by
the recursive formula
u�
1
u�0 = u�−1 , u�u� = − ∑ u�u� u�u�−u� (when u� ≥ 1).
0 u�0 u�=1

Yet another operation is composing series, i.e. forming the series

u�(u�(u�)). This is again defined naturally, but we can only do this if
u�0 = 0, because otherwise we would get a potentially infinite num-
ber of terms for each degree. For example the degree 0 coefficient
we would get is u�0 + u�1 u�0 + u�2 u�02 + …, which need not converge in
u�. Assuming that u�0 = 0, a short calculation shows that
∞
u�(u�(u�)) = ∑ ∑ u�u� u�u�1 …u�u�u� u�u� .
u�=0 u�≥0
u�1 ,…,u�u� ≥1
u�1 +…+u�u� =u�

Finally we may formally differentiate the formal power series, so we

define
∞
u�′(u�) ≔ ∑ u�u�u� u�u�−1 .
u�=1

1.2 analytic functions

The formal power series are all fine, but the real fun starts when
they happen to be Taylor series of some analytic functions. From
now on we will therefore simply take u� = u�.
Recall that a function u�∶ u� → u� is analytic in a neighbour-
hood of 0 if it is complex differentiable in that neighbourhood. In
other words, there exists an open disc u�(u�) ≔ {u� ∈ u�∶ |u�| < u�}
such that for all u� ∈ u�(u�) the limit
u�(u�) − u�(u�)
lim = u�′(u�)
u�→u� u� − u�
Analytic functions 101

exists. It is a basic result in complex analysis that in this case u� is

actually differentiable infinitely many times, and we may write u� in
the form of a power series
∞
u�(u�) = ∑ u�u� u�u�
u�=0

that converges in the disc u�(u�). The coefficients u�u� are uniquely
1 (u�)
determined by the formula u�u� = u�! u� (0), where u� (u�) is the u�th
derivative of u�.
Whenever our formal power series represents an analytic func-
tion, we may as well work with the function itself. The uniqueness
of the representation ensures that the operations (addition, mul-
tiplication, …) we do are in one-to-one correspondence with the
operations on the series.
Let us now look at some important examples of analytic func-
tions and their power series.
First of all there is the geometric series
∞
1
= ∑ u�u� .
1 − u� u�=0

If we differentiate this u� times, we get

∞
1 u� + u� u�
u�+1
= ∑( )u� .
(1 − u�) u�=0
u�

An even more general version is given by the Binomial series

∞
u�
(1 + u�)u� = ∑ ( )u�u� ,
u�=0
u�

where
u� u�(u� − 1)…(u� − u� + 1)
( )≔
u� u�!

is the generalized binomial coefficient.

Solving recurrence relations and sums 102

Next there is the exponential function

∞
u� u�u�
u� = ∑ .
u�=0
u�!

Using the formula u�u�u� = cos(u�) + u� sin(u�) it is easy to derive the

series for cos and sin:
∞ ∞
(−1)u� 2u� (−1)u� 2u�+1
cos(u�) = ∑ u� , sin(u�) = ∑ u� .
u�=0
(2u�)! u�=0
(2u� + 1)!

For logarithm we can find the series

∞
u�u�
log(1 − u�) = − ∑
u�=1
u�

and a few less often occuring ones around the same theme are
∞ ∞
u�2u� u�2u�+1
cosh(u�) = ∑ , sinh(u�) = ∑
u�=0
(2u�)! u�=0
(2u� + 1)!

and
∞
u�2u�+1
arctan(u�) = ∑(−1)u� .
u�=0
2u� + 1

1.3 solving recurrence relations and sums

In this section we will apply the machinery we have developed so

far to a couple of practical example problems. Let us start with the
most famous one.
The Fibonacci sequence u�u� (u� ∈ u�) is defined by the equa-
tions

u�0 = 0, u�1 = 1, u�u� = u�u�−1 + u�u�−2 .

∞
Let u� (u�) = ∑u�=0 u�u� u�u� be the associated generating function for
the terms with non-negative indices. Now the general procedure
for solving u� (u�) in the case of a linear recursion like this goes as
 Solving recurrence relations and sums 103

follows. We first multiply both sides of the recursive equation by

u�u� to get

u�u� u�u� = u�u�−1 u�u� + u�u�−2 u�u� .

Then we sum over u� to form the (formal) power series

∞ ∞
u� (u�) = ∑ u�u�−1 u� + ∑ u�u�−2 u�u�
u�

u�=0 u�=0
∞ ∞
= u�−1 + u� ∑ u�u�−1 u�u�−1 + u�−2 + u�−1 u� + u�2 ∑ u�u�−2 u�u�−2
u�=1 u�=2
2
= u�u� (u�) + u� + u� u� (u�).

Finally we solve for u� (u�) to get

u�
u� (u�) = .
1 − u� − u�2

To obtain the coefficients we can use partial fraction decomposition

to write
u� u� u� u�−1
u� (u�) = = ( + ),
1 − u� − u� 2 u� + u� −1 1 − u�u� 1 + u�−1 u�
√
where u� ≔ 1+2 5 is the Golden ratio. Now using the formula for a
geometric series we get
∞
u�u� − (−1)u� (u�−1 )u� u�
u� (u�) = ∑ u� .
u�=1
u� + u�−1

We have the iden- We have thus proved Binet’s formula

√
tity u� + u�−1 = 5. u� u� − (−u�)−u�
u�u� = √ .
5

Similar techniques work for many other kind of recurrences too,

and here is one more example. Let u�u� be defined by

u�0 = 1, u�u� = (u� − 1)u�u�−1 + u� when u� ≥ 1.

Solving recurrence relations and sums 104

Because the factor u� − 1 indicates that the sequence will grow like
u�!, we let u�(u�) be the corresponding exponential generating
function, which is a power series of the form
∞
u�u�
u�(u�) = ∑ u�u� .
u�=0
u�!

Starting similarly as with the Fibonacci series we get

∞ ∞ ∞
u�u� u�u� u�u�
∑ u�u� = ∑(u� − 1)u�u�−1 + ∑ u�
u�=1
u�! u�=1
u�! u�=1 u�!
∞ ∞ ∞
u�u�−1 u�u� u�u�−1
= u� ∑ u�u�−1 − ∑ u�u�−1 + u� ∑
u�=1
(u� − 1)! u�=1 u�! u�=1
(u� − 1)!
∞
u� u�u�
= u�u�(u�) + u�u� − ∑ u�u�−1 .
u�=1
u�!

The left hand side is u�(u�) − u�0 , so we have

∞
u� u�u�
u�u�(u�) − u�(u�) + 1 + u�u� = ∑ u�u�−1 .
u�=1
u�!

Differentiating both sides gives us

u�(u�) + u�u�′(u�) − u�′(u�) + u�u� + u�u�u� = u�(u�),

so
1 + u� u�
u�′(u�) = u� .
1 − u�

This does not have an antiderivative in terms of elementary func-

tions. However, we may still extract its coefficients by looking at
the product
u�2 u�3
u�′(u�) = (1 + u�)(1 + u� + u�2 + …)(1 + u� + + + …).
2 3!

The product of the first two terms is

Solving recurrence relations and sums 105

(1 + u� + u�2 + …) + (u� + u�2 + u�3 + …) = 1 + 2u� + 2u�2 + …

Multiplying this with the third factor gives

u�u� + 2u�u�u� + 2u�2 u�u� + 2u�3 u�u� + …,

whose u�th coefficient is

1 2 2
+ +…+ .
u�! (u� − 1)! (u� − u�)!

Thus u�′(u�) has u�th coefficient equal to

1 + 2u� + 2u�(u� − 1) + … + 2u�!
.
u�!

This means that the u�th coefficient of u�(u�) is

1 + 2(u� − 1) + 2(u� − 1)(u� − 2) + … + 2(u� − 1)!
,
u�!

which gives us

u�0 = u�1 = 1,
u�−1
u�u� = 1 + 2 ∑(u� − u�)…(u� − 1) (u� ≥ 2).
u�=1

This result is quite unsurprising if one stares at the original re-

cursion for a while. Indeed one would have probably guessed this
formula even without generating functions. Yet it should be noted
that the generating function approach turned the problem into a
fairly mechanical task.
 combinatorial species

2
Combinatorial species is an abstract – but at the same time delight-
fully concrete – framework for modeling combinatorial structures.
Computationally its strength arises from its strong connections to
generating functions, while for modeling purposes it brings together
classical combinatorial enumeration and Pólya theory.

2.1 definition

For those who know category theory, the definition of a combina-

torial species is easy.

Definition 2.1 A species is a functor u�∶ u�u�u� → u�u�u�u�u�u�, where u�u�u� is the category
of finite sets and bijections, and u�u�u�u�u�u� is the category of finite sets
and functions.

Spelled out for those that do not know category theory, this means
that a species is a rule u� that assigns to every finite set u� a finite set
u�[u� ] and to every bijection u�∶ u� → u� a function u�[u�]∶ u�[u� ] → u�[u� ].
Moreover the rule u� should satisfy the following two properties:
− u� respects composition, i.e. if u�∶ u� → u� and u� ∶ u� → u� are two
bijections, then u�[u� ∘ u�] = u�[u� ] ∘ u�[u�]

− u� maps identity to identity, i.e. u�[Idu� ] = Idu�[u�]

The idea is that u� is a set of labels and u�[u� ] is the set of all
Notice that it fol- u�-structures with labels drawn from u�. The map u�[u�] relabels the
lows from the defin- u�[u� ] structures so that they become u�[u� ] structures. For example
ition of species that if u� = u� is the species of permutations and u� = {1, 2, 3}, then
each map u�[u�] is ac-
tually a bijection. u�[u� ] = {(1)(2)(3), (12)(3), (13)(2), (23)(1), (123), (132)}.

If u�∶ u� → u� is a bijection, the map u�[u�] is defined simply by map-

ping u� ∈ u�[u� ] to u�u� u�−1 ∈ u�[u� ]. So if for example u�∶ u� → u� ≔
{u�, u�, u�} is defined by u�(1) = u�, u�(2) = u�, u�(3) = u�, then u�[u�] maps

(1)(2)(3) ↦ (u�)(u�)(u�), (12)(3) ↦ (u�u�)(u�), (13)(2) ↦ (u�u�)(u�),

(23)(1) ↦ (u�u�)(u�), (123) ↦ (u�u�u�), (132) ↦ (u�u�u�).

Associated generating functions 107

2.2 combinatorial equality, embeddings and coverings

In general there are many isomorphic ways to specify a given species.

For example, a permutation u�∶ u� → u� can be defined either as a bi-
jection or as an ordered pair (u� , u�), where u� ⊂ u� is the set of fixed
points of u� and u�∶ u� ∖ u� → u� ∖ u� is a derangement (a permutation
without fixed points).
A transformation u� between species u� and u� is a collection
of maps u�u� ∶ u�[u� ] → u�[u� ], where u� ranges over finite sets. Such a
transformation is natural if the following diagram commutes for
all finite sets u� and u� and bijections u�∶ u� → u�:

u�[u� ] u�[u� ]
u�[u�]
u�u� u�u�

u�[u� ] u�[u� ]
u�[u�]

A natural transformation u� is said to be an isomorphism between

species u� and u� if every u�u� is a bijection. In this case we say that
u� and u� are combinatorially equal and write u� = u�.
Finally u� is said to be a covering if every u�u� is a surjection
and embedding if every u�u� is an injection.

2.3 associated generating functions

The fundamental counting series associated to a species u� is its

cycle index, defined by
∞
1 u�
u�u� (u�1 , u�2 , …) ≔ ∑ ∑ | Fix u�[u�]|u�1 1 …u�u�u�u� .
u�=0
u�! u�∈u� u�

Here Fix u�[u�] is the set of those u�-structures in u�[u�] ≔ u�[{1, 2, …, u�}]
that are fixed by u�[u�] and u�u� is the number of u�-cycles in u�.
From the cycle index we can recover two basic generating func-
tions associated to the species u�. The first one is given by
 Operations on species 108

∞
u�u�
u� (u�) ≔ u�u� (u�, 0, 0, …) = ∑ |u�[u�]| .
u�=0
u�!

This is an exponential generating function that simply counts the

number of labeled u�-structures.
The second basic generating function is given by
∞
̃ 1
u�(u�) ≔ u�u� (u�, u�2 , u�3 , u�4 , …) = ∑ ( ∑ | Fix u�[u�]|) u�u� .
u�=0
u�! u�∈u�
u�

̃
Notice that u�(u�) is We claim that the coefficient
an ordinary generat-
1
1
ing function since u�! ∑ | Fix u�[u�]|
u�! u�∈u�
is part of the number u�

we are interested in.

is the number of unlabeled u�[u�]-structures, which means the number
of distinct shapes of u�[u�]-structures that remain after the labels have
been erased. In more technical terms, two structures are considered
to have the same unlabeled structure if one can be obtained from
the other one by permuting the labels. Indeed, we can think of
unlabeled structures as orbits in u�[u�] under the u�u� -action given by
u� ⋅ u� = u�[u�](u�) for all u� ∈ u�u� and u� ∈ u�[u�]. Then what we claimed
is simply Burnside’s lemma.

2.4 operations on species

One of the main aspects of the theory of combinatorial species is its

own combinatorial nature (duh). This refers to the ease at which
one may combine different species to form new ones. In this section
we will list some of these combining operations and look at how the
generating functions of the resulting new species are calculated.
The first operation is sum. If u� and u� are two species, then
we define u� + u� to be the species whose structures and morphisms
are
Here ⊔ is the − (u� + u�)[u� ] ≔ u�[u� ] ⊔ u�[u� ],
disjoint union.
Operations on species 109

u�[u�](u�), if u� ∈ u�[u� ]
− (u� + u�)[u�](u�) ≔ {
u�[u�](u�), if u� ∈ u�[u� ]
It is easy to see that the series of the new species are simply
− u�u� +u� = u�u� + u�u� ,

− (u� + u�)(u�) = u� (u�) + u�(u�), and

− (u�̃ ̃
̃ + u�(u�).
+ u�)(u�) = u�(u�)
An intuitive way to think about a sum species u� + u� is that an
(u� + u�)-structure is an u�-structure or a u�-structure.
The second operation is product. If u� and u� are two species,
then their product species u� ⋅ u� is defined by setting
− (u� ⋅ u�)[u� ] ≔ ⋃{u�[u�1 ] × u�[u�2 ] : u� = u�1 ∪ u�2 , u�1 ∩ u�2 = ∅},

− (u� ⋅ u�)[u�]((u�, u�)) ≔ (u�[u�|u�1 ](u�), u�[u�|u�2 ](u�)) where u� ∈ u�[u�1 ]

and u� ∈ u�[u�2 ].
What this means is that we look at all the possible partitions of u�
into two disjoint sets u�1 and u�2 and form all pairs of u�[u�1 ]- and
u�[u�2 ]-structures. For the generating functions we have
− u�u� ⋅u� = u�u� u�u� ,

− (u� ⋅ u�)(u�) = u� (u�)u�(u�),

− (u�̃ ̃
̃ u�(u�).
⋅ u�)(u�) = u�(u�)
Proving these is left as an exercise. Intuitively one can think that
an (u� ⋅ u�)-structure is an u�-structure and a u�-structure.
The third operation we look at is composition. If u� and u�
are two species, then their composition species u� ∘ u� is defined by
− (u� ∘ u�)[u� ] ≔ ⋃u� a partition of u� u�[u�] × ∏u� ∈u� u�[u� ],

− for u� = {u�1 , …, u�u� } and a (u� ∘ u�)-structure (u�, u�1 , …, u�u� ) ∈

u�[u�] × u�[u�1 ] × … × u�[u�u� ] we set

(u� ∘ u�)[u�](u�, u�1 , …, u�u� ) ≔

(u�[u�|u�](u�), u�[u�|u�1 ](u�1 ), …, u�[u�|u�u� ](u�u� )).

In words, an (u� ∘ u�)-structure is formed as follows: Take a partition

of the given labels and construct an u�-structure with the parts as
Basic species 110

labels. Then go through the parts and construct a u�-structure on

each of them.
With composition the corresponding rules for the generating
functions are not quite as simple as in the case of sums and prod-
ucts, except for (u� ∘ u�)(u�). For the cycle index we have

u�u� ∘u� (u�1 , u�2 , …) = u�u� (u�u� (u�1 , u�2 , u�3 , …), u�u� (u�2 , u�4 , u�6 , …),
u�u� (u�3 , u�6 , u�9 , …), u�u� (u�4 , u�8 , u�12 , …), …),

from which one easily deduces

− (u� ∘ u�)(u�) = u� (u�(u�)) and

− (u�̃ ̃
∘ u�)(u�) = u�u� (u�(u�), ̃ 2 ), u�(u�
u�(u� ̃ 3 ), …).
To maintain the light stick-to-the-point exposition, we will skip the
proofs here. Intuitively one can think of an (u� ∘ u�)-structure as an
u�-structure of u�-structures.

2.5 basic species

There are two trivial species, 0 and 1. For 0 there are no structures
whatsoever. For 1 there is exactly one structure for the empty set of
labels and no structures for any other set of labels. The generating
functions of u� = 0 and u� = 1 are u�u� = u� (u�) = u�(u�) ̃ = 0 and
̃
u�u� = u�(u�) = u�(u�) = 1.
In fact we can take the sum species 1 + … + 1 where there are
u� terms to get a species u� which has exactly u� structures on the
empty set of labels and no structures on the other label sets. For
u� = u� we have u�u� = u� (u�) = u�(u�) ̃ = u�. Thus u� can be embedded
in the space of species. One can check that u� ⋅ u� = u�u� as species,
as well as u� ⋅ u� = u� + … + u� for any species u� (the sum has u�
terms).
The next interesting species is the singleton species u� which
has a single structure for any label set that has exactly one element
and no structures for other label sets. It follows that we have
̃
u�u� (u�1 , u�2 , …) = u�1 and u� (u�) = u�(u�) = u�.
Basic species 111

Let us now introduce a species that has structures for label sets
of any size. The species u� of sets is simply defined by u�[u� ] = {u� }.
Since there is exactly one structure, we have
∞ ∞
u�u� ̃ 1
u�(u�) = ∑ = u�u� and u�(u�) = ∑ u�u� = .
u�=0
u�! u�=0
1 − u�

For the cycle index we have

∞
1 u�
u�u� = ∑ ∑ u�1 1 …u�u�u�u�
u�=0
u�! u�∈u�
u�

∞ u� u�
u�1 1 u�2 2 …u�u�u�u�
= ∑ ∑
u�=0 u�1 +2u�2 +…+u�u�u�
u� !…u�u� !1u�1 2u�2 …u�u�u�
=u� 1
u�1 u�2 u�u�
∞ ( u�11 ) ( u�22 ) … ( u�u�u� )
= ∑
u�1 +2u�2 +…+u�u�u� =0
u�1 !…u�u� !
u�2 u�3 u�4
= exp (u�1 + + + + …) ,
2 3 4

since there are u� !…u� !1u�u�!1 2u�2 …u�u�u� different permutations of cycle
1 u�
type (u�1 , …, u�u� ).
The species of permutations u� can be defined by setting u�[u� ] =
{u� ∶ u� → u� : u� is a bijection} and u�[u�](u� ) = u� ∘ u� ∘ u�−1 . We have
∞
1 u�
u�u� = ∑ ∑ u�1 !…u�u� !1u�1 …u�u�u� u�1 1 …u�u�u�u�
u�=0
u�! u�∈u� u�
∞
u�
= ∑ ∑ u�1 1 …u�u�u�u�
u�=0 u�1 +2u�2 +…+u�u�u� =u�
∞
1
= ∏ ,
u�=1
1 − u�u�

since there are u�1 !…u�u� !1u�1 …u�u�u� permutations that are fixed under
u�!
conjugation by u� and in total there are u� !…u� !1 u�1 …u�u�u� permutations
1 u�
Derived species 112

1
of given cycle type. From this we easily see that u�(u�) = 1−u� and
̃ = ∏∞
u�(u�) 1
.
u�=1 1−u�u�

2.6 derived species

The most common tool for investigating new species is to form

combinatorial equalities. For example, if u� is the species of binary
trees, then we have

u� = 1 + u� ⋅ u�2 ,

meaning that u� is either empty or a root together with two rooted

binary trees, namely the left subtree and the right subtree. To
enumerate the unlabeled binary trees we can solve the equation
̃
u�(u�) ̃ 2
= 1 + u�u�(u�)

to get
√
̃ 1− 1 − 4u�
u�(u�) = .
2u�

A short computation reveals that

∞
̃ 1 1/2
u�(u�) = (1 − ∑ ( )(−4u�)u� )
2u� u�=0
u�
∞ 1 ( 12 − 1) … ( 12 − u� + 1)
−1 2
= ∑ (−4u�)u�
2u� u�=1 u�!
∞
1 2u�
= ∑ ( )u�u� ,
u�=0
u� + 1 u�

so that the number of unlabeled binary trees on u� vertices is given

1 2u�
by the Catalan number u�+1 ( u� ). In a similar manner we can calcu-
late that
Derived species 113

√
1− 1 − 4u�
u�(u�) =
2u�

and
1 − √1 − 4u�1
u�u� = .
2u�1

There is a caveat that one should notice here: We never gave an

explicit definition of u�. Thus what we have done is simply show
that if a species u� satisfying u� = 1 + u� ⋅ u�2 exists, then its unla-
beled generating function is given as above. (In fact the quadratic
equation for u�(u�)̃ has two solutions, and we ignored the other one
on the grounds that it has a pole at 0, so its generating series has
a term u�1 in it.)
One can show that in a fairly general setting such recursive
equations actually admit a unique species as a solution, but we will
not pursue this direction here. In applications we usually know
beforehand that the species we are looking at should exist, and we
are happy to just compute its generating series by utilizing combi-
natorial equalities such as the one given above for u�.
The next species we look at is the species of cycles u�u�u�. It
can be defined by setting u�u�u�[u� ] = {u� ∶ u� → u� : u� is a cycle} and
u�u�u�[u�](u� ) = u� ∘ u� ∘ u�−1 for any bijection u�∶ u� → u�.
Notice that any permutation can be written as a set of cycles.
That is, we have

u� = u� ∘ u�u�u�.

In particular we have
∞
1 u�Cyc (u�2 , u�4 , u�6 , …)
∏ = exp (u�Cyc (u�1 , u�2 , …) +
u�=1
1 − u�u� 2
u�Cyc (u�3 , u�6 , u�9 , …)
+ + …),
3

and after taking logarithms on both sides this becomes

Derived species 114

∞ ∞ ∞
u�u�u� u�Cyc (u�u� , u�2u� , u�3u� , …)
∑∑ =∑ . (2.1)
u�=1 u�=1
u� u�=1
u�

Let’s look first at u�1 . We must have

∞
u�1u�
u�Cyc (u�1 , u�2 , …) = ∑ + u�2 (u�2 , u�3 , …)
u�=1
u�

for some series u�2 not depending on u�1 , since all the other terms
on the right hand side of (2.1) do not contain u�1 . Now assume by
induction that we have written u�Cyc (u�1 , u�2 , …) in the form
u�−1 ∞
u�u�u�
u�Cyc (u�1 , u�2 , …) = ∑ u�u� ∑ + u�u� (u�u� , u�u�+1 , …)
u�=1 u�=1
u�

for some numbers u�u� and consider u�u� . All the terms that contain
u�u� are contained in the sum
u�Cyc (u�u� , u�2u� , …, u� u� ⋅u� , …) 1
u�−1
u�u� ∞
= ∑ ( ∑ u�u� ∑ u�u� +
u�
∑
u� u� u�=1 u�=1 u�
u�|u� u�|u�

u�u� (u�u�u� , u�u�(u�+1) , …)).

u�u�/u�
In particular we see that ∑u�|u� u� = 1, giving the recursion

u�u�/u�
u�u� = 1 − ∑
u�
u�|u�,u�≠1

and completing the induction if we choose u�u�+1 to contain all the

left-over terms once we move every term with u� > 1 on the left hand
side to the right hand side. Now what is the sequence u�u� ? Notice
that if we define u�u� = u�u�u� we get the relation ∑u�|u� u�u�/u� = u�, or in
other words 1 ∗ u� = Id, where ∗ is the Dirichlet convolution. Thus
u� = Id ∗u� = u�, where u� is the Euler totient function. We have
shown that
Derived species 115

∞
u�(u�) 1
u�Cyc (u�1 , u�2 , …) = ∑ log ( ).
u�=1
u� 1 − u�u�

Looking at the unlabeled enumeration function we get the nice

identity
∞
̃ u� u�(u�) 1
Cyc(u�) = =∑ log ( ),
1 − u� u�=1 u� 1 − u�u�

and for the labeled enumeration function we have

1
Cyc(u�) = log ( ).
1 − u�
 pólya theory

3
Pólya theory is about counting objects that have symmetries. For
example we might want to count in how many ways u� people can be
seated around a round table when different rotations of the same
arrangement should be considered to be equal. In this case the
rotational symmetry is easy to take into account, and the answer
is of course (u� − 1)!.
The question becomes more difficult and interesting, however,
if we instead ask in how many ways we can form a necklace with u�
red beads, u� green beads and u� blue beads such that u� + u� + u� = u�.
Two necklaces are considered to be the same if one can be obtained
from the other by rotating the necklace.
In general the symmetry is described by some group. In the
case of necklaces this group is simply u�u� , but we could have some-
thing more complicated instead. We might for example want to
account also for reflections, in which case we would be counting
bracelets and the group in question would be u�u� . Yet another
problem would be to count in how many ways we can color the 6
faces of a cube in 3 colors when all the rotational symmetries should
be taken into account. The rotational symmetry group of the cube
turns out to be isomorphic to u�4 .

3.1 colored species

Colored species, more oftenly called multisort species, are species

where the labels also carry a color (or sort). In the literature usually
only finitely many sorts are allowed, but we will present a version
without this restriction. Therefore we will use the term colored
species. Formally the definitions are the following.

Definition 3.1 By a finite colored set u� we mean a disjoint union of a sequence

of finite sets u�u� (u� ≥ 1) where only finitely many of the sets u�u� are
∞
non-empty. In other words u� = ⋃u�=1 ({u�} × u�u� ). We will think of
u�u� as a subset of u� via the embedding u�u� ↦ {u�} × u�u� ⊂ u� and the
elements in u�u� ⊂ u� are said to have color u�.
 Colored species 117

Definition 3.2 A color-respecting bijection between two finite colored sets u�

and u� is simply a bijection u� → u� that maps u�u� bijectively onto u�u�
for all u� ≥ 1.

Definition 3.3 A colored species is a functor u�∶ u�u�u�u�u�u� → u�u�u�u�u�u�, where u�u�u�u�u�u�
is the category of finite colored sets and color-respecting bijections.

Notice that an ordinary species u� can be thought of as a colored

species for which u�[u� ] = ∅ if there are labels with other colors than
1 in u�.
Let u�1 , u�2 , … be such that u�u� = 0 for all but finitely many u�
and write

u�[u�1 , u�2 , …] ≔ u�[u� ],

∞
where u� is the colored finite set u� = ⋃u�=1 {(u�, 1), …, (u�, u�u� )}. Simi-
larly when u�(u�) ∈ u�u�u� (u� ≥ 1) we write

u�[u�(1) , u�(2) , …] ≔ u�[u�],

where u�∶ u� → u� is the color-respecting bijection defined by setting

u�((u�, u�)) = (u�, u�(u�) (u�)) for all (u�, u�) ∈ u�.
The cycle index of a colored species u� is now given by
(1) (2)
u�u� ((u�u� )u�≥1 ; (u�u� )u�≥1 ; …) =
∞ u�u�
1 (u�) (u�)
∑ ∑ | Fix u�[u�(1) , u�(2) , …]| ∏ ∏(u�u� )u�u� ,
u�1 ,u�2
u� !u�
,… 1 2
!… u�=1 u�=1
u�(u�) ∈u�u�u� ,u�≥1

where the first sum ranges over all sequences u�1 , u�2 , … such that
u�u� = 0 for all but finitely many u�.
The generating function for a labeled species u� is given by

u� (u�1 , u�2 , …) = u�u� (u�1 , 0, …; u�2 , 0, …; …)

|u� [u�1 , u�2 , …]| u�1 u�2
= ∑ u�1 u�2 ….
u�1 ,u�2 ,…
u�1 !u�2 !…

and for unlabeled species we have

 Colored species 118

̃ 1 , u�2 , …) = u�u� (u�1 , u�2 , u�3 , …; u�2 , u�2 , u�3 , …; …).

u�(u� 1 1 2 2

The definitions and rules for sums and products of colored species
parallel those of ordinary species and the induced operations on the
generating functions are the same.
For substitution we have the following: Let u� and u�1 , u�2 , …
be colored species and assume that u�u� [∅] = ∅. An u� ∘ (u�1 , u�2 , …)-
structure on a colored set u� is formed by taking a colored partition
of u�, creating an u�-structure on the partition, and then assigning
each part with color u� a u�u� -structure. The generating functions of
u� = u�(u�1 , u�2 , …) are

u�(u�1 , u�2 , …) = u� (u�1 (u�1 , u�2 , …), u�2 (u�1 , u�2 , …), …)
̃ (u� , u� , …), u�
̃ 1 , u�2 , …) = u�u� (u�
u�(u� ̃ (u�2 , u�2 , …), …;
1 1 2 1 1 2
̃ (u� , u� , …), u�
u� ̃ (u�2 , u�2 , …), …; …)
2 1 2 2 1 2
(1)
u�u� ((u�u� )u�≥1 ; …) = u�u� ((u�u�1 )1 , (u�u�1 )2 , …; (u�u�2 )1 , (u�u�2 )2 , …; …),
(1) (1) (2) (2)
where (u�u�u� )u� = u�u�u� (u�u� , u�2u� , …; u�u� , u�2u� , …; …).
It is typical to denote by u�u� (u� ≥ 1) a species that only has
a single structure for a single label of color u�. Then for example
u�1 + u�2 + u�3 would be a single label of one of the three colors 1,
2 or 3. This makes it easy to start constructing colored species out
of uncolored (or single-colored species) species by substitution.

Example 3.4 In the beginning we asked in how many ways we can form a necklace
of u� red, u� green and u� blue beads. This information can be distilled
from the unlabeled generating function of the species u�u�u�(u�1 +u�2 +
u�3 ), which is simply

u�Cyc (u�1 + u�2 + u�3 , u�21 + u�22 + u�23 , …) =

∞
u�(u�) 1
∑ log ( u� − u�u� − u�u� ) =
u�=1
u� 1 − u� 1 2 3
∞ ∞
u�(u�) (u�u� + u�u�2 + u�u�3 )u�
∑ ∑ 1 =
u�=1
u� u�=1 u�
 Quotient species 119

∞ ∞
u�(u�) 1 u�! u�u� u�u� u�u�
∑ ∑ ∑ u�1 1 u�2 2 u�3 3 .
u�=1
u� u�=1 u� u� u� !u�
=u� 1 2 3
!u� !
1 +u�2 +u�3

We need u�u�1 = u�, u�u�2 = u� and u�u�3 = u�, so u� must divide gcd(u�, u�, u�).
Thus the coefficient of u�u�1 u�u�2 u�u�3 is
u�+u�+u�
u�(u�) ( u� − 1)!
∑ ⋅ u� .
u� ( )! ( u�
)! ( u�
)!
u�| gcd(u�,u�,u�) u� u� u�

3.2 quotient species

In this section we will look at a situation where we have a group

Γ acting on some species u� in a natural way. It is then possible to
form a species u�/Γ where the structures are Γ-orbits of u�-structures.

Definition 3.5 Let Γ be a group and u� a (colored) species. We say that Γ acts
naturally on u�-structures if for every finite (colored) set u� there
exists an action Γ × u�[u� ] → u�[u� ] such that

u� ⋅ u�[u�](u�) = u�[u�](u� ⋅ u�)

for every (color-respecting) bijection u�, u� ∈ Γ and u� ∈ u�[u� ].

In other words, Γ acts naturally on u�-structures if and only if its

action commutes with relabeling of structures.
There is also a category theoretical way to look at this, which
also justifies the use of word natural in the definition. If we let
u�u�u�u� be the category of species and natural transformations be-
tween them, and regard Γ as a category with one object and group
elements as morphisms, then we can define a u�-species to be a
functor Γ → u�u�u�u�. Now, if the target object of such a functor is a
species u�, the morphisms in Γ get mapped to natural isomorphisms
u� → u�, which in turn define a natural action (in the sense of Defi-
nition 3.5) of Γ on u�-structures. We say that u� is the underlying
species of the Γ-species.
 Quotient species 120

Definition 3.6 The quotient of a Γ-species with underlying species u� is the species
u�/Γ defined by letting (u�/Γ)[u� ] ≔ u�[u� ]/Γ and (u�/Γ)[u�](Γu�) ≔
Γu�[u�](u�) for all finite (colored) sets u� and (color-respecting) bijec-
tions u�.

It follows from the naturality of the action of Γ that (u�/Γ)[u�](Γu�)

is well-defined, i.e. does not depend on the representative u� of the
orbit Γu�.
It is useful to define a special cycle index series for Γ-species
that is parametrised also on the elements of u�.

Definition 3.7 Let u� be an underlying species of a colored Γ-species. Then we

define
∞
1 (u�) (u�)
u�u�Γ (u�) = ∑ ∑ | Fix(u�⋅u�[u�(1) , u�(2) , …])| ∏(u�u� )u�u� .
u�1 ,u�2
u� !u� !… (u�)
,… 1 2 u�,u�
u� ∈u�u�u�

Notice in particular that the Γ-species series retains the information

on the cycle series of u�, since u�u�Γ (1) = u�u� .

Theorem 3.8 The cycle index of u�/Γ is given by

1
u�u�/Γ = ∑ u� Γ (u�).
|Γ| u�∈Γ u�

Proof. It is enough to show that

1
| Fix (u�/Γ)[u�]| = ∑ | Fix(u� ⋅ u�[u�])|.
|Γ| u�∈Γ

This in turn is a direct application of the following Burnside-type

lemma.

Lemma. Let Γ and u� be two groups acting on a set u� and assume

that the actions commute, i.e. u� ⋅ u� ⋅ u� = u� ⋅ u� ⋅ u� for all u� ∈ Γ,
u� ∈ u� and u� ∈ u�. Then u� acts on u�/Γ by u� ⋅ Γu� = Γ(u� ⋅ u�) and
1
| Fixu�/Γ (u�)| = ∑ | Fixu� (u� ⋅ u�)|
|Γ| u�∈Γ
 Quotient species 121

for all u� ∈ u�.

In the case at hand, both Γ and the (color-preserving) bijections

act on sets of u�-structures and the commutativity is satisfied by the
definition of Γ-species.
It remains to prove the lemma. Notice that a given orbit Γu� is
fixed by u� ∈ u� if and only if we have Γu� = u� ⋅(Γu�) = Γ(u� ⋅u�), which
happens if and only if there exists u� ∈ Γ such that u� = u� ⋅ u� ⋅ u�. If
Recall that Γu� is this is true, then there are exactly |Γu� | different such u�s. Thus
the stabilizer of u�.
1
∑ u�(u� = u� ⋅ u� ⋅ u�) = u�(Γu� ∈ Fixu�/Γ (u�)).
|Γu� | u�∈Γ

It follows that
1
| Fixu�/Γ (u�)| = ∑ u�(Γu� ∈ Fixu�/Γ (u�))
u�∈u�
|Γu�|
1 1
= ∑ ∑ u�(u� = u� ⋅ u� ⋅ u�)
u�∈u�
|Γu�| |Γu� | u�∈Γ

1
= ∑ | Fixu� (u� ⋅ u�)|.
|Γ| u�∈Γ

Here we used the orbit–stabilizer theorem to conclude that |Γu�‖Γu� | =

|Γ|. □

For a Γ-species u� we may also define the corresponding labeled and

unlabeled generating functions simply by setting
− u�u� (u�1 , u�2 , …) ≔ u�u�Γ (u�, 0, …; u�2 , 0, …; …), and

− u�u�̃ (u�1 , u�2 , …) ≔ u�u�Γ (u�1 , u�21 , …; u�2 , u�22 , …; …).

These count the u�-invariant structures of u�. Note in particular that
for the quotient species u� ≔ u�/Γ we have by Theorem 3.8 that
1
− u�(u�1 , u�2 , …) = |Γ| ∑u�∈Γ u�u� (u�1 , u�2 , …), and

̃ , u� , …) =
− u�(u� 1
∑u�∈Γ u�u�̃ (u�1 , u�2 , …).
1 2 |Γ|
 Quotient species 122

Example 3.9 We can construct the species u�u�u� of bracelets by letting the two-
element group u�2 act on u�u�u� by reflection and taking the quotient.
By Theorem 3.8 we have
1 Γ
u�Bra = (u� + u�Bra (u� )) ,
2 Cyc

where u� is the reflection. Now

∞
Γ 1 u�
u�Bra (u� ) = ∑ ∑ | Fix(u� ⋅ u�u�u�[u�])|u�1 1 …u�u�u�u� ,
u�=0
u�! u�∈u�
u�

so we have to figure out Fix(u� ⋅ u�u�u�[u�]).

Let us denote by (u�1 …u�u� ) an arbitrary cycle of length u� on
the set {1, …, u�}. Now

u� ⋅u�u�u�[u�]((u�1 …u�u� )) = u� ((u�(u�1 )…u�(u�u� ))) = (u�(u�u� )u�(u�u�−1 )…u�(u�1 )).

Thus [u�1 , …, u�u� ] is fixed by u� ⋅u�u�u�[u�] if and only if there exists ℓ ≥ 0

such that u�(u�u� ) = u�ℓ−u� for all 1 ≤ u� ≤ u� when we take indexing
modulo u�.
Case 1, u� is odd: In this case u� must consist of one 1-cycle
and u�−1
2 2-cycles for any solutions to exist. If this is true, then we
may choose a unique representation for any fixed cycle by requiring
that u�1 is the fixed element. The rest of the elements in the cycle
u�−1
u�−1
can be assigned pairwise to the 2 2-cycles in ( u�−1
2 )!2
2 ways.
u�!
There are u�−1 valid permutations.
( u�−1
2 )!2
2

Case 2a, u� is even and ℓ is odd: In this case u� must consist

u�
of 22-cycles for any solutions to exist. If this is true, then we
may choose a unique representation for any fixed cycle by choosing
u�1 = 1. There are u�2 choices for ℓ and the choice u�1 = 1 also fixes
u�−2
u�ℓ−1 = u�(1). The rest of the pairs can be chosen in ( u�−2
2 )!2
2

u�
ways and thus there are ( u�2 )!2 2 −1 fixed cycles in total. There are
u�!
u� valid permutations.
( u�
2 )!2
2
Quotient species 123

Case 2b, u� is even and ℓ is even: In this case u� must consist of

two 1 cycles and u�−2 2 2-cycles. If this is true, then we may choose a
unique representation for any fixed cycle by choosing u�1 = 1. Since
the number of fixed cycles only depends on the cycle type of u�, we
may assume that u�(1) ≠ 1. Then there are u�2 − 1 valid choices for ℓ
(we must exclude ℓ = 2). The fixed points can be chosen in 2 ways,
the pair (u�1 , u�ℓ−1 ) is fixed already and the rest of the u�−4
2 pairs can
u�−4 u�−4
be chosen in ( u�−4
2 )!2
2 ways. Thus we have 2 ( u�2 − 1) ( u�−4
2 )!2
2

u�!
fixed cycles. There are u�−2 valid permutations.
2( u�−2
2 )!2
2

These considerations let us derive the following formula for the

the cycle index of u�u�u�:
1 1 u� u�−2
1 u�−1

u�Bra = u�Cyc + ∑ (u�22 + u�12 u�2 2 ) + ∑ u�1 u�2 2

2 4 u� even 2 u� odd
1 1 (1 + u�1 )2 1
= u�Cyc + − .
2 4 1 − u�2 4
 game theory

P
A
R
T
IV
 impartial games

1
In this chapter we will look at a class of combinatorial games which
are impartial in the sense that the available moves at a given game
position does not depend on which player is moving.

1.1 nimbers

We first need a model for a game. The idea is to define an impartial

game as a set of positions (games) that correspond to the possible
moves in the starting position.

Definition 1.1 An impartial game is a finite set u� such that one of the following
holds:
− u� = ∅

− u� = {u�1 , …, u�u� } for some u� ≥ 1 and u�u� are impartial games.

A normal two player play on the game corresponds to choosing a

sequence u� ∋ u�1 ∋ u�2 … ∋ ∅ and the loser is the one who cannot
make a move because the sequence reached ∅.

Definition 1.2 To an impartial game u� we assign a nimber u� (u�) ∈ u� as follows:

0, if u� = ∅
u� (u�) = {
mex({u� (u�1 ), …, u� (u�u� )}), if u� = (u�1 , …, u�u� )

Here mex(u�) is the minimum excludant defined by

mex(u�) = min(u� ∖ u�)

for every finite u� ⊂ u�.

Nimbers will be useful when we will consider combining games in

the next two sections.

Theorem 1.3 Under perfect play the first player wins game u� if and only if
u� (u�) ≠ 0. Equivalently u� is a losing position if and only if
u� (u�) = 0.

Proof. This is easy to prove by induction. The claim clearly holds for
u� = ∅. Assume that the claim holds for all u� ∈ u�. Now if
 Sum games 126

u� (u�) = 0, then u� (u�) ≠ 0 for all u� ∈ u�, so we may only move to a

winning position which makes the current position losing. Similarly
if u� (u�) ≠ 0 then there exists u� ∈ u� such that u� (u�) = 0. Moving
to u� is therefore a winning move for position u�. □

1.2 sum games

̃ of two games u� and u�

The sum u� + u� ̃ is a game where a player
̃
may make a move in either of the games u� or u�.
̃ is defined recursively by
Definition 1.4 The sum of two games u� and u�

̃ = {u� + u�
u� + u� ̃ : u� ∈ u�} ∪ {u� + u�
̃ : u� ̃
̃ ∈ u�}.

The following theorem is a fundamental tool in analysing many

impartial games.
̃ are impartial games, then
Theorem 1.5 If u� and u�

̃ = u� (u�) ⊕ u� (u�),
u� (u� + u�) ̃

where ⊕ is the (bitwise) xor-operator.

Proof. By induction

̃ = mex({u� (u� + u�)

u� (u� + u�) ̃ : u� ∈ u�} ∪ {u� (u� + u�)
̃ : u� ̃
̃ ∈ u�})
̃ : u� ∈ u�} ∪ {u� (u�) ⊕ u� (u�)
= mex({u� (u�) ⊕ u� (u�) ̃ : u� ̃
̃ ∈ u�}).

It is therefore enough to show that for all u�, u� ∈ u� we have

u� ⊕ u� = mex({u�′ ⊕ u� : u�′ < u�} ∪ {u� ⊕ u�′ : u�′ < u�}).

We do this also by induction: We have to show that every u� < u� ⊕ u�

is either of the form u�′ ⊕ u� or of the form u� ⊕ u�′ . Looking at the
largest bit of u� ⊕ u� ⊕ u� it is easy to see that one of u� ⊕ u� < u� or
u� ⊕u� < u� holds. Thus the given form is obtained either as (u� ⊕u�)⊕u�
or u� ⊕ (u� ⊕ u�). □
index

a cyclic group 82
abelian group 78
additive group d
of a ring 26 Dirichlet ring 72
alternating group 89 dihedral group 79
analytic function 100 direct product
arithmetic function 72 of groups 83

b e
best rational approximation 55 Euclidean domain 14
Euler totient function 26
c embedding
centralizer 85 of species 107
characteristic polynomial 93 even permutation 89
chinese remainder theorem 24
class equation 86 f
colored species 117 Fibonacci sequence 102
combinatorial species 106 field 10
combinatorially equal 107 formal power series 99
commutative
group 78 g
completely multiplicative function Gaussian integers 44
72 generalized binomial coefficient
composite element 17 101
conjugacy class 85 generating function 104
conjugate elements 85 ordinary 99
continued fraction 49 greatest common divisor 14
periodic 62 group 78
convergent 50 homomorphism 81
convolution group of units 26
arithmetic functions 72
coprime 15 h
covering homomorphism
of species 107 group 81
cycle 87
cycle index 107 i
cycle type 88 ideal 11
 128

impartial game 125 p

integral domain 10 Pell’s equation 67
invertible element 10 Pythagorean triple 47
irreducible element 17 partially ordered set 90
isomorphic periodic
ring 23 continued fraction 62
isomorphism permutation 87
group 81 species 106
prime
j element 12
Jacobi symbol 31 ideal 12
number 13
k prime factorization
kernel integers 20
of a group homomorphism 81 prime-counting function 41
of a ring homomorphism 22 primitive root 29
principal ideal 11
l principal ideal domain 11
least common multiple 14 product ring 23
left coset 80
linear diophantine equation 17 q
linear recursive sequence 93 quadratic irrational 61
quadratic non-residue 30
m quadratic residue 30
maximal ideal 13 quotient group 81
minimal polynomial 93 quotient ring 12
multiplicative function 72
multiplicative group r
of a ring 26 reducible 17
right coset 80
n ring 9
nimber 125 ring homomorphism 22
normal subgroup 80 ring isomorphism 22

o s
odd permutation 89 sgn
orbit 84 of a permutation 89
 129

species 106 u
stabilizer 84 unique factorization domain 18
subgroup 79 unit 10

t w
totient function 26 witness
transposition 87 of compositeness 39