to Number Theory Translated from the Chinese by Peter Shiu With 14 Figures Springer-Verlag Berlin Heidelberg New York 1982 HuaLooKeng Institute of Mathematics Academia Sinica Beijing The People's Republic of China PeterShlu Department of Mathematics University of Technology Loughborough Leicestershire LE 11 3 TU United Kingdom ISBN -13 : 978-3-642-68132-5 e-ISBN -13 : 978-3-642-68130-1 DOl: 10.1007/978-3-642-68130-1 Library of Congress Cataloging in Publication Data. Hua, Loo-Keng, 1910 -. Introduc- tion to number theory. Translation of: Shu lun tao yin. Bibliography: p. Includes index. 1. Numbers, Theory of. I. Title. QA241.H7513.5 12'.7.82-645. ISBN-13:978-3-642-68132-5 (U.S.). AACR2 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically those of translation, reprinting, reuse of illustra- tions, broadcasting, reproductiOli by photocopying machine or similar means, and storage in data banks. Under 54 of the German Copyright Law where copies are made for other than private use a fee is payable to "VerwertungsgeselIschaft Wort", Munich. (c) Springer-Verlag Berlin Heidelberg 1982 Softcover reprint of the hardcover 1st edition 1982 Typesetting: Buchdruckerei Dipl.-Ing. Schwarz' Erben KG, Zwettl. 214113140-5432 I 0 Preface to the English Edition The reasons for writing this book have already been given in the preface to the original edition and it suffices to append a few more points.

Table of Contents:
1. The Factorization of Integers.- 1.1 Divisibility.- 1.2 Prime Numbers and Composite Numbers.- 1.3 Prime Numbers.- 1.4 Integral Modulus.- 1.5 The Fundamental Theorem of Arithmetic.- 1.6 The Greatest Common Factor and the Least Common Multiple.- 1.7 The Inclusion-Exclusion Principle.- 1.8 Linear Indeterminate Equations.- 1.9 Perfect Numbers.- 1.10 Mersenne Numbers and Fermat Numbers.- 1.11 The Prime Power in a Factorial.- 1.12 Integral Valued Polynomials.- 1.13 The Factorization of Polynomials.- Notes.- 2. Congruences.- 2.1 Definition.- 2.2 Fundamental Properties of Congruences.- 2.3 Reduced Residue System.- 2.4 The Divisibility of 2p-1-1 by p2.- 2.5 The Function ?(m).- 2.6 Congruences.- 2.7 The Chinese Remainder Theorem.- 2.8 Higher Degree Congruences.- 2.9 Higher Degree Congruences to a Prime Power Modulus.- 2.10 Wolstenholme's Theorem.- 3. Quadratic Residues.- 3.1 Definitions and Euler's Criterion.- 3.2 The Evaluation of Legendre's Symbol.- 3.3 The Law of Quadratic Reciprocity.- 3.4 Practical Methods for the Solutions.- 3.5 The Number of Roots of a Quadratic Congruence.- 3.6 Jacobi's Symbol.- 3.7 Two Terms Congruences.- 3.8 Primitive Roots and Indices.- 3.9 The Structure of a Reduced Residue System.- 4. Properties of Polynomials.- 4.1 The Division of Polynomials.- 4.2 The Unique Factorization Theorem.- 4.3 Congruences.- 4.4 Integer Coefficients Polynomials.- 4.5 Polynomial Congruences with a Prime Modulus.- 4.6 On Several Theorems Concerning Factorizations.- 4.7 Double Moduli Congruences.- 4.8 Generalization of Fermat's Theorem.- 4.9 Irreducible Polynomials mod p.- 4.10 Primitive Roots.- 4.11 Summary.- 5. The Distribution of Prime Numbers.- 5.1 Order of Infinity.- 5.2 The Logarithm Function.- 5.3 Introduction.- 5.4 The Number of Primes is Infinite.- 5.5 Almost All Integers are Composite.- 5.6 Chebyshev's Theorem.- 5.7 Bertrand's Postulate.- 5.8 Estimation of a Sum by an Integral.- 5.9 Consequences of Chebyshev's Theorem.- 5.10 The Number of Prime Factors of n.- 5.11 A Prime Representing Function.- 5.12 On Primes in an Arithmetic Progression.- Notes.- 6. Arithmetic Functions.- 6.1 Examples of Arithmetic Functions.- 6.2 Properties of Multiplicative Functions.- 6.3 The Mobius Inversion Formula.- 6.4 The Mobius Transformation.- 6.5 The Divisor Function.- 6.6 Two Theorems Related to Asymptotic Densities.- 6.7 The Representation of Integers as a Sum of Two Squares.- 6.8 The Methods of Partial Summation and Integration.- 6.9 The Circle Problem.- 6.10 Farey Sequence and Its Applications.- 6.11 Vinogradov's Method of Estimating Sums of Fractional Parts.- 6.12 Application of Vinogradov's Theorem to Lattice Point Problems.- 6.13 ?-results.- 6.14 Dirichlet Series.- 6.15 Lambert Series.- Notes.- 7. Trigonometric Sums and Characters.- 7.1 Representation of Residue Classes.- 7.2 Character Functions.- 7.3 Types of Characters.- 7.4 Character Sums.- 7.5 Gauss Sums.- 7.6 Character Sums and Trigonometric Sums.- 7.7 From Complete Sums to Incomplete Sums.- 7.8 Applications of the Character Sum $$\sum\limits_{x = 1}^p {\left( {\frac{{x^2 + ax + b}}{p}} \right)} $$.- 7.9 The Problem of the Distribution of Primitive Roots.- 7.10 Trigonometric Sums Involving Polynomials.- Notes.- 8. On Several Arithmetic Problems Associated with the Elliptic Modular Function.- 8.1 Introduction.- 8.2 The Partition of Integers.- 8.3 Jacobi's Identity.- 8.4 Methods of Representing Partitions.- 8.5 Graphical Method for Partitions.- 8.6 Estimates for p(n).- 8.7 The Problem of Sums of Squares.- 8.8 Density.- 8.9 A Summary of the Problem of Sums of Squares.- 9. The Prime Number Theorem.- 9.1 Introduction.- 9.2 The Riemann ?-Function.- 9.3 Several Lemmas.- 9.4 A Tauberian Theorem.- 9.5 The Prime Number Theorem.- 9.6 Selberg's Asymptotic Formula.- 9.7 Elementary Proof of the Prime Number Theorem.- 9.8 Dirichlet's Theorem.- Notes.- 10. Continued Fractions and Approximation Methods.- 10.1 Simple Continued Fractions.- 10.2 The Uniqueness of a Continued Fraction Expansion.- 10.3 The Best Approximation.- 10.4 Hurwitz's Theorem.- 10.5 The Equivalence of Real Numbers.- 10.6 Periodic Continued Fractions.- 10.7 Legendre's Criterion.- 10.8 Quadradic Indeterminate Equations.- 10.9 Pell's Equation.- 10.10 Chebyshev's Theorem and Khintchin's Theorem.- 10.11 Uniform Distributions and the Uniform Distribution of n? (mod 1).- 10.12 Criteria for Uniform Distributions.- 11. Indeterminate Equations.- 11.1 Introduction.- 11.2 Linear Indeterminate Equations.- 11.3 Quadratic Indeterminate Equations.- 11.4 The Solution to ax2 + bxy + cy2=k.- 11.5 Method of Solution.- 11.6 Generalization of Soon Go's Theorem.- 11.7 Fermat's Conjecture.- 11.8 Markoff's Equation.- 11.9 The Equation x3 + y3 + z3 + ?3=0.- 11.10 Rational Points on a Cubic Surface.- Notes.- 12. Binary Quadratic Forms.- 12.1 The Partitioning of Binary Quadratic Forms into Classes.- 12.2 The Finiteness of the Number of Classes.- 12.3 Kronecker's Symbol.- 12.4 The Number of Representations of an Integer by a Form.- 12.5 The Equivalence of Formsmod q.- 12.6 The Character System for a Quadratic Form and the Genus.- 12.7 The Convergence of the Series K(d).- 12.8 The Number of Lattice Points Inside a Hyperbola and an Ellipse.- 12.9 The Limiting Average.- 12.10 The Class Number: An Analytic Expression.- 12.11 The Fundamental Discriminants.- 12.12 The Class Number Formula.- 12.13 The Least Solution to Pell's Equation.- 12.14 Several Lemmas.- 12.15 Siegel's Theorem.- Notes.- 13. Unimodular Transformations.- 13.1 The Complex Plane.- 13.2 Properties of the Bilinear Transformation.- 13.3 Geometric Properties of the Bilinear Transformation.- 13.4 Real Transformations.- 13.5 Unimodular Transformations.- 13.6 The Fundamental Region.- 13.7 The Net of the Fundamental Region.- 13.8 The Structure of the Modular Group.- 13.9 Positive Definite Quadratic Forms.- 13.10 Indefinite Quadratic Forms.- 13.11 The Least Value of an Indefinite Quadratic Form.- 14. Integer Matrices and Their Applications.- 14.1 Introduction.- 14.2 The Product of Matrices.- 14.3 The Number of Generators for Modular Matrices.- 14.4 Left Association.- 14.5 Invariant Factors and Elementary Divisors.- 14.6 Applications.- 14.7 Matrix Factorizations and Standard Prime Matrices.- 14.8 The Greatest Common Factor and the Least Common Multiple.- 14.9 Linear Modules.- 15. p-adic Numbers.- 15.1 Introduction.- 15.2 The Definition of a Valuation.- 15.3 The Partitioning of Valuations into Classes.- 15.4 Archimedian Valuations.- 15.5 Non-Archimedian Valuations.- 15.6 The ?-Extension of the Rationals.- 15.7 The Completeness of the Extension.- 15.8 The Representation of p-adic Numbers.- 15.9 Application.- 16. Introduction to Algebraic Number Theory.- 16.1 Algebraic Numbers.- 16.2 Algebraic Number Fields.- 16.3 Basis.- 16.4 Integral Basis.- 16.5 Divisibility.- 16.6 Ideals.- 16.7 Unique Factorization Theorem for Ideals.- 16.8 Basis for Ideals.- 16.9 Congruent Relations.- 16.10 Prime Ideals.- 16.11 Units.- 16.12 Ideal Classes.- 16.13 Quadratic Fields and Quadratic Forms.- 16.14 Genus.- 16.15 Euclidean Fields and Simple Fields.- 16.16 Lucas's Criterion for the Determination of Mersenne Primes.- 16.17 Indeterminate Equations.- 16.18 Tables.- Notes.- 17. Algebraic Numbers and Transcendental Numbers.- 17.1 The Existence of Transcendental Numbers.- 17.2 Liouville's Theorem and Examples of Transcendental Numbers.- 17.3 Roth's Theorem on Rational Approximations to Algebraic Numbers.- 17.4 Application of Roth's Theorem.- 17.5 Application of Thue's Theorem.- 17.6 The Transcendence of e.- 17.7 The Transcendence of ?.- 17.8 Hilbert's Seventh Problem.- 17.9 Gelfond's Proof.- Notes.- 18. Waring's Problem and the Problem of Prouhet and Tarry.- 18.1 Introduction.- 18.2 Lower Bounds for g(k) and G(k).- 18.3 Cauchy's Theorem.- 18.4 Elementary Methods.- 18.5 The Easier Problem of Positive and Negative Signs.- 18.6 Equal Power Sums Problem.- 18.7 The Problem of Prouhet and Tarry.- 18.8 Continuation.- 19. Schnirelmann Density.- 19.1 The Definition of Density and its History.- 19.2 The Sum of Sets and its Density.- 19.3 The Goldbach-Schnirelmann Theorem.- 19.4 Selberg's Inequality.- 19.5 The Proof of the Goldbach-Schnirelmann Theorem.- 19.6 The Waring-Hiibert Theorem.- 19.7 The Proof of the Waring-Hiibert Theorem.- Notes.- 20. The Geometry of Numbers.- 20.1 The Two Dimensional Situation.- 20.2 The Fundamental Theorem of Minkowski.- 20.3 Linear Forms.- 20.4 Positive Definite Quadratic Forms.- 20.5 Products of Linear Forms.- 20.6 Method of Simultaneous Approximations.- 20.7 Minkowski's Inequality.- 20.8 The Average Value of the Product of Linear Forms.- 20.9 Tchebotaref's Theorem.- 20.10 Applications to Algebraic Number Theory.- 20.11 The Least Value for |?|.