0 Preface
This set of notes on number theory was originally written in 1995 for students
at the IMO level. It covers the basic background material that an IMO
student should be familiar with. This text is meant to be a reference, and
not a replacement but rather a supplement to a number theory textbook;
several are given at the back. Proofs are given when appropriate, or when
they illustrate some insight or important idea. The problems are culled from
various sources, many from actual contests and olympiads, and in general
are very difficult. The author welcomes any corrections or suggestions.
1 Divisibility
For integers a and b, we say that a divides b, or that a is a divisor (or
factor) of b, or that b is a multiple of a, if there exists an integer c such
that b = ca, and we denote this by a | b. Otherwise, a does not divide b, and
we denote this by a - b. A positive integer p is a prime if the only divisors of
p are 1 and p. If p
k
| a and p
k+1 - a where p is a prime, i.e. p
k
is the highest
power of p dividing a, then we denote this by p
kka.
Useful Facts
• If a, b > 0, and a | b, then a ≤ b.
• If a | b1, a | b2, . . . , a | bn, then for any integers c1, c2, . . . , cn,
a |
Xn
i=1
bici
.
Theorem 1.1. The Division Algorithm. For any positive integer a and
integer b, there exist unique integers q and r such that b = qa + r and
0 ≤ r < a, with r = 0 iff a | b.