Read an Excerpt
Elementary Number Theory
An Algebraic Approach
By Ethan D. Bolker Dover Publications, Inc.
Copyright © 2007 Ethan D. Bolker
All rights reserved.
ISBN: 978-0-486-15309-4
CHAPTER 1
Linear Diophantine Equations
We shall begin our study of number theory not with the topic announced in the title of this first chapter but with an empirical investigation of a problem studied and solved by Fermat.
1. SUMS OF SQUARES
Which positive integers can be written as sums of two integral squares? Let us call such integers representable; the first few representable integers are 1, 2, 4, 5, 8, 9, 10, 13, and 16. What pattern does the sequence of representable integers form? How can we decide whether a given integer is representable? We need more data to make intelligent guesses.
The representable integers less than 100 appear in boldface in Table 1. The arrangement of that table in rows of eight allows us to guess a part of the pattern; the third, sixth, and seventh columns seem free of representable integers. The reader is invited (in Problem 6.1) to prove that that phenomenon continues. It is harder to predict which integers in the other columns are representable. Some hints will be found in Problems 6.2 and 6.3.
Some integers can be represented more than one way. The smallest such is 25 = 52 + 02 = 42 + 32; the others less than 100 are 50, 65, and 85.
The least integer representable three ways is
325 = 182 + 12 = 172 + 62 = 152 + 102.
Counting the number of ways n can be represented gives clues to the pattern of representable integers. (See Problems 6.2 and 6.3.)
The recorded history of the study of representable integers starts in about 250 A.D. with Diophantos. Problems in which integral values of the unknowns are sought are called Diophantine in his honor. In the seventeenth century Fermat gave, as a simple function of n, the number of solutions to the Diophantine equation x2 + y2 = n and thus answered all the questions we have raised about the representability of integers. His answer is our Theorem 36.3.
In the preface to the collected works of Eisenstein, Gauss wrote of number theory that "... important propositions, with the impress of simplicity upon them, are often easily discoverable by induction and yet are of so profound a character that we cannot find their demonstration until after many vain attempts; and even then, when we do suceed, it is often by some tedious and artificial process, while the simpler methods may long remain concealed." The argument which stretches from here to our proof of Fermat's theorem on representable integers and beyond is not the shortest possible, but by lengthening and modernizing it we have freed it of many of the "artificial processes" and revealed the "simpler methods" to which Gauss refers.
2. DIVISIBILITY AND UNIQUE FACTORIZATION
The simplest nontrivial Diophantine equation,
ax = b, (a ≠ 0) (1)
has a solution if and only if a divides b; when that occurs we write a | b and say too that a is a factor or divisor of b, while b is a multiple of a. Since a 0 = 0, we have a| 0 for every a. An integer p other than 0, 1, or – 1 is prime when its only divisors are ±1 and ±p. If n ≠ 0, ±1 is not prime, it is composite.
2.1 Theorem. Every nonzero integer other than ±1 can be written "uniquely" as a product of primes.
The uniqueness is qualified by the quotation marks because, for example,
6 = (-2)(-3) = 3 · 2
and 2, – 2, 3, and – 3 are all primes. What we mean by "uniquely" is, of course, that if n = ± p1 ... pr = ±q1 ... qs where the ITLπITL and the qj are primes, thenr = s, and the sequence |p1|, ..., |pr| is a permutation of the sequence |q1|, ..., |qs|.
In Appendix 1 we prove that Lemma 2.2 below implies Theorem 2.1, the fundamental theorem of arithmetic. We repeat here some of the auxiliary definitions and intermediate steps in that argument.
2.2 Lemma. Given integers m and n ≠ 0 there are unique integers q and r with 0 = ≤ r< |n| for which
m = qn + r.
This is simply a formal assertion of the possibility of "division with remainder" in Z, the ring of integers.
2.3 Definition. The integer d is a greatest common divisor of a and b in Z if d | a and d | b, and if whenever c | a and c | b, then c | d.
2.4 Theorem. Every pair <a, b > of integers except <0, 0> has a greatest common divisor d. The Diophantine equation
ax + by = d (2)
has a solution.
There are several algorithms for computing d and solving Eq. (2) in a predictable finite number of steps. The most common, the Euclidean algorithm, is illustrated in Example 15 of Appendix 1.
If d is a greatest common divisor of a and b, then so is – d; no other integer enjoys this privilege. We shall write (a, b) for the positive greatest common divisor of a and b and <a, b > for the ordered pair formed by a and b. Thus (4, 6) = 2 and (25, -4) = 1. If a ≠ 0 then (a, 0) = |a| because the common divisors of a and 0 are just the divisors of a; (0, 0) is undefined.
2.5 Definition. The integers a and b are relatively prime, or coprime, if and only if (a, b) = 1.
If p is prime and a ≠ ± 1, then p and a are relatively prime if and only if p x a, that is, p does not divide a.
2.6 Theorem. If a | bc and (a, b) = 1, then a | c. In particular, if a prime divides a product, then it divides one of the factors. (See Appendix 1, Theorem 16.)
2.7 Definition. An integer m ≠ 0 is a common multiple of a and b if a | m and b | m. If neither a nor b is 0, then |ab| is a common multiple, so among the positive common multiples there is a least, which we write
l.c.m. {a, b}.
2.8 Theorem. If ab > 0, then the least common multiple of a and b is ab/(a, b); the least common multiple divides any common multiple.
3. THE DIOPHANTINE EQUATION ax + by = c
The second simplest Diophantine equation is ax + by = c which one often meets in secondary school in a form such as: "How many dimes and quarters make n cents?" That banking problem is clearly hopeless unless 5 | n.
3.1 Theorem. The Diophantine equation
ax + by = c, <a, b> ≠ <0, 0>(3)
has solutions if and only if (a, b)|c. When solutions exist, they are all given by
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)
where
ax0 + by0 = (a, b) (5)
and n is any integer.
Proof. "Only if" is obvious. To show that Eqs. (4) give all the solutions suppose (a, b) | c and that <x, y> is a solution to Eq. (3). Let a' = a /(a, b); b' = b /(a, b); and c' = c /(a, b). Use Theorem 2.4 to find a solution <x0, y0> to Eq. (5). Then
a'(x - c'x0) = -b'(y - c'y0). (6)
Since (a', b') = 1 (Problem 6.11), Eq. (6) implies
a'|y – cy0
so that
y = c'y0 + a'n
for some integer n. Then
a '(x – c'x0) = – a'b'n
so
x = c'x0 - b'n. (7)
Moreover, if x and y are defined by Eqs. (4) then <x, y> solves Eq. (3).
4. THE DIOPHANTINE EQUATION a1x1 + ... + anxn = c
Let a1, ..., an be integers at least one of which is not 0. A greatest common divisor d of a1, ..., an is a common divisor which is a multiple of every common divisor. Write (a1, ..., an) for the unique positive greatest common divisor the proof of whose existence is Problem 6.13. Now we generalize Theorem 3.1.
4.1 Theorem. The Diophantine equation
a1x1 + ... + anxn = c(8)
(some ai ≠ 0) has a solution if and only if (a1, ..., an) | c.
Proof. When n = 2, this is just Theorem 3.1, so our induction on n, the number of variables, begins well. Suppose n > 2. We shall show that Eq. (8) can be solved assuming that similar equations in n – 1 variables can be solved. To this end observe that (a1, a2, ..., an) = ((a1, a2), a3,..., an) (Problem 6.14). Then use Theorem 3.1 and the inductive hypothesis to find integers y1, y2, x, x3, ..., xn satisfying
a1y1 + a2y2 = (a1, a2)
and
(a1, a2)x + a3x3 + ... + anxn = c.
If we set x1 = y1x and x2 = y2x, then <x1, ..., xn > solves Eq. (8).
5. THE INFINITUDE OF THE PRIMES
This section contains some information on the way in which the primes are distributed in Z and introduces some techniques which we shall generalize in the next chapter. Euclid knew the following theorem.
5.1 Theorem. There are infinitely many primes.
Proof. Let P be the set of primes. Since 2 is prime, P is not empty. We shall show that no finite subset Q of P exhausts P. Suppose Q = {q1, ..., qn} is a nonempty subset of P. Let m = 1 + q1 ... qn ≠ ± 1. The fundamental theorem of arithmetic implies that there is a prime p which divides m. Since no q1 divides m, p [not member of] Q. That is, Q ≠ P, so P is infinite.
We can exploit this method to prove a little more. Lemma 2.2 implies that every integer n may be written in just one of the forms, 4k; 4k + 1; 4k + 2; or 4k + 3. Since 2 | 4k and 2 | 4k + 2, every odd prime is of the form 4k + 1 or 4k + 3. The following lemma is a very special case of a principle we shall introduce in Section 7.
5.2 Lemma. The product of integers of the form 4k + 1 is again of that form.
Proof. It clearly suffices to prove this lemma for the product of just two integers. Let n = 4k + 1 and n' = 4k' + 1. Then
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
5.3 Theorem. There are infinitely many primes of the form 4k + 3.
Proof. Let P be the set of such primes. Since 3 [member of] P, P is not empty. We shall show that no finite subset Q of P exhausts P. Suppose Q = {q1, ..., qn} is a nonempty subset of P. Let
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
The fundamental theorem of arithmetic implies that m is a product of primes. Since m is odd, every prime divisor of m is odd. If all the prime divisors of m were of the form 4k + 1, then m would be of that form (Lemma 3.2), which is false. Therefore there is a prime p [member of] P which divides m. Since no qi divides m, p [not member of] Q. That is Q ≠ P; P is infinite.
Note that we have not used the full strength of the fundamental theorem of arithmetic. We needed only the existence, not the "uniqueness," of a prime factorization of m to prove Theorems 5.1 and 5.3.
The technique we used to prove Theorem 5.3 fails to prove the infinitude of the primes of the form 4n + 1 since the analogue of Lemma 3.2 is false: (4 · 1 + 3)(4 · 0 + 3) = 7 · 3 = 21 = 4 · 5 + 1. In fact, the product of two numbers of the form 4k + 3 is always of the form 4k + 1. There are infinitely many primes of the form 4k + 1; we shall prove it in Section 12. Much more is known. A justly famous theorem of Dirichlet's asserts that the arithmetic progression of numbers of the form ak + b contains infinitely many primes whenever a ≠ 0 and (a, b) = 1. Dirichlet's theorem is beyond the scope of this book; we shall, however, prove several special cases.
6. PROBLEMS
6.1 Show that the third, sixth, and seventh columns of Table 1 remain free of representable integers.
6.2 Prove that 2n is representable when n is. Is the converse true?
6.3 Prove that mn is representable when m and n are. How many ways can mn be represented?
6.4* Formulate some guesses about integers which can be represented as a sum of three squares. Show that column 7 in Table 1 contains no such integers. We shall show in Section 40 that every integer is a sum of four squares.
6.5 Show n (n – 1)(2n – 1) is always divisible by 6.
6.6 Prove that the Diophantine equation
3y2 – 1 = x2
has no solutions. That is, 3y2 – 1 is never a perfect square.
6.7 Prove: If 2 x n and 3 x n, then 24 | (n2 + 23).
6.8 What is (32 · 56 · 73 · 17, 321 · 5 · 13)? The answer is easily computed without the Euclidean algorithm and suggests a useful theorem for computing greatest common divisors when prime factorizations are known. That theorem simplifies some of the problems which follow.
6.9 Prove Theorem 2.8.
6.10 Prove: If (a, b) = 1 and ab is a square, then |a| and |b| are squares.
6.11 Prove (a/(a, b), b/(a, b)) = 1.
6.12 Use the fundamental theorem of arithmetic to show that the Diophantine equation nx2 = y2 has a solution if and only if n is a square. Deduce that [square root of n] is irrational unless n is a square.
(Continues...)
Excerpted from Elementary Number Theory by Ethan D. Bolker. Copyright © 2007 Ethan D. Bolker. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
