Elementary number theory

Cover

S Title

Elementary Number Theory

Copyright © 1994 by Waveland Press, Inc.
     Reissued 2002 by Waveland Press
     ISBN 978-1-57766-224-2

Preface

Preface to the Student

Contents

Introduction

1  Divisibility and Factorization
     1.1 Divisibility
          Exercise Set 1.1
     1.2 Prime Numbers
          Exercise Set 1.2
     1.3 Greatest Common Divisors
          Exercise Set 1.3
     1.4 The Euclidean Algorithm
          Exercise Set 1.4
     1.5 The Fundamental Theorem of Arithmetic
          Exercise Set 1.5
     1.6 Concluding Remarks
     Student Projects

2  Congruences
     2.1 Congruences
          Exercise Set 2.1
     2.2 Linear Congruences in One Variable
          Exercise Set 2.2
     2.3 The Chinese Remainder Theorem
          Exercise Set 2 .3
     2.4 Wilson\'s Theorem
          Exercise Set 2.4
     2.5 Fermat\'s Little Theorem; Pseudoprime Numbers
          Exercise Set 2 .5
     2.6 Euler\'s Theorem
          Exercise Set 2.6
     2.7 Concluding Remarks
     Student Projects

3  Arithmetic Functions
     3.1 Arithmetic Functions; Multiplicativity
          Exerdse Set 3.1
     3.2 The Euler Phi-Function
          Exercise Set 3.2
     3.3 The Number of Positive Divisors Function
          Exercise Set 3.3
     3.4 The Sum of Positive Divisors Function
          Exercise Set 3.4
     3.5 Perfect Numbers
          Exercise Set 3.5
     3.6 The Mobius Inversion Formula
          Exercise Set 3.6
     3.7 Concluding Remarks
     Student Projects

4  Quadratic Residues
     4.1 Quadratic Residues
          Exercise Set 4.1
     4.2 The Legendre Symbol
          Exercise Set 4.2
     4.3 The Law of Quadratic Reciprocity
          Exercise Set 4.3
     4.4 Concluding Remarks
     Student Projects

5  Primitive Roots
     5.1 The Order of an Integer; Primitive Roots
          Exercise Set 5.1
     5.2 Primitive Roots for Prime Numbers
          Exercise Set 5.2
     5.3 The Primitive Root Theorem
          Exercise Set 5.3
     5.4 Index Arithmetic; nth Power Residues
          Exercise Set 5.4
     5.5 Concluding Remarks
     Student Projects

6  Diophantine Equations
     6.1 Linear Diophantine Equations
          Exercise Set 6.1
     6.2 Nonlinear Diophantine Equations; a Congruence Method
          Exercise Set 6.2
     6.3 Pythagorean Triples
          Exercise Set 6.3
     6.4 Fermat\'s Last Theorem
          Exercise Set 6.4
     6.5 Representation of an Integer as a Sum of Squares
          Exercise Set 6.5
     6.6 Concluding Remarks
     Student Projects

7  Continued Fractions
     7.1 Rational and Irrational Numbers
          Exercise Set 7.1
     7.2 Finite Continued Fractions
          Exercise Set 7.2
     7.3 Convergents
          Exercise Set 7.3
     7.4 Infinite Continued Fractions
          Exercise Set 7.4
     7.5 Eventually Periodic Continued Fractions
          Exercise Set 7.5
     7.6 Periodic Continued Fractions
          Exercise Set 7.6
     7.7 Concluding Remarks
     Student Projects

8  A Few Applications
     8.1 A Recreational Application
          Exercise Set 8.1
     8.2 Cryptography; The RSA Encryption System
          Exercise Set 8.2
     8.3 Primality Testing
          Exercise Set 8.3
     8.4 Pell\' s Equation
          Exercise Set 8 .4
     8.5 Concluding Remarks
     Student Projects

Appendices
     A  Mathematical Induction
          A.1 The First Principle of Mathematical Induction
          A.2 The Second Principle of Mathematical Induction
          Exercise Set A
     B  Equivalence Relations
          B.1 Relations
          B.2 Equivalence Relations
          B.3 Partitions
          Exercise Set B
     C  Abstract Algebra
          C.1 Rings and Fields
          C.2 Groups
          Exercise Set C
     D  The Binomial Theorem
          D.1 The Binomial Theorem
          Exercise Set D
     E  Tables
          Table 1 Prime Numbers
          Table 2 Arithmetic Functions
          Table3 Primitive Roots/Prime Numbers
          Table 4 Continued Fractions

Hints and Answers to Selected Exercises
     Exercise Sets 1.1, 1.2
     Exercise Sets 1.3, 1.4, 1.5
     Exercise. Sets 2.1, 2.2
     Exercise Sets 2.3, 2.4, 2.5, 2.6
     Exercise Sets 3.1, 3.2
     Exercise Sets 3.3. 3.4. 3.5
     Exercise Sets 3.6
     Exercise Sets 4.1. 4.2
     Exercise Set 4.3
     Exercise Sets 5.1, 5.2, 5.3
     Exercise Set 5.4
     Exercise Sets 6.1, 6.2, 6.3
     Exercise Sets 6.4, 6.5
     Exercise Sets 7.1, 7.2
     Exercise Sets 7.3, 7.4, 7.5, 7.6
     Exercise Set 8.2
     Exercise Sets 8.3, 8.4

Bibliography

Index

Back Cover