LeVeque - Elementary Theory of Numbers

ELEMENTARY THEORY OF NUMBERS
_________________

by

WILLIAM J. LEVEQUE

University of Michigan

DOVER PUBLICATIONS, INC.
New York

Copyright 1962, 1990 by William J. LeVeque.

All rights reserved.

This Dover edition, first published in 1990, is an unabridged, slightly corrected republication of the work originally published by Addison-Wesley Publishing Company, Inc., Reading, Mass., in 1962 in the Addison-Wesley Series in Introductory Mathematics.

Library of Congress Cataloging-in-Publication Data

LeVeque, William Judson.

Elementary theory of numbers / William J. LeVeque.

p. cm.

Reprint. Originally published: Reading, Mass. : Addison-Wesley, 1962 (Addison-Wesley series in introductory mathematics)

Includes bibliographical references.

eISBN 13: 978-0-486-15076-5

1. Number theory. I. Title. II. Series: Addison-Wesley series in introductory mathematics.
QA241.L57 1990
512.7dc20

90-2802
CIP

Manufactured in the United States by Courier Corporation
66348508
www.doverpublications.com

PREFACE

In the past few years there has been a great resurgence of interest in mathematics on both the secondary and undergraduate levels, and a growing recognition that the courses traditionally offered do not exhaust the mathematics which it is both possible and desirable to teach at those levels. Of course, not all of modern mathematics is accessible; some of it is too abstract to be comprehensible without more training in mathematical thinking, and some of it requires more technical knowledge than the young student can have mastered. Happily, the theory of numbers presents neither of these difficulties. The subject matter is the very concrete set of whole numbers, the rules are those the student has been accustomed to since grade school, and no assumption need be made as to special prior knowledge. To be sure, the results are not directly applicable in the physical world, but it is difficult to name a branch of mathematics in which the student encounters greater variety in types of proofs, or in which he will find more simple problems to stimulate his interest, challenge his ability, and increase his mathematical strength. For these and a number of other reasons, both the School Mathematics Study Group and the Committee on Undergraduate Programs have advocated the teaching of number theory to high-school and college students.

The present book is the result of an attempt to expose the subject in such form as to be accessible to persons with less mathematical training than those who would normally read, for example, the authors Topics in Number Theory, Volume I. There is considerable overlapping in material, of courseit is, after all, the same subjectbut the exposition is more leisurely, the examples and computational problems are more numerous, and certain relatively difficult topics have been omitted. Furthermore, the chapter on Gaussian arithmetic is entirely new, and the chapters on continued fractions and Diophantine equations have been almost entirely rewritten. I hope that the book may prove useful in high-school enrichment programs, in nontraditional freshman and sophomore courses, and in teacher training and refresher programs.

Certain problems are starred to indicate greater than average difficulty.

W. J. L.

CONTENTS

CHAPTER 1

INTRODUCTION

11 What is number theory? In number theory we are concerned with properties of certain of the integers (whole numbers)

... , 3, 2, 1, 0, 1, 2, 3,... ,

or sometimes with those properties of real or complex numbers which depend rather directly on the integers. It might be thought that there is little more that can be said about such simple mathematical objects than what has already been said in elementary arithmetic, but if you stop to think for a moment, you will realize that heretofore integers have not been considered as interesting objects in their own right, but simply as useful carriers of information. After totaling a grocery bill, you are interested in the amount of money involved, and not in the number representing that amount of money. In considering sin 31, you think either of an angular opening of a certain size, and the ratios of some lengths related to that angle, or of a certain position in a table of trigonometric functions, but not of any interesting properties that the number 31 might possess.

The attitude which will govern the treatment of integers in this text is perhaps best exemplified by a story told by G. H. Hardy, an eminent British number theorist who died in 1947. Hardy had a young protg, an Indian named Srinivasa Ramanujan, who had such a truly remarkable insight into hidden arithmetical relationships that, although he was almost uneducated mathematically, he did a great amount of first-rate original research in mathematics. Ramanujan was ill in a hospital in England, and Hardy went to visit him. When he arrived, he idly remarked that the taxi in which he had ridden had the license number 1729, which, he said, seemed to him a rather uninteresting number. Ramanujan immediately replied that, on the contrary, 1729 was singularly interesting, being the smallest positive integer expressible as a sum of two positive cubes in two different ways, namely 1729 = 103 + 93 = 123 + 13!

It should not be inferred that one needs to know all such little facts to understand number theory, or that one needs to be a lightning calculator; we simply wished to make the point that the question of what the smallest integer is which can be represented as a sum of cubes in two ways is of interest to a number theorist. It is interesting not so much for its own sake (after all, anyone could find the answer after a few minutes of unimaginative computation), but because it raises all sorts of further questions whose answers are by no means simple matters of calculation. For example, if s is any positive integer, about how large is the smallest integer representable as a sum of cubes of positive integers in s different ways? Or, are there infinitely many integers representable as a sum of cubes in two different ways? Or, how can one characterize in a different fashion the integers which can be represented as a sum of two cubes in at least one way? Or, are any cubes representable as a sum of two cubes? That is, has the equation

any solutions in positive integers x, y, and z? These questions, like that discussed by Hardy and Ramanujan, are concerned with integers, but they also have an additional element which somehow makes them more significant: they are concerned not with a particular integer, but with whole classes or collections of integers. It is this feature of generality, perhaps, which distinguishes the theory of numbers from simple arithmetic. Still, there is a gradual shading from one into the other, and number theory is, appropriately enough, sometimes called higher arithmetic.

In view of the apparent simplicity of the subject matter, it is not surprising that number-theoretic questions have been considered throughout almost the entire history of recorded mathematics. One of the earliest such problems must have been that of solving the Pythagorean equation

For centuries it was supposed that the classical theorem embodied in (2) concerning the sides of a right triangle was due either to Pythagoras or a member of his school (about 550 B.C). Recently interpreted cuneiform texts give strong evidence, however, that Babylonian mathematicians not only knew the theorem as early as 1600 B.C., but that they knew how to compute all integral solutions