The Art and Craft of Problem Solving

Chapter 7

Number Theory

Number theory, the study of the integers Z, is one of the oldest branches of mathe­

matics, and is a particularly fertile source of interesting problems that are accessible at

many levels. This chapter will very briefly explore a few of the most important topics

in basic number theory, focusing especially on ideas crucial for problem solvers. The

presentation is a mix of exposition and problems for you to solve as you read. It is

self-contained and does not assume that you have studied the subject before, but if you

haven't, you may want to consult an elementary text such as [45] to learn things in

more depth or at a more leisurely pace.

Several number theory topics were discussed in earlier chapters. If you read them,

great. If not, the text below will remind you to read (or reread!) them at the appropriate

times.

We will denote the integers (positive and negative whole numbers including zero)

by Z, and the natural numbers (positive whole numbers) by N. In this chapter we

will follow the convention that any Roman letter (a through z) denotes an integer.

Furthermore , we reserve the letters p and q for primes.

7.1 Primes and Divisibility

222

If alb is an integer, we say that b divides a or b is a factor or divisor of a. We also say

this with the notation

bla,

which you read "b divides a." Equivalently, there exists an integer m such that a = bm.

The Fundamental Theorem of Arithmetic

Undoubtedly, you are familiar with the set of prime numbers. A number n is prime if

it has no divisors other than 1 and n. Otherwise, n is called composite. By convention,

1 is considered neither prime nor composite, so the set of primes begins with

2,3,5,7, 11, 13, 17,2 3,29,31, ....

It is not at all obvious whether this sequence is finite or not. In turns out that