From Great Discoveries in Number Theory to Applications

Description

This book provides an overview of many interesting properties of natural numbers, demonstrating their applications in areas such as cryptography, geometry, astronomy, mechanics, computer science, and recreational mathematics. In particular, it presents the main ideas of error-detecting and error-correcting codes, digital signatures, hashing functions, generators of pseudorandom numbers, and the RSA method based on large prime numbers. A diverse array of topics is covered, from the properties and applications of prime numbers, some surprising connections between number theory and graph theory, pseudoprimes, Fibonacci and Lucas numbers, and the construction of Magic and Latin squares, to the mathematics behind Prague’s astronomical clock. Introducing a general mathematical audience to some of the basic ideas and algebraic methods connected with various types of natural numbers, the book will provide invaluable reading for amateurs and professionals alike. Preface Contents Glossary of Symbols 1 Divisibility and Congruence 1.1 Introduction 1.2 Natural Numbers 1.3 Simple Criteria of Divisibility 1.4 The Least Common Multiple and the Greatest Common Divisor 1.5 Coprime Numbers 1.6 Euclidean Algorithm 1.7 Linear Diophantine Equations 1.8 Congruence 1.9 The Chinese Remainder Theorem 1.10 Dirichlet's Pigeonhole Principle 2 Prime and Composite Numbers 2.1 The Fundamental Theorem of Arithmetic 2.2 Euclid's Theorem on the Infinitude of Primes 2.3 Pythagorean Triples 2.4 Fermat's Method of Infinite Descent 2.5 Elliptic Curves 2.6 Fermat's Last Theorem 2.7 Fermat's Little Theorem 2.8 Euler–Fermat Theorem 2.9 Carmichael's Theorem 2.10 Legendre and Jacobi Symbol 2.11 Prime Factorization 3 Properties of Prime Numbers 3.1 Criteria for Primality 3.2 Wilson's Theorem 3.3 Dirichlet's Theorem 3.4 Fermat's Christmas Theorem 3.5 Polynomials Generating Primes 3.6 Riemann Hypothesis 3.7 Further Properties of Primes 4 Special Types of Primes 4.1 Mersenne Primes 4.2 Fermat Primes 4.3 Wieferich Primes 4.4 Elite Primes 4.5 Regular and Irregular Primes 4.6 Sophie Germain Primes 4.7 Euclidean Primes 4.8 Factorial Primes 4.9 Palindromic Primes 4.10 Cyclic and Permutation Primes 4.11 Further Types of Primes 4.12 Gaussian Primes 4.13 Eisenstein Primes 5 On a Connection of Number Theory with Graph Theory 5.1 Definitions and Notations 5.2 Structure of Iteration Digraphs 5.3 Application of the Carmichael Lambda Function 5.4 Application of the Euler Totient Function 5.5 Generalized Power Digraphs 6 Pseudoprimes 6.1 What Is a Pseudoprime? 6.2 Historical Notes 6.3 Density and Distribution of Pseudoprimes 6.4 Carmichael Numbers 6.5 Mersenne and Fermat Pseudoprimes 6.6 Further Types of Pseudoprimes 7 Fibonacci and Lucas Numbers 7.1 Fibonacci Numbers 7.2 Fibonacci Numbers and The Mandelbrot Set 7.3 Golden Section and Lucas Numbers 7.4 Equalities Containing Fibonacci Numbers 7.5 The Most Beautiful Theorems on Fibonacci and Lucas Numbers 7.6 Primes in Fibonacci and Lucas Sequences 7.7 Prime Factors of the Fibonacci Numbers 7.8 Properties of Digits of Fibonacci and Lucas Numbers 7.9 Further Properties of the Fibonacci Numbers 7.10 Diophantine Equations 7.11 A Trick with the Number 11 7.12 Generalizations of Fibonacci and Lucas Numbers 7.13 Analogue of Fermat's Little Theorem 7.14 Defective Fibonacci Sequence Modulo m 7.15 A Theorem on Fibonacci Numbers with Odd Index 7.16 Fibonacci Numbers Divisible by Their Index 8 Further Special Types of Integers 8.1 Polygonal Numbers 8.2 Perfect Numbers 8.3 Deficient and Abundant Numbers 8.4 Amicable Numbers 8.5 Cunningham Numbers 8.6 Cullen Numbers 8.7 Other Special Types of Integers 9 Magic and Latin Squares 9.1 Magic Squares 9.2 The Existence of Prime Number Magic Squares 9.3 Further Prime Number Magic Squares 9.4 Construction of 3times3times3 Prime Number Magic Cube 9.5 Latin Squares 9.6 Sudoku 10 The Mathematics Behind Prague's Horologe 10.1 Prague Clock Sequence 10.2 Connection with Triangular Numbers and Periodic Sequences 10.3 Necessary and Sufficient Condition for the Existence of a Šindel Sequence 10.4 Construction of the Primitive Šindel Sequence 10.5 Which Šindel Sequence Is the Most Beautiful? 10.6 Peculiar Šindel Sequences 10.7 Astronomical Dial 10.8 What Mathematics Is Hidden Behind the Main Clock? 11 Application of Primes 11.1 The Prime 11 in Coding 11.2 Encryption of Secret Messages by Large Prime Numbers 11.3 Digital Signature 11.4 Hashing Functions 11.5 Generators of Pseudorandom Numbers 11.6 A Message to Extraterrestrial Civilizations 11.7 Further Applications of Primes 12 Further Applications of Number Theory 12.1 Error-Correcting Codes 12.2 Coding By a Symmetric Key 12.3 Kepler's Semiregular Tilings 12.4 Platonic Solids 12.5 Tetrahedral Space-Fillers 12.6 Tricks with Numbers 12.7 Application of Congruences 12.8 Paradoxes in Numerical Computations 13 Tables Appendix References Subject Index Index Author Index Author Index