The Theory of Algebraic Numbers

NUMBERS

CHAPTER I

DIVISIBILITY

1. Uniqueness of factorization. Elementary number theory has for its object the study of the integers 0, ±1, ±2, …. Certain of these, the prime numbers, occupy a special position; they are the numbers m which are different from 0 and ±1, and which possess no factors other than ±1 and ±m. For example 2, 3, –5 are prime, whereas 6 and 9 are not, since 6 = 2·3, 9 = 3². The importance of the primes is due to the fact that, together with 0 and ±1, all the other integers can be constructed from them. The fundamental theorem of arithmetic asserts that every integer greater than 1 can be factored in one and only one way, apart from order, as the product of positive prime numbers. Thus

are the only factorizations of 12 into positive prime factors, and these factorizations all yield precisely the same factors; the only difference among them is in the order of appearance of the factors.

We shall give a proof of the fundamental theorem of arithmetic. In the course of it the following fact will play a decisive role: every collection, finite or infinite, of non-negative integers contains a smallest one. The validity of this assumption will not be debated here; it is certainly clear intuitively, and the reader may take it to be one of the defining properties of integers. Some preliminary theorems will be established first.

THEOREM 1.1. If a and b are integers, b > 0, then there exist integers q and r such that

where 0 ≤ r < b. The integers q and r are unique.

Consider the rational number a/b and let q be the largest integer which does not exceed it. Then q ≤ a/b, but q + 1 > a/b. Define r as a – bq. Since r/b = (a/b) – q ≥ 0, and b > 0, it follows that r ≥ 0. Also from 1 > (a/b) – q = (a – bq)/b = r/b we conclude that r < b.

To show that q and r are unique suppose that q′ and r′ is any pair of integers for which

If q′ > q, then q′ ≥ q + 1, so that

this contradicts r′ ≥ 0. If q′ ≤ q, then q′ ≤ q – 1, so that

this contradicts r′ < b.

Then both possibilities q′ > q, q′ < q are ruled out. It follows that q′ = q, and hence that r′ = r. This completes the proof of Theorem 1.1.

We shall say that two integers a and b are relatively prime if they share no factors except ±1. Thus 5 and 9 are relatively prime, whereas 6 and 9 are not.

THEOREM 1.2. If a and b are relatively prime then there exist integers s and t for which as + bt = 1.

Observe that there is no assertion about the uniqueness of s and t. In fact if a = 3, b = 5 we have

To prove the theorem note first that neither a nor b can be zero unless the other is ±1. In that case the theorem is trivial. Otherwise consider the set of all numbers of the form ax + by, where x and y are integers. If we choose x = 1, y = 0, and then x = –1, y = 0, it is clear that a and –a are both in the set. Since a ≠ 0, one of a and –a is positive, so the set contains some positive numbers. Let d be the smallest positive number in the set, and write d = as + bt.

By Theorem 1.1 we can find q and r so that

Then

so that r is also in the set. Now 0 < r < d is not possible, since d is the least positive number in the set. The only alternative is r = 0. Hence b = dq. A similar argument, beginning with

shows that r′ = 0, a = dq′.

This proves that d is a factor shared by both a and b. But a and b are relatively prime, so that d = ±1; moreover d is positive, so it must be 1. Hence 1 = as + bt.

In what follows the notation "m | n means m divides n or m is a factor of n". If m is not a factor of n . The following theorem is the key to unique factorization.

THEOREM 1.3. If p is a prime number and p | ah, then p | a or p | b.

The possibility that p | a and p | b is not excluded by the theorem.

If p | a ; we shall show that in this case p must divide b.

Since p and a are relatively prime there exist integers l and m for which

This follows from the preceding theorem. Since p | ab we can write ab = pq. The last formula becomes p(lb + mq) = b, so that p | b.

COROLLARY 1.4. If a prime number p divides a product a1a2 ··· an of integers, it divides at least one of the ai.

For if p divides no ai, then by Theorem 1.3 it cannot divide any of

We are now in a position to prove the fundamental theorem stated in the opening paragraph of the chapter. Let m be a positive integer not 1. If it is not prime suppose it factors as m = m1m2, where m1 > 1, m2 > 1. If m1 and m2 are primes, stop; otherwise repeat the procedure for m1 and m2, and continue it for the new factors which appear. Eventually we must arrive at a stage where none of the factors will decompose again. Otherwise m, which is a finite integer, would be the product of an arbitrarily large number of factors all greater than 1.

Thus we arrive at a factorization

where each pi is positive and prime. Suppose

is any other factorization of m into positive primes. We must prove that the two factorizations differ at most in the order in which the primes appear. Since

it follows from Corollary 1.4 that q1 must divide one of the pi. We may suppose it to be p1, by renumbering the pi if necessary. Then q1 | p1. Since p1 and q1 are positive and prime p1 = q1. Hence, dividing out p1 = q1, we obtain

This procedure can be repeated with q2, …, until all the prime factors on one side are exhausted. At this stage all the factors on the other side must also be exhausted; otherwise we should have a product of primes on one side equal to 1 on the other. Then r = s and we are done.

If we try to apply the principle of unique factorization to negative integers, we encounter an obvious difficulty in the possible presence of minus signs in the factors. Thus

are two factorizations of –12 into primes, and these factorizations differ not merely in the order of the factors, but in the factors themselves. For in the first case the factors are 2, 2, –3; in the second case they are –2, –3, –2. This difficulty can be remedied by a slight restatement of the fundamental theorem to include negative numbers. Let 1 and – 1 be called units. The new statement is this.

THEOREM 1.5. (The Fundamental Theorem). Each integer not zero or a unit can be factored into the product of primes which are uniquely determined to within order and multiplication by units.

The slight change in the original proof which is needed here will be left to the reader.

2. A general problem. We are now in a possition to state the basic problem of algebraic number theory: if we extend the meaning of integer to include a wider class of numbers than the numbers 0, ±1, ±2, … is there still a valid analogue of Theorem 1.5? The nature of the question can best be made plain by examples.

For this purpose we select first the Gaussian integers. By such an integer we shall mean a number of the form a + bi, where a and b . To avoid confusion later we shall refer to the ordinary integers as the rational integers. Let G denote the set of all Gaussian integers, and J the set of all rational integers. We shall sometimes write α ∈ A if α is a member of a set A. Note that in each set the sum, difference and product of integers are integers.

If α and β are numbers in G we say that α divides β, written α | β, if there is a number γ in G such that β = αγ. An element of G is a unit if it divides 1, and hence also every element of G. A number π is prime if it is not a unit and if in every factorization π = αβ one of α or β is a unit. With this terminology Theorem 1.5 becomes meaningful for the integers of G.

But is it true? It is, as we shall show presently. This fact may strike the reader as only what is to be expected. That such an impression is erroneous we demonstrate by exhibiting another simple class of integers for which Theorem 1.5 is meaningful, but false.

, where a and b are rational integers. Clearly the sum, difference and product of such integers are of the same form. We shall denote the totality of them by H. Define unit and prime just as we did for the Gaussian integers by simply reading H for G wherever the latter occurs. As we shall prove a little later, ±1 are the only units in Hwill turn out to be prime in H. But observe that

so that the factorization of 21 into prime factors is not unique to within order and multiplication by units.

It is therefore reasonable to ask for which classes of integers the fundamental theorem holds, and for which it does not. In particular how does one explain the discrepancy in behavior between the sets J and G on the one hand and H on the other? The answer to these questions must be postponed until later. For the present we content ourselves with demonstrating the assertions just made concerning the sets G and H.

3. The Gaussian integers. If α = a + bi is an element of G its norm N(α), or simply Nα= | α |² = a² + b². (

α

is the complex-conjugate of α). The following list contains the fundamental properties of the norm.

The proof of (i) is obvious since b = 0. To prove (ii) observe that if α = a + bi, β = c + di, then

As for (iii), suppose first that α is a unit. Then α | 1, so αβ = 1 for some β. By (ii) NαNβ = N1 = 1, and Nα | 1. Since Nα must be a non-negative integer, Nα = 1. Conversely if Nα = 1, a² + b² = 1, so that a = 0 or b = 0. Then α = 1, –1, i or –i, and these are obviously units. This argument also establishes most of (iv); the rest we leave to the reader.

Finally to prove (v), suppose Nα is prime and α = βγ. Then Nα = NβNγ is prime in J. So one of Nβ or Nγ is equal to 1, and by (iii) either β or γ is a unit.

The converse of (v) is false. To see this it is enough to show that 3 is prime in G, for N3 = 3² = 9. Suppose 3 = αβ. Then 9