6 Integers, Divisors, and Primes
In this chapter we discuss properties of integers. This area of mathematics
is callednumber theory, and it is a truly venerable field: Its roots go back
about 2500 years, to the very beginning of Greek mathematics. One might
think that after 2500 years of research, one would know essentially every-
thing about the subject. But we shall see that this is not the case: There
are very simple, natural questions that we cannot answer; and there are
other simple, natural questions to which an answer has been found only in
the last few years!
6.1 Divisibility of Integers
We start with some very basic notions concerning integers. Letaandbbe
two integers. We say thatadividesb,orais a divisor ofb,orbis a multiple
ofa(these phrases mean the same thing), if there exists an integermsuch
thatb=am. In notation:a|b.Ifais not a divisor ofb, then we writeab.
Ifa = 0, thena|bmeans that the ratiob/ais an integer.
Ifabanda>0, then we can still dividebbyawith remainder. The
remainderrof the divisionb÷ais an integer that satisfies 0≤r<a.If
the quotient of the division with remainder isq, then we have
b=aq+r.This is a very useful way of thinking about a division with remainder.
You have probably seen these notions before; the following exercises
should help you check whether you remember enough.