**Uh-oh, it looks like your Internet Explorer is out of date.**

For a better shopping experience, please upgrade now.

## NOOK Book(eBook)

^{$}10.99

Available on Compatible NOOK Devices and the free NOOK Apps.

^{®}See Details

## Overview

Ethan D. Bolker teaches mathematics and computer science at the University of Massachusetts, Boston.

## ADVERTISEMENT

## Product Details

ISBN-13: | 9780486153094 |
---|---|

Publisher: | Dover Publications |

Publication date: | 05/17/2012 |

Series: | Dover Books on Mathematics |

Sold by: | Barnes & Noble |

Format: | NOOK Book |

Pages: | 208 |

File size: | 5 MB |

## 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

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 *x*2 + *y*2 = *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* = ± *p*1 ... *pr* = ±*q*1 ... *q*s where the ITLπITL and the *qj* are primes, then*r* = *s,* and the sequence |*p*1|, ..., |*pr*| is a permutation of the sequence |*q*1|, ..., |*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

*ax*0 + *by*0 = (*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 <*x*0, *y*0> to Eq. (5). Then

*a'*(*x - c'x*0) = *-b'*(*y - c'y*0). *(6)*

Since (*a', b'*) = 1 (Problem 6.11), Eq. (6) implies

*a'*|*y* – *cy*0

so that

*y* = *c'y*0 + *a'n*

for some integer *n.* Then

*a* '(*x* – *c'x*0) = – *a'b'n*

so

*x = c'x*0 - *b'n*. *(7)*

Moreover, if *x* and *y* are defined by Eqs. (4) then <*x, y*> solves Eq. (3).

*4. THE DIOPHANTINE EQUATION a*1*x*1 + ... + *anxn = c*

Let *a*1, ..., *an* be integers at least one of which is not 0. A greatest common divisor *d* of *a*1, ..., *an* is a common divisor which is a multiple of every common divisor. Write (*a*1, ..., *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

*a*1*x*1 + ... + *anxn = c**(8)*

(some *ai* ≠ 0) has a solution if and only if (*a*1, ..., *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 (*a*1, *a*2, ..., *an*) = ((*a*1, *a*2), *a*3,..., *an*) (Problem 6.14). Then use Theorem 3.1 and the inductive hypothesis to find integers *y*1, *y*2, *x, x*3, ..., *x*n satisfying

*a*1*y*1 + *a*2*y*2 = (*a*1, *a*2)

and

(*a*1, *a*2)*x* + *a*3*x*3 + ... + *anxn* = *c.*

If we set *x*1 = *y*1*x* and *x*2 = *y*2*x,* then <*x*1, ..., *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* = {*q*1, ..., *qn*} is a nonempty subset of *P.* Let *m* = 1 + *q*1 ... *qn* ≠ ± 1. The fundamental theorem of arithmetic implies that there is a prime *p* which divides *m.* Since no *q*1 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, 4*k;* 4*k* + 1; 4*k* + 2; or 4*k* + 3. Since 2 | 4*k* and 2 | 4*k* + 2, every odd prime is of the form 4*k* + 1 or 4*k* + 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 4*k* + 1 is again of that form.

*Proof.* It clearly suffices to prove this lemma for the product of just two integers. Let *n* = 4*k* + 1 and *n'* = 4*k*' + 1. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

**5.3 Theorem.** There are infinitely many primes of the form 4*k* + 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* = {*q*1, ..., *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 4*k* + 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 4*n* + 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 4*k* + 3 is always of the form 4*k* + 1. There *are* infinitely many primes of the form 4*k* + 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 2*n* 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)(2*n* – 1) is always divisible by 6.

**6.6** Prove that the Diophantine equation

3*y*2 – 1 = *x*2

has no solutions. That is, 3*y*2 – 1 is never a perfect square.

**6.7** Prove: If 2 *x n* and 3 *x n,* then 24 | (*n*2 + 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 *nx*2 = *y*2 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 fromElementary Number TheorybyEthan 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.

## Table of Contents

#### Contents

DOVER BOOKS ON MATHEMATICS,Title Page,

Copyright Page,

Preface,

Preface to the Dover Edition,

Dedication,

1 - Linear Diophantine Equations,

2 - Congruence,

3 - Polynomials,

4 - The Group of Units of Zn,

5 - Quadratic Reciprocity,,

6 - Quadratic Numbers Fields,

7 - The Fermat Conjecture,

APPENDIX 1 - Unique Factorization,

APPENDIX 2 - Primitive Roots,

APPENDIX 3 - Indices for Φ(315),

APPENDIX 4 - Fundamental Units in Real Quadratic Number Fields,

APPENDIX 5 - Chronological Table,

Bibliography,

List of Symbols,

List of Errata,

Index,