.

0 (hodnocen0 x )

(1) Půjčeno:1x 

BK

New York : Springer, c2003

xviii, 287 s.

ISBN 0-387-95320-5 (váz.)

Undergraduate texts in mathematics

Přeloženo z maďarštiny

Obsahuje předmluvy, rejstřík, údaje o autorech a jejich fotografie

Bibliografie: s. 275-291

Čísla - teorie čísel - učebnice vysokošk.

000110275

Contents // Note: Chapters are divided into sections, and groupe of sections form unified topics; this is indicated in the table of contents by indentation. Thus, for example, in Chapter 1, Sections 1 through 3 form a topic, as do Sections 4 and 5. // Preface to the Second Edition...v // Preface to the First Edition...vii // Preface to the English TYanslation...ix // Facts Used Without Proof in the Book ... xvii // Chapter 1. Divisibility, the Fundamental Theorem of Number Theory .. 1 // 1. Perfect numbers, amicable numbers. 2. Division with remainder. 1 // (Exercises 1-11.) 3. The four number theorem. (Exercises 13- // W.) // 4. Divisibility properties. (Exercise 15.) 5. Further divisibility prop- 7 // crties. (Exercises 16-18.) // 6. Prime and composite numbers, existence of prime divisors. The 10 // sequence of primes is infinite. (Exercises 19-20.) 7. Decomposition as a product of prime factors. (Exercises 21-23.) 8. Euclid’s lemma. (Exercises 24-25.) 9. The prime property. // 10. The uniqueness of decomposition into prime factors (fundamen- 13 // tal theorem). The generalization of the four number theorem. // 11. The proof of the generalization. 12. History of the fundamental theorem. (Exercises 26-33.) 13. Canonical decomposition. // 14. The divisors, multiples, and number of divisors of an integer. (Exercises 34-35.) 15. Common divisors of numbers, the distinguished common divisor. 16. Common multiples, the distinguished common multiple. (Exercises 36-38.) 17. Relatively

prime numbers and pairwise relatively prime numbers. 18. The irrationality of the *th root. 19. The canonical decomposition of factorials. 20. Canonical decomposition of binomial coefficients, their prime power divisors. (Exercises 39-44.) // xii Contents // 21. Pythagorean triples. 22. Squares of odd integers. 23- 25 // 24. Parametrization of Pythagorean triples, primitive triples. (Exercises 45-49.) 25. The divisors of the sum of two squares. (Exercises 50-53.) // 26. Two properties of the distinguished common divisor (without the 30 use of the fundamental theorem). 27. The Euclidean algorithm. (Exercises 54-57.) 28. Numbers with the prime property. (Exercise 58.) A new proof of the fundamental theorem. (Exercises 59-60.) 29. Solubility of first-order Diophantine equations. // 30. All solutions of first-order Diophantine equations. (Exercises 61-65.) // Chapter 2. Congruences... 39 // 1. The concept of congruence. 2. Fundamental properties. 3. Rules 39 for divisibility. 4. Residue classes, operations with residue classes. // 5. The splitting of a residue class into residue classes for a multiple of the original modulus. 6. Complete residue system. (Exercises 1-6.) // 7. Disjoint residue systems. 8. Covering residue systems. (Exercises 45 7—10.) 9*—10. The sum of the reciprocals of the moduli. // 11. Solubility of first-order congruences. (Exercises 11-13.) 12. A 49 necessary and sufficient condition for the solution. 13. Relation with first-order Diophantine equations. 14.

Simultaneous systems of congruences, a survey of solubility. 15. How to determine one solution (in the case of relatively prime moduli). 16. The Chinese remainder theorem. 17. The general case. (Exercises 14-18.) // 18. Improving the computational speed using parallel processing. // 19. “Reclusive primes.” (Dirichlet’s theorem on arithmetic progressions.) (Exercises 19—20.) // 20. Reduced residue systems, Euler’s ( -function. 21. A characteri- 58 zation of the function. 22. A characterization of reduced residue systems. (Exercise 21.) 23. An application: the Euler-Fermat theorem. 24. Fermat’s theorem. 25. An application to the solution of first-order congruences. 26. A geometric proof of Fermat’s theorem. 27. Cryptography. 28. A number-theoretic code. // 29. The code can be published. 30. Verifying the identity of the sender. // 31. The order of an element, modulo m. 32. Factoring out a root of a 64 polynomial, modulo m. 33. The number of roots for a prime modulus. 34. Wilson’s theorem. 35. Solubility of c2 = -1 (mod p). (Exercises 22-26.) 36. The number of roots of xk - 1, modulo m. (Exercises 27-28.) 37. Properties of the order of an element. // 38. The distribution of the order of elements for a prime modulus, primitive roots, index. (Exercises 29-31.) 39. The Euler function is multiplicative. // Contents xiii // 40. Second degree congruences, quadratic residues, quadratic charac- 73 ter of a product. 41. The Legendre symbol. 42. The Euler lemma. // 43. An example;

notes on how to arrive at a solution. 44. The Gauss lemma. 45-47. Examples to determine those primes for which a number can be a quadratic residue. 48-50. Two general theorems to the previous question. 51. The reciprocity theorem. (Exercises 32-38.) // Chapter 3. Rational and Irrational Numbers. Approximation of Numbers by Rational Numbers (Diophantine Approximation) ...85 // 1. The goal of the chapter. 2. Rational numbers in decimal notation. 85 // 3. The meaning of infinite decimals. 4. The common fractional representation of periodic decimals (Exercises 1—3.) 5—6. Aperiodic decimals. (Exercise 4.) 7. Incommensurable distances, the irrationality of \\Jm? -f 1. 8. A modification to the proof. (Exercises 5-6.) 9. An arithmetic proof of the irrationality of \\/2. // 10. A geometric proof that \\/m either is an integer or is irrational. // 11. An arithmetic variation of the proof. // 12. The irrationality of tan(7r/m); a formula for tan та. The case 95 for m odd. 13. The case for m even. 14*. The irrationality of e. // 15. Transcendental numbers, results, problems. (Exercises 7-13.) // 16. Approximating real numbers well by rational numbers; the exis- 100 tence of infinitely many close rational numbers. The sequence of points of a circle arising by measuring off arc lengths. 17. Finding approximating fractions. (Exercises 14-15.) 18. Liouville’s theorem; Thue equations. 19. Roth’s theorem and limits to approximation. 20-22. Related Diophantine equations, results, problems.

// Chapter 4. Geometric Methods in Number Theory ... 109 // 1. A geometrical-combinatorial proof of Wilson’s theorem. 2. Re- 109 // lated problems. (Exercises 1—4.) 3. Parallelogram lattices, lattice points. 4. Lattice coordinates. Two fundamental properties // 5. Further lattice properties. 6. Regular lattice polygons. 7. Simultaneous regular lattice polygons. // 8. Lattices arising from parallelograms. Parallelogram lattices that 119 give rise to a given point lattice. // 9. Determining the area of lattice polygons by the number of lattice 120 points. Subpolygons of lattice polygons. 10. Proving the theorem // for lattice triangles. 11. The extension to arbitrary lattice polygons. 12. The existence of simple, interior diagonals in lattice polygons. (Exercises 5-19.) // 13. Lattice points close to lines. 14. Sharpening of the result for lat- 127 tice rays. 15. An application. (Exercises 20-21.) // xiv Contents // 16. Minkowski’s theorem about convex regions. 17. The proof of the 130 theorem for regions of area greater than 4<f. 18. The case of equality. 19. The necessity of the hypotheses. 20. A related problem. // 21. Three applications. 22-23. The sharpness of the theorem; the existence of infinitely many lattice points satisfying the hypotheses. 24. An application to the decomposition of a prime number as the sum of two squares. (Exercises 22-27.) // 25. The sharpness of the hypotheses of the theorem. 26-27. The 139 sharpness of the theorem relating to disks. 28. Admissible

lattices between the pair of hyperbolas. 29. Proof of the theorem. 30. The bound cannot be improved. 31. An application to Diophantine approximation. 32. A possible improvement of the theorem by decreasing the lattice circle. // 33. Homogeneous and inhomogeneous lattices. The existence of di- 150 vided cells. 34. The theorem rediscovered; the 3-dimensional case. // 35. Obtaining all divided cells. 36. An application of the theorem. // 37. An arithmetic conclusion to the proof. (Exercises 28-31.) // Chapter 5. Properties of Prime Numbers ... 157 // 1. The role of prime numbers, their distribution. 2. The differences 157 among primes: results, problems. (Exercises 1-2.) 3. Sequences of pairwise relatively prime elements. 4. An observation about primes not greater than x. (Exercises 3-4.) 5. A lower bound for n(x). 6. The sum of the reciprocals of the elements of a sequence. // 7. An indirect proof that the series of reciprocals of primes diverges. (Exercises 5—7.) 8-9*. A lower bound for the sum of the sequence of reciprocals of primes. // 10. The order of magnitude of ir(x), a lower bound. 11. An up- 166 per bound on the product of the primes less than x. 12. Using the result to bound 7г(х) from below. Sequences of density 0. // 13. The order of magnitude of the number of prime powers not greater than x. (Exercises 8-12.) 14. Primes between n and 2n. // 15. A sharpening, the Sylvester-Schur theorem. (Exercises 13- // 16.) 16. A common thread to the proofs. The asymptotic value

of 7г(х). The Riemann zeta function. // 17-18. Some primes in arithmetic progressions. 19. Reduction to the 177 proof of the existence of a prime. 20. The special case of a satisfying infinite arithmetic sequence. 21. The relation with primitive roots. 22. The generalized scope of validity of the method. // Contents // Chapter 6. Sequences of Integers ... // 1. Some examples from the preceding chapters. 2. Pairs of numbers having a short Euclidean algorithm, Fibonacci and Fibonacci-type numbers. 3. Divisors of Fibonacci numbers. 4. Observations. (Exercises 1-8.) 5. Lower, upper, and asymptotic density of the sequence. (Exercises 9-10.) // 6. Sequences not containing the difference of two elements. 7. The partition of all integers up to a given bound into such sequences. // 8. Fermat’s last theorem in the congruence case. 9. Fermat’s last theorem. 10. Remarks regarding the tests in Section 7. // 11. The number of prime divisors of the sum of a given set of numbers. A lemma. 12. The proof of the theorem. Results relating to the sum of elements from two sequences. 13. The number of elements in a sequence not containing multiples of its elements. 14. Proof by induction. 15. Proof by examining parity. 16-17. Results for infinite sequences. (Exercise 11.) // 18. The number of elements in sequences not containing arithmetic progressions of length к (гк(п)), some results about гз(п). // 19. Some small values calculated. (Exercise 12.) 20. Some related results for arithmetic

progressions. // 21. Sequences with all pairwise two-element sums distinct (Sidon sequences). Upper bound on the number of elements. 22-23. Further improvement of the bound. 24-25. Sharpness of the bound. (Exercises 13-23.) // Chapter 7. Diophantine Problems ... // 1. Parametric representation of “Pythagorean n-tuples.” 2. The representation is essentially unique. (Exercises 1-3.) 3. Problems regarding the representation of integers as sums of squares. // 4. Numbers which are the sum of squares of two integers. 5. The sufficiency of the hypothesis. 6. Numbers that cannot be written as the sum of three integers. 7. Representation as the sum of four squares. Reduction to the case of primes. 8-9. Proof of the special case. 10-11. Proof of the lemmas. (Exercises 4—6.) 12. Further results and exercises. // 13. Representation as the sum of fourth powers. 14. Infinitely many numbers that are not the sum of 15 fourth powers. 15. The functions g(k) and G(k) relating to the number of terms in a kth-power representation, known results, problems. (Exercises 7-9.) // XV // 181 // 181 // 186 // 190 // 196 // 199 // 205 // 205 // 208 // 215 // xvi Contents // 16. Representations as sums of A:th powers with mixed signs, squares. 218 // 17. Cubics. 18. The number of terms is bounded in the case of arbitrary powers. (Exercises 10—11.) // 19. When can (p— 1)! +1 be a power of p? 20. Related results, prob- 221 lems. 21*-22*. Binomial coefficients as perfect powers, a lower bound. 23*-24*.

Upper bound, completion of the proof. 25. Further results, problems. (Exercises 12-26.) // Chapter 8. Arithmetic Functions ... 231 // 1-2. Arithmetic functions, a new method of calculating the value 231 of p. 3. Probabilistic background for the proof. (Exercises 1- // 5.) 4. The sum of the divisors (a(n)). 5. Representation of even perfect numbers. 6. Mersenne primes; a criterion for their pri-mality. 7. The function a is multiplicative. 8. A formula for a. (Exercises 6-13.) 9. Further examples of arithmetic functions, the determination of additive and multiplicative functions. (Exercises 14-17.) 10. Deficient and abundant numbers. 11*. A theorem about odd perfect numbers, a grouping of the prime divisors. 12*. A result arising from limits leads to a contradiction. // 13*. Extension of the theorem to primitive abundant numbers. // 14. Further results and problems. (Exercises 18-29.) // 15. Examples of the behavior of inequalities for number-theoretic 245 functions. (Exercise 30.) 16*. The rhapsodic behavior of the number of divisors. 17*-18*. Sequences of к consecutive integers with a small number of average divisors. 19. Possible fine tuning of the proof. 20. Further results, problems. 21*-22*. The range of the Euler function is bounded above. 23. Related results, problems. 24. A sequence arising from the iteration of tp. 25. Further results, problems. 26. “Narrow valleys” in the graph of r. 27. A lower bound for r(n). 28. An upper bound for r(n). // 29. The average value

of r(n). 30. Earlier results, the current situ- 262 // ation. 31. The average value of w and Q. 32. Average values of additional functions; r(n)’s most frequent values and determination of its average values. // 33. Only the logarithmic function is additive and monotone. 34. Im- 265 // provements, extending the tests. (Exercises 31-32.) // Hints to the More Difficult Exercises...269 // Bibliography...275 // Index // 283