Number Theory in Z

In this section we will study some of the arithmetic properties of integers. The properties which we establish will motivate many of the abstract notions which we will consider later.

We will say that a|b (read "a divides b") if b = k · a for some k. If a|b, we will say that b is a multiple of a and that a is a divisor of b. The following properties of divisibility are more or less obvious:

(1)

a|b,b|c a|c,

a|b, a|c a|(bx + cy)   for all integers x,y

a|b, b|a b = a or b = -a.

We will leave proofs of (1) and (2) to the reader. To prove (3), let us prove two auxiliary assertions

a|b, a|c a|(b + c),

a|b a|bx    for all x.

Assertions (3a) and (3b) imply (3) since if a|b, a|c, then a|bx, a|cy by (3b), which implies that a|(bx + cy) by (3a). To prove (3a), notice that if a|b, a|c, there exists k and m such that b = k · a, c = m · a. Therefore, b + c = (k + m) · a, so that a|(b + c). The proof of (3b) is similar.

Let us now prove (4). If a|b then ±a|±b, so that is suffices to consider the case where a > 0, b > 0. In this case, a|b implies that b = k · a with k > 0. Therefore, by the order properties of Z, b > a. But, since b|a, we deduce similarly that a > b. Therefore, a = b.

We say that c is a greatest common divisor of a and b, provided that.

1. c > 0.

2. c|a, c|b.

3. Whenever d is an integer such that d|a, d|b, then d|c.

Property (2) asserts that c is a divisor of both a and b, that is, a common divisor of a and b. Property (3) asserts that among all common divisors of a and b, c is the "greatest" in the sense that every common divisor of a and b is also a divisor of c. We denote c by (a,b).

Exercise 1: Suppose that a and b have a greatest common divisor c. Show that c is the largest denominator of a and b.

It is not obvious that two integers have a greatest common divisor. Nor is it obvious that two integers have only one greatest common divisor. Let us clarify the second point: If a greatest common divisor exists, it must be unique. For suppose that c₁ and c₂ both satisfy (1)-(3). Then by (2), c₂|a, c₂|b. Thus by (3) for c₁, we see that c₂|c₁. Similarly, c₁|c₂. Therefore by (4) c₁ = ±c₂. However, since both c₁ and c₂ are positive, c₁ = c₂. Let us know prove that a greatest common divisor exists.

Proposition 1: Suppose that a and b are not zero. Then a and b have a greatest common divisor.

Proof: We noted that the proposition is not at all obvious. In order to prove it, a tremendously ingenious idea is required. Let

S = {ax + by | x,y Z}

We will prove that S contains the common divisor of a and b. If f = ax + by S, then f = a(-x)+b(-y) S. Moreover, since a S and b S we see that S contains elements distinct from zero, and therefore S contains positive elements. Let S₊ = {z S | z > 0}. By the well ordering of N, S₊ contains a smallest element c. Then c > 0 and we assert that c is a greatest common divisor of a and b. Since c S, there exists x and y such that

(5)

Therefore, if d|a, d|b, we see that d|c by (3). Thus, properties (1) and (3) hold. In order to prove (2), let us prove the following.

Claim: Each element of S is a multiple of c.

It clearly suffices to show that every positive element of S is a multiple of c. Therefore, let f = ax'+ by' S₊. By the division algorithm, there exist q and r such that 0 < r < c and such that

which implies that r S. If r > 0, then r S₊, which is a contradiction to the assumption that c is the smallest element in S₊. Therefore r = 0 and f = qc; that is f is a multiple of c. This establishes the claim.

In order to complete the proof of the proposition, we note that since a S, b S, we have c|a, c|b by the claim.

Corollary 2: Let a and b be integers, at least one of which is nonzero, and let c be the greatest common divisor of a and b. Then there exist integers x and y such that.

We say that two nonzero numbers are relatively prime if their greatest common divisor is 1. By the preceding corollary, we immediately derive

Corollary 3: If a and b are relatively prime, then there exist integers x and y such that

Henceforth, we will denote by (a,b) the greatest common divisor of a and b.

Definition 4: A prime number is a natural number p > 1 whose only divisors are ±1 and ±p.

For example, 2 and 3 are primes, but 6 = 2 · 3 is not a prime. The primes are the basic building blocks from which all other integers can be built. We have

Let n be an integer greater than 1. Then n can be expressed as a product of primes. Lemma 5: Let n be an integer greater than 1. Then n can be expressed as a product of primes.

Proof: Let us reason by induction on n. The assertion is clearly true for n = 2. Thus, assume that the assertion is true for all integers < n, and let us prove from this assumption that n can be expressed as a product of primes. If n is prime, then n is clearly a product of primes. Thus, assume that n is not prime. Then n can be written in the form n = n'n'', 1 < n', n'' < n. By the induction assumption, both n' and n'' can be written as products of primes, so n can be written as a product of primes and the induction is complete.

As a simple application of the lemma, we can prove

Theorem 6(Euclid): There exist infinitely many primes.

Proof: Let us reason by contradiction. Suppose that {p₁, p₂,...,p_N} were a complete list of the primes. The integer

is greater than 1, and is therefore divisible by some prime, by Lemma 5. But M is not divisible by any one of p₁,...,p_N. Thus there must exist a prime different from p₁,...,p_N, and a contradiction is reached.

There is a simple way of constructing a table of the primes, first discovered by the Greek mathematician Eratosthenes. Write down all of the natural numbers, beginning with 1:

1,2,3,4,5,6,7,8,9,...

Cross out all of the numbers divisible by 2, except for the first one, 2, to get

1,2,3,4,5,6,7,8,9,10,...

Next, cross out all of the multiples of 3, except for the first one to get

1,2,3,4,5,6,7,8,9,10,11,12...

Four and its multiples have already been crossed out, so next cross out the multiples of 5, except for the first, and continue in this way. The natural numbers remaining will be precisely the primes and 1. For am additional example click on sieve example.

Lemma 5 asserts that every every nonzero integer can be expressed as a product of primes. Our last major result in this section will be to show that this expression is unique, that is, unique except for the arrangements of the factors. This fact is known as the fundamental theorem of arithmetic.

The notion of a prime was already known to the Greeks. In fact the fundamental theorem of arithmetic had its origins in Greek mathematics. The proof that there are infinitely many primes was known to Euclid, who included a proof in his Elements. If one looks at a table of primes, one of the interesting features which one notices is the rather irregular way in which the primes are distributed. For example, the primes below 100 are

2,3,5,7,11,13,17,19,23,29,31,37,41,

43,47,53,59,61,67,71,73,79,89,93,97.

in 1798 Legendre made some highly significant empirical investigations concerning the distributions of primes. For x > 1, let (x) denote the number of primes < x. By some experimentation, Legendre advanced the conjecture that (x) is "approximately"

x

(A log x + B)

where A and B are numerical constants, not depending on x. By "approximately" Legendre meant that as x tends to infinity, the ratio

(x)

x/(A log x + B)

tends to 1. Actually, Legendre did not know that Gauss had done the same empirical experiments in 1792 and in 1793 without publishing them. Legendre was quite specific. He conjectured that A = 1 and B = 1.08366.... In particular, Legendre's conjecture implies that

(6)

Statement (6) is called the prime number theorem.

The first substantial progress toward a proof of (6) was made by the Russian mathematician Tchebycheff in 1851-1852. He showed, among other things, that for all sufficiently large x,

However, Tchebycheff's ideas could not be pushed far enough to prove the prime number theorem.

The year 1860 was the turning point in the efforts to give a proof of the prime number theorem. In that year Riemann published a paper in which he connected the function (x) with a certain function of a complex variable, subsequently called the Riemann zeta function. The analytic properties of the zeta function reflect themselves in the behavior of (x). Riemann made many conjectures about the zeta function, the most famous of which is the celebrated Riemann hypothesis, which predicts the points at which the zeta function is zero. This conjecture has been the object of an incredible effort by many of the finest minds of the last 100 years, but it remains unproven. If the Riemann hypothesis holds, it is possible to state the prime number theorem much more precisely than (6) by estimating how good an approximation to (x) is given by the function x/log x.

Although Riemann was not able to prove the prime number theorem, his ideas figured prominently in the first proof, which was discovered independently by Hadamard and de la Vallee Poussin, both in 1896.

Let us now turn to the fundamental theorem of arithmetic. Before we are able to give a proof of this basic result, we must first establish two preliminary facts which are important in their own right. Again the ideas are Euclid's.

Lemma 7: Let a,b, and c be nonzero. If a divides bc and a and b are relatively prime, then a divides c.

Proof:By Corollary 3 there exist x and y such that ax + by = 1. Since a|bc, there exists k such that bc = ka. Then

acx + bcy = c,

acx + kay = c,

a(cx + ky) = c,

a|c.

Theorem 8 (Euclid): Let p be a prime. If p divides a product ab, then either p divides a or p divides b.

Proof: The result is clear if a or b is zero. Therefore, assume both a and b are nonzero. Assume that p does not divide a (denoted pa). Then since p is prime, a and p are relatively prime. There for, by Lemma 7, p|b.

The reader should have no difficulty showing that if p > 1 is not a prime, there exist nonzero integers a and b such that pa, pb but nevertheless p|ab. Thus, theorem 8 gives an equivalent definition of a prime. A prime is an integer p > 1 such that for any integers a and b having the property that p|ab, we have either p|a or p|b. In more abstract contexts it turns out that this is the "proper" definition of a prime.

A useful consequence of Theorem 8 is

Let p be a prime. If p divides a₁ · a₂ ··· a_r, then p divides a_i for some i(1 < i < r).

Corollary 9: Let p be a prime. If p divides a₁ · a₂ ··· a_r, then p divides a_i for some i(1 < i < r).

Proof:Follows by induction from theorem 8.

Let us now address ourselves to the fundamental theorem.

Theorem 10 (Fundamental Theorem of Arithmetic): Let n be an integer greater than 1. Then n can be represented as a product of primes

n = p₁ ··· p_r.

Moreover, the representation of n is unique up to the rearrangement of the factors. That is, if n = q₁ ··· q_s is another representation of n as a product of primes, then r = s and we may renumber q₁,...,q_s so that p_i = q_i for 1 < i < r.

Proof: The first assertion is true by Lemma 5. Let us proceed by induction on r. If r = 1, then n is prime and the assertion is clear. Thus let us assume that r > 1 and that the theorem holds for n which are the product of r - 1 primes. Since p₁|n, we see that p₁|q₁ ··· q_s. Therefore by corollary 9, p₁|q_i for some i. Without loss of generality, suppose that p₁|q₁. Then, since p₁ and q₁ are both primes, p₁ = q₁. Therefore,

p₁p₂ ··· p_r = p₁q₂ ··· q_s,

which implies that

(7)

p₂ ··· p_r = q₂ ··· q_s

By our induction assumption and equation (7), we see that r -1 = s - 1 and that q₂,...q_s may be renumbered so that p_i = q_i for i = 2,...,r. Thus, since p₁ = q₁, the theorem has been proved for r and the induction is complete.