Chapter 8 Number Theory244
ajb, adividesb, ais adivisorofb, ais afactorofb, bisdivisiblebya, bis amultipleofa.Some immediate consequences of Definition 8.1.1 are that for alln
nj0; njn;and ̇ 1 jn:Also,
0 jn IMPLIES nD0:
Dividing seems simple enough, but let’s play with this definition. The Pythagore-
ans, an ancient sect of mathematical mystics, said that a number isperfectif it
equals the sum of its positive integral divisors, excluding itself. For example,
6 D 1 C 2 C 3 and 28 D 1 C 2 C 4 C 7 C 14 are perfect numbers. On the
other hand, 10 is not perfect because 1 C 2 C 5 D 8 , and 12 is not perfect because
1 C 2 C 3 C 4 C 6 D 16. Euclid characterized all theevenperfect numbers around
300 BC (Problem 8.2). But is there anoddperfect number? More than two thou-
sand years later, we still don’t know! All numbers up to about 10300 have been
ruled out, but no one has proved that there isn’t an odd perfect number waiting just
over the horizon.
So a half-page into number theory, we’ve strayed past the outer limits of human
knowledge. This is pretty typical; number theory is full of questions that are easy to
pose, but incredibly difficult to answer. We’ll mention a few more such questions
in later sections.^1
8.1.1 Facts about Divisibility
The following lemma collects some basic facts about divisibility.
Lemma 8.1.2.
- Ifajbandbjc, thenajc.
(^1) Don’t Panic—we’re going to stick to some relatively benign parts of number theory. These
super-hard unsolved problems rarely get put on problem sets.