Introduction to Number Theory

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. © 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.

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 Möbius Inversion Formula.- 6.4 The Möbius 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 $$sumlimits_{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 |?|.