# Book:G.H. Hardy/An Introduction to the Theory of Numbers/Fifth Edition

## G.H. Hardy and E.M. Wright: An Introduction to the Theory of Numbers (5th Edition)

Published $\text {1979}$, Oxford University Press

ISBN 0-19-853171-0.

### Contents

Preface to the Fifth Edition (Aberdeen, October 1978, E.M.W)
Preface to the First Edition (Oxford, August 1938, G.H.H. and E.M.W)
REMARKS ON NOTATION
$\text {I}$. THE SERIES OF PRIMES (1)
1.1. Divisibility of integers
1.2. Prime numbers
1.3. Statement of the fundamental theorem of arithmetic
1.4. The sequence of primes
1.5. Some questions concerning primes
1.6. Some notations
1.7. The logarithmic function
1.8. Statement of the prime number theorem
$\text {II}$. THE SERIES OF PRIMES (2)
2.1. First proof of Euclid's second theorem
2.2. Further deductions from Euclid's argument
2.3. Primes in certain arithmetical progressions
2.4. Second proof of Euclid's theorem
2.5. Fermat's and Mersenne's numbers
2.6. Third proof of Euclid's theorem
2.7. Further remarks on formulae for primes
2.8. Unsolved problems concerning primes
2.9. Moduli of integers
2.10. Proof of the fundamental theorem of arithmetic
2.11. Another proof of the fundamental theorem
$\text {III}$. FAREY SERIES AND A THEOREM OF MINKOWSKI
3.1. The definition and simplest properties of a Farey series
3.2. The equivalence of the two characteristic properties
3.3. First proof of Theorems $28$ and $29$
3.4. Second proof of the theorems
3.5. The integral lattice
3.6. Some simple properties of the fundamental lattice
3.7. Third proof of Theorems $28$ and $29$
3.8. The Farey dissection of the continuum
3.9. A theorem of Minkowski
3.10. Proof of Minkowski's theorem
3.11. Developments of Theorem $37$
$\text {IV}$. IRRATIONAL NUMBERS
4.1. Some generalities
4.2. Numbers known to be irrational
4.3. The theorem of Pythagoras and its generalizations
4.4. The use of the fundamental theorem in the proofs of Theorems $43$-$45$
4.5. A historical digression
4.6. Geometrical proof of the irrationality of $\sqrt 5$
4.7. Some more irrational numbers
$\text {V}$. CONGRUENCES AND RESIDUES
5.1. Highest common divisor and least common multiple
5.2. Congruences and classes of residues
5.3. Elementary properties of congruences
5.4. Linear congruences
5.5. Euler's function $\map \phi m$
5.6. Applications of Theorems $59$ and $61$ to trigonometrical series
5.7. A general principle
5.8. Construction of the regular polygon of $17$ sides
$\text {VI}$. FERMAT'S THEOREM AND ITS CONSEQUENCES
6.1. Fermat's theorem
6.2. Some properties of binomial coefficients
6.3. A second proof of Theorem $72$
6.4. Proof of Theorem $22$
6.6. Special cases of Theorem $79$: Wilson's theorem
6.7. Elementary properties of quadratic residues and non-residues
6.8. The order of $a \pmod m$
6.9. The converse of Fermat's theorem
6.10. Divisibility of $2^{p - 1} - 1$ by $p^2$
6.11. Gauss's lemma and the quadratic character of $2$
6.12. The law of reciprocity
6.13. Proof of the law of reciprocity
6.14. Tests for primality
6.15. Factors of Mersenne numbers; a theorem of Euler
$\text {VII}$. GENERAL PROPERTIES OF CONGRUENCES
7.1. Roots of congruences
7.2. Integral polynomials and identical congruences
7.3. Divisibility of polynomials (mod $m$)
7.4. Roots of congruences to a prime modulus
7.5. Some applications of the general theorems
7.6. Lagrange's proof of Fermst's and Wilson's theorems
7.7. The residue of $\set {\tfrac 1 2 \paren {p - 1} }!$
7.8. A theorem of Wolstenholme
7.9. The theorem of von Staudt
7.10. Proof of von Staudt's theorem
$\text {VIII}$. CONGRUENCES TO COMPOSITE MODULI
8.1. Linear congruences
8.2. Congruences of higher degree
8.3. Congruences to a prime-power modulus
8.4. Examples
8.5. Bauer's identical congruence
8.6. Bauer's congruence: the case $p = 2$
8.7. A theorem of Leudesdorf
8.8. Further consequences of Bauer's theorem
8.9. The residues of $2^{p - 1}$ and $\paren {p - 1}!$ to modulus $p^2$
$\text {IX}$. THE REPRESENTATION OF NUMBERS BY DECIMALS
9.1. The decimal associated with a given number
9.2. Terminating and recurring decimals
9.3. Representation of numbers in other scales
9.4. Irrationals defined by decimals
9.5. Tests for divisibility
9.6. Decimals with the maximum period
9.7. Bachet's problem of the weights
9.8. The game of Nim
9.9. Integers with missing digits
9.10. Sets of measure zero
9.11. Decimals with missing digits
9.12. Normal numbers
9.13. Proof that almost all numbers are normal
$\text {X}$. CONTINUED FRACTIONS
10.1. Finite continued fractions
10.2. Convergents to a continued fraction
10.3. Continued fractions with positive quotients
10.4. Simple continued fractions
10.5. The representation of an irreducible rational fraction by a simple continued fraction
10.6. The continued fraction algorithm and Euclid's algorithm
10.7. The difference between the fraction and its convergence
10.8. infinite simple continued fractions
10.9. The representation of an irrational number by an infinite continued fraction
10.10. A lemma
10.11. Equivalent numbers
10.12. Periodic continued fractions
10.14. The series of Fibonacci and Lucas
10.15. Approximation by convergents
$\text {XI}$. APPROXIMATION OF IRRATIONALS BY RATIONALS
11.1. Statement of the problem
11.2. Generalities concerning the problem
11.3. An argument of Dirichlet
11.4. Orders of approximation
11.5. Algebraic and transcendental members
11.6. The existence of transcendental numbers
11.7. Liouville's theorem and the construction of transcendental numbers
11.8. The measure of the closest approximations to an arbitrary irrational
11.9. Another theorem concerning the convergents to a continued fraction
11.10. Continued fractions with bounded quotients
11.11. Further theorems concerning approximation
11.12. Simultaneous approximation
11.13. The transcendence of $e$
11.14. The transcendence of $\pi$
$\text {XII}$. THE FUNDAMENTAL THEOREM OF ARITHMETIC IN $\map k 1$, $\map k i$, AND $\map k \rho$
12.1. Algebraic numbers and integers
12.2. The rational integers, the Gaussian integers, and the integers of $\map k \rho$
12.3. Euclid's algorithm
12.4. Application of Euclid's algorithm to the fundamental theorem in $\map k 1$
12.5. Historical remarks on Euclid's algorithm and the fundamental theorem
12.6. Properties of the Gaussian integers
12.7. Primes in $\map k i$
12.8. The fundamental theorem of arithmetic in $\map k i$
12.9. The integers of $\map k \rho$
$\text {XIII}$. SOME DIOPHANTINE EQUATIONS
13.1. Fermat's last theorem
13.2. The equation $x^2 + y^2 = z^2$
13.3. The equation $x^4 + y^4 = z^4$
13.4. The equation $x^3 + y^3 = z^3$
13.5. The equation of $x^3 + y^3 = 3z^3$
13.6. The expression of a rations as a sum of rational cubes
13.7. The equation $x^3 + y^3 + x^3 = t^3$
$\text {XIV}$. QUADRATIC FIELDS (1)
14.1. Algebraic melds
14.2. Algebraic numbers and integers; primitive polynomials
14.3. The general quadratic field $\map k {\sqrt m}$
14.4. Unities and primes
14.5. The unities of $\map k {\sqrt 2}$
14.6. Fields in which the fundamental theorem is false
14.7. Complex Euclidean fields
14.8. Real Euclidean fields
14.9. Real Euclidean fields (continued)
$\text {XV}$. QUADRATIC FIELDS (2)
15.1. The primes of $\map k i$
15.2. Fermat's theorem in $\map k i$
15.3. The primes of $\map k \rho$
15.4. The primes of $\map k {\sqrt 2}$ and $\map k {\sqrt 5}$
15.5. Lucas's test for the primarily of the Mersenne number $M_{4 n + 3}$
15.6. General remarks on the arithmetic of quadratic fields
15.7. Ideals in a quadratic fields
15.8. Other fields
$\text {XVI}$. THE ARITHMETICAL FUNCTIONS $\map \phi n$, $\map d n$, $\map \sigma n$, $\map r n$
16.1. The function $\map \phi n$
16.2. A further proof of Theorem $63$
16.3. The Möbius function
16.4. The Möbius inversion formula
16.5. Further inversion formulae
16.6. Evaluation of Ramanujan's sum
16.7. The functions $\map d n$ and $\map {\sigma_k} n$
16.8. Perfect numbers
16.9. The function $\map r n$
16.10. Proof of the formula for $\map r n$
$\text {XVII}$. GENERATING FUNCTIONS OF ARITHMETICAL FUNCTIONS
17.1 The generation of arithmetical functions by means of Dirichlet series
17.2. The zeta function
17.3. The behaviour of $\map \zeta s$ when $s \to 1$
17.4. Multiplication of Dirichlet series
17.5. The generating functions of some special arithmetical functions
17.6. The analytical interpretation of the Möbius formula
17.7. The function $\map \Lambda n$
17.8. Further examples of generating functions
17.9. The generating function of $\map r n$
17.10. Generating functions of other types
$\text {XVIII}$. THE ORDER OF MAGNITUDE OF ARITHMETICAL FUNCTIONS
18.1. The order of $\map d n$
18.2. The average order of $\map d n$
18.3. The order of $\map \sigma n$
18.4. The order of $\map \phi n$
18.5. The average order of $\map \phi n$
18.6. The number of squarefree numbers
18.7. The order of $\map r n$
$\text {XIX}$. PARTITIONS
19.1. The general problem of additive arithmetic
19.2. Partitions of numbers
19.3. The incepting function of $\map p n$
19.4. Other generating functions
19.5. Two theorems of Euler
19.6. Further algebraical identities
19.7. Another formula for $\map F x$
19.8. A theorem of Jacobi
19.9. Special cases of Jacobi's identity
19.10. Applications of Theorem $353$
19.11. Elementary proof of Theorem $358$
19.12. Congruence properties of $\map p n$
19.13. The Rogers-Ramanujan identities
19.14. Proof of Theorems $362$ and $363$
19.15. Ramanujan's continued fraction
$\text {XX}$. THE REPRESENTATION OF A NUMBER BY TWO OR FOUR SQUARES
20.1. Waring's problem: the numbers $\map g k$ and $\map G k$
20.2. Squares
20.3. Second proof of Theorem $366$
20.4. Third and fourth proofs of Theorem $366$
20.5. The four-square theorem
20.6. Quaternions
20.7. Preliminary theorems about integral quaternions
20.8. The highest common right-hand divisor of two quaternions
20.9. Prime quaternions and the proof of Theorem $370$
20.10. The values of $\map g 2$ and $\map G 2$
20.11. Lemma for the third proof of Theorem $369$
20.12. Third proof of Theorem $369$: the number of representations
20.13. Representations by a larger number of squares
$\text {XXI}$. REPRESENTATION BY CUBES AND HIGHER POWERS
21.2. Cubes: the existence of $\map G 3$ and $\map g 3$
21.3. A bound for $\map g 3$
21.4. Higher powers
21.5. A lower bound for $\map g k$
21.6. Lower bounds for $\map G k$
21.7. Sums affected with signs: the number $\map v k$
21.8. Upper bounds for $\map v k$
21.9. The problem of Prouhet and Tarry: the number $\map P {k, j}$
21.10. Evaluation of $\map P {k, j}$ for particular $k$ and $j$
21.11. Further problems of Diophantine analysis
$\text {XXII}$. THE SERIES OF PRIMES (3)
22.1. The functions $\map \vartheta x$ and $\map \phi x$
22.2. Proof that $\map \vartheta x$ and $\map \phi x$ are of order $x$
22.3. Bertrand's postulate and a 'formula' for primes
22.4. Proof of Theorems $7$ and $9$
22.5. Two formal transformations
22.6. An important sum
22.7. The sum $\sum p^{-1}$ and the product $\prod \paren {1 - p^{-1} }$
22.8. Mertens's theorem
22.9. Proof of Theorems $323$ and $328$
22.10. The number of prime factors of $n$
22.11. The normal order of $\map \omega n$ and $\map \Omega n$
22.12. A note on round numbers
22.13. The normal order of $\map d n$
22.14. Selberg's theorem
22.15. The functions $\map R x$ and $\map V \xi$
22.16. Completion of the proof of theorems $434$, $6$ and $8$
22.17. Proof of Theorem $335$
22.18. Products of $k$ prime factors
22.19. Primes in an interval
22.20. A conjecture about the distribution of prime pairs $p$, $p + 2$
$\text {XXIII}$. KRONECKER'S THEOREM
23.1. Kronecker's theorem in one dimension
23.2. Proofs of the one-dimensional theorem
23.3. The problem of the reflected ray
23.4. Statement of the general theorem
23.5. The two forms of the theorem
23.6. An illustration
23.7. Lettenmeyer's proof of the theorem
23.8. Estermann's proof of the theorem
23.9. Bohr's proof of the theorem
23.10. Uniform distribution
$\text {XXIV}$. GEOMETRY OF NUMBERS
24.1. Introduction and restatement of the fundamental theorem
24.2. Simple applications
24.3. Arithmetical proof of Theorem 448
24.4. Best possible inequalities
24.5. The best possible inequality for $\xi^2 + \eta^2$
24.6. The best possible inequality for $\size {\xi \eta}$
24.7. A theorem concerning non-homogeneous forms
24.8. Arithmetical proof of Theorem $455$
24.9. Tchebotaref's theorem
24.10. A converse of Minkowski's Theorem $446$
APPENDIX
l. Another formula for $p_n$
2. A generalisation of Theorem $22$
3. Unsolved problems concerning primes
A LIST OF BOOKS
INDEX OF SPECIAL SYMBOLS AND WORDS
INDEX OF NAMES

Next