Section 1

Integers

The subject matter of number theory is numbers, and a large part of number theory is devoted to studying the properties of the integers — that is, the numbers ... , -2, -1, 0, 1, 2, ... . Usually the integers are used merely to convey information (3 apples, $32, 17 x2 + 9), with no consideration of their properties. When counting apples, dollars, or x2'S, it is immaterial how many divisors 3 has, whether 32 is prime or not, or that 17 can be written as the sum of the squares of two integers. But the integers are so basic a part of mathematics that they have been thought worthy of study for their own sake. The same situation arises elsewhere: the number theorist is comparable to the linguist, who studies words and their properties, independent of their meaning.

There are many replies to the question, "Why study numbers?" Here are some that have been given:

Because teacher says you must.

Because you won't graduate if you don't.

Because you have to take something.

Because it gives your mind valuable training in thinking logically.

Because numbers might be interesting.

Because numbers are a fundamental part of man's mental universe and hence worth looking into.

Because some of the most powerful human minds that ever existed were concerned with numbers, and what powerful minds study is worth studying.

Because you want to know all about numbers: what makes them work, and what they do.

Because mathematics contains some beautiful things, and someone told you that number theory contained some of the most beautiful- and few of the most ugly-things.

Because it is fun.

Let us begin.

In this section, and until further notice, lower case italic letters will invariably denote integers. We will take as known and use freely the usual properties of addition, subtraction, multiplication, division, and order for the integers. We also use in this section an important property of the integers-a property that you may not be consciously aware of because it is not stated explicitly as the others. It is the least-integer principle: a nonempty set of integers that is bounded below contains a smallest element. There is the corresponding greatest-integer principle: a nonempty set of integers that is bounded above contains a largest element.

We will say that adividesb (written a|b) if and only if there is an integer d such that ad = b. For example, 216, 12160, 17117, -5150, and 81 -24. If a does not divide b, we will write a [??] b. For example, 4 [??] 2 and 3 [??] 4.

Exercise 1. Which integers divide zero?

Exercise 2. Show that if a|b and b|c, then a|c.

As a sample of the sort of properties that division has, we prove

Lemma 1. If d|a and d|b, then d|(a + b).

Proof. From the definition, we know that there are integers q and r such that

dq = a and dr = b.

Thus

a + b = d(q + r),

so from the definition again, d|(a + b).

In the same way, we can prove

Lemma 2. If d|a1, d|a2, ..., d|an then d|(c1a1 + c2a2 + ... + cnan for any integers c1, c2, ..., cn.

Proof. From the definition, there are integers q1, q2, ..., qn such that a1 = dq1, a2 = dq2 ..., an = dqn. Thus

(c1a1 + c2a2 + ... + cnan = d(c1q1 + c2q2 + ... + cnqn),

and from the definition again, d|(c1a1 + c2q2 + ... + cnan.

Exercise 3. Prove that if d|a then d|ca for any integer c.

As an application of Lemma 2, let us see if it is possible to have 100 coins, made up of c pennies, d dimes, and q quarters, be worth exactly $5.00. If it is possible, then

c + d + q = 100

and

c + 10d + 25q = 500.

Subtract the first equation from the second and we get 9d + 24q = 400. Since 319 and 3124, Lemma 2 says that 319d + 24q. That is, 31400. But that is impossible, so having exactly $5.00 is impossible with 100 pennies, dimes, and quarters. There are, however, five different ways of getting $4.99, and later we will develop a method for finding them.

Fractions are not as natural as integers, and there seems to be a human tendency to avoid them. For example, we divide a gallon into quarts, a quart into pints, and a pint into ounces so that we can always measure with integer multiples of some unit. Finding a unit common to different measures was a problem which would arise naturally in commerce—if 15 Athenian drachmas are worth 18 drachmas from Miletus, how many Athenian drachmas are equivalent to 60 Miletian drachmas? That is one reason why the Euclidean Algorithm for finding greatest common divisors was part of Euclid's Elements, written around 300 BC. The rest of this section will be devoted to the greatest common divisor and its properties, which we will use constantly later. We say that d is the greatest common divisor of a and b (written d = (a, b)) if and only if

(i) d|a and d|b, and

(ii) if c|a and c|b, then c ≤ d.

Condition (i) says that d is a common divisor of a and b, and (ii) says that it is the greatest such divisor. For example, (2, 6) = 2 and (3, 4) = 1. Note that if a and b are not both zero, then the set of common divisors of a and b is a set of integers that is bounded above by the largest of a, b, -a, and -b. Hence, from the greatest-integer principle for the integers, the set has a largest element, so the greatest common divisor of a and b exists and is unique. Note that (0, 0) is not defined, and that if (a, b) is defined, then it is positive. In fact, (a, b) ≥ 1 because 1|a and...