Số học

THE HIGHER
ARITHMETIC
AN INTRODUCTION TO
THE THEORY OF NUMBERS
Eighth edition
H. Davenport
M.A., SC.D., F.R.S.
late Rouse Ball Professor of Mathematics
in the University of Cambridge and
Fellow of Trinity College
Editing and additional material by
James H. Davenport
CAMBRIDGE UNIVERSITY PRESS
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo
Cambridge University Press
The Edinburgh Building, Cambridge CB2 8RU, UK
First published in print format
ISBN-13 978-0-521-72236-0
ISBN-13 978-0-511-45555-1
© The estate of H. Davenport 2008
2008
Information on this title: www.cambridge.org/9780521722360
This publication is in copyright. Subject to statutory exception and to the
provision of relevant collective licensing agreements, no reproduction of any part
may take place without the written permission of Cambridge University Press.
Cambridge University Press has no responsibility for the persistence or accuracy
of urls for external or third-party internet websites referred to in this publication,
and does not guarantee that any content on such websites is, or will remain,
accurate or appropriate.
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
eBook (EBL)
paperback
CONTENTS
Introduction
page viii
I Factorization and the Primes
1
1. The laws of arithmetic 1
2. Proof by induction 6
3. Prime numbers 8
4. The fundamental theorem of arithmetic 9
5. Consequences of the fundamental theorem 12
6. Euclid’s algorithm 16
7. Another proof of the fundamental theorem 18
8. A property of the H.C.F 19
9. Factorizing a number 22
10. The series of primes 25
II Congruences
31
1. The congruence notation 31
2. Linear congruences 33
3. Fermat’s theorem 35
4. Euler’s function φ(m) 37
5. Wilson’s theorem 40
6. Algebraic congruences 41
7. Congruences to a prime modulus 42
8. Congruences in several unknowns 45
9. Congruences covering all numbers 46
v
vi
Contents
III Quadratic Residues
49
1. Primitive roots 49
2. Indices 53
3. Quadratic residues 55
4. Gauss’s lemma 58
5. The law of reciprocity 59
6. The distribution of the quadratic residues 63
IV Continued Fractions
68
1. Introduction 68
2. The general continued fraction 70
3. Euler’s rule 72
4. The convergents to a continued fraction 74
5. The equation ax − by = 1 77
6. Infinite continued fractions 78
7. Diophantine approximation 82
8. Quadratic irrationals 83
9. Purely periodic continued fractions 86
10. Lagrange’s theorem 92
11. Pell’s equation 94
12. A geometrical interpretation of continued
fractions 99
V Sums of Squares
103
1. Numbers representable by two squares 103
2. Primes of the form 4k + 1 104
3. Constructions for x and y 108
4. Representation by four squares 111
5. Representation by three squares 114
VI Quadratic Forms
116
1. Introduction 116
2. Equivalent forms 117
3. The discriminant 120
4. The representation of a number by a form 122
5. Three examples 124
6. The reduction of positive definite forms 126
7. The reduced forms 128
8. The number of representations 131
9. The class-number 133
Contents
vii
VII Some Diophantine Equations
137
1. Introduction 137
2. The equation x
2
+ y
2
= z
2
138
3. The equation ax
2
+ by
2
= z
2
140
4. Elliptic equations and curves 145
5. Elliptic equations modulo primes 151
6. Fermat’s Last Theorem 154
7. The equation x
3
+ y
3
= z
3
+ w
3
157
8. Further developments 159
VIII Computers and Number Theory
165
1. Introduction 165
2. Testing for primality 168
3. ‘Random’ number generators 173
4. Pollard’s factoring methods 179
5. Factoring and primality via elliptic curves 185
6. Factoring large numbers 188
7. The Diffie–Hellman cryptographic method 194
8. The RSA cryptographic method 199
9. Primality testing revisited 200
Exercises 209
Hints 222
Answers 225
Bibliography 235
Index 237
INTRODUCTION
The higher arithmetic, or the theory of numbers, is concerned with the
properties of the natural numbers 1, 2, 3, These numbers must have
exercised human curiosity from a very early period; and in all the records
of ancient civilizations there is evidence of some preoccupation with arith-
metic over and above the needs of everyday life. But as a systematic and
independent science, the higher arithmetic is entirely a creation of modern
times, and can be said to date from the discoveries of Fermat (1601–1665).
A peculiarity of the higher arithmetic is the great difficulty which has
often been experienced in proving simple general theorems which had
been suggested quite naturally by numerical evidence. ‘It is just this,’ said
Gauss, ‘which gives the higher arithmetic that magical charm which has
made it the favourite science of the greatest mathematicians, not to men-
tion its inexhaustible wealth, wherein it so greatly surpasses other parts of
mathematics.’
The theory of numbers is generally considered to be the ‘purest’ branch
of pure mathematics. It certainly has very few direct applications to
other sciences, but it has one feature in common with them, namely the
inspiration which it derives from experiment, which takes the form of test-
ing possible general theorems by numerical examples. Such experiment,
though necessary in some form to progress in every part of mathematics,
has played a greater part in the development of the theory of numbers than
elsewhere; for in other branches of mathematics the evidence found in this
way is too often fragmentary and misleading.
As regards the present book, the author is well aware that it will not be
read without effort by those who are not, in some sense at least, mathe-
maticians. But the difficulty is partly that of the subject itself. It cannot be
evaded by using imperfect analogies, or by presenting the proofs in a way
viii
Introduction
ix
which may convey the main idea of the argument, but is inaccurate in detail.
The theory of numbers is by its nature the most exact of all the sciences,
and demands exactness of thought and exposition from its devotees.
The theorems and their proofs are often illustrated by numerical exam-
ples. These are generally of a very simple kind, and may be despised by
those who enjoy numerical calculation. But the function of these examples
is solely to illustrate the general theory, and the question of how arithmeti-
cal calculations can most effectively be carried out is beyond the scope of
this book.
The author is indebted to many friends, and most of all to Professor
Erd
˝
os, Professor Mordell and Professor Rogers, for suggestions and cor-
rections. He is also indebted to Captain Draim for permission to include an
account of his algorithm.
The material for the fifth edition was prepared by Professor D. J. Lewis
and Dr J. H. Davenport. The problems and answers are based on the
suggestions of Professor R. K. Guy.
Chapter VIII and the associated exercises were written for the sixth edi-
tion by Professor J. H. Davenport. For the seventh edition, he updated
Chapter VII to mention Wiles’ proof of Fermat’s Last Theorem, and is
grateful to Professor J. H. Silverman for his comments.
For the eighth edition, many people contributed suggestions, notably
Dr J. F. McKee and Dr G. K. Sankaran. Cambridge University Press
kindly re-typeset the book for the eighth edition, which has allowed
a few corrections and the preparation of an electronic complement:
www.cambridge.org/davenport. References to further material in
the electronic complement, when known at the time this book went to print,
are marked thus: ♠:0.

I
FACTORIZATION AND THE PRIMES
1. The laws of arithmetic
The object of the higher arithmetic is to discover and to establish general
propositions concerning the natural numbers 1, 2, 3, of ordinary arith-
metic. Examples of such propositions are the fundamental theorem (I.4)
∗
that every natural number can be factorized into prime numbers in one
and only one way, and Lagrange’s theorem (V.4) that every natural num-
ber can be expressed as a sum of four or fewer perfect squares. We are not
concerned with numerical calculations, except as illustrative examples, nor
are we much concerned with numerical curiosities except where they are
relevant to general propositions.
We learn arithmetic experimentally in early childhood by playing with
objects such as beads or marbles. We first learn addition by combining two
sets of objects into a single set, and later we learn multiplication, in the form
of repeated addition. Gradually we learn how to calculate with numbers,
and we become familiar with the laws of arithmetic: laws which probably
carry more conviction to our minds than any other propositions in the whole
range of human knowledge.
The higher arithmetic is a deductive science, based on the laws of arith-
metic which we all know, though we may never have seen them formulated
in general terms. They can be expressed as follows.
∗
References in this form are to chapters and sections of chapters of this book.
1
2
The Higher Arithmetic
Addition. Any two natural numbers a and b have a sum, denoted by
a + b, which is itself a natural number. The operation of addition satisfies
the two laws:
a + b = b + a (commutative law of addition),
a + (b + c) = (a + b) + c (associative law of addition),
the brackets in the last formula serving to indicate the way in which the
operations are carried out.
Multiplication. Any two natural numbers a and b have a product, denoted
by a × b or ab, which is itself a natural number. The operation of
multiplication satisfies the two laws
ab = ba (commutative law of multiplication),
a(bc) = (ab)c (associative law of multiplication).
There is also a law which involves operations both of addition and of
multiplication:
a(b + c) = ab+ ac (the distributive law).
Order.Ifa and b are any two natural numbers, then either a is equal
to b or a is less than b or b is less than a, and of these three possibilities
exactly one must occur. The statement that a is less than b is expressed
symbolically by a < b, and when this is the case we also say that b is
greater than a, expressed by b > a. The fundamental law governing this
notion of order is that
if a < b and b < cthena< c.
There are also two other laws which connect the notion of order with the
operations of addition and multiplication. They are that
if a< bthena+ c < b + c and ac < bc
for any natural number c.
Cancellation. There are two laws of cancellation which, though they
follow logically from the laws of order which have just been stated, are
important enough to be formulated explicitly. The first is that
if a+ x = a + ythenx= y.
This follows from the fact that if x < y then a + x < a + y, which is
contrary to the hypothesis, and similarly it is impossible that y < x,and
therefore x = y. In the same way we get the second law of cancellation,
which states that
if ax= ay then x = y.

Xem chi tiết: Số học