Mersenne Numbers And Fermat Numbers (Selected Chapters Of Number Theory: Special Numbers Book 1)

Main subject categories: • Mersenne numbers • Fermat numbers • Number theoryThis book contains a complete detailed description of two classes of special numbers closely related to classical problems of the Theory of Primes. There is also extensive discussions of applied issues related to Cryptography. In Mathematics, a Mersenne number (named after Marin Mersenne, who studied them in the early 17-th century) is a number of the form Mn = 2n – 1 for positive integer n. In Mathematics, a Fermat number (named after Pierre de Fermat who first studied them) is a positive integer of the form Fn = 2i + 1, i = 2n, where n is a non-negative integer. Mersenne and Fermat numbers have many other interesting properties. Long and rich history, many arithmetic connections (with perfect numbers, with construction of regular polygons etc.), numerous modern applications, long list of open problems allow us to provide a broad perspective of the Theory of these two classes of special numbers, that can be useful and interesting for both professionals and the general audience. Contents 8 Notations 10 Preface 16 1. Preliminaries 22 1.1 Divisibility of integers 22 Division algorithm 22 Divisibility 22 Prime and composite numbers 23 Greastest common divisor and least common multiple 25 Euclidean Algorithm 26 Coprime numbers 27 Exercises 28 1.2 Modular arithmetics 29 Congruence relation 29 Congruence classes 30 Exercises 31 1.3 Arithmetic functions 32 Examples of arithmetic functions 32 Multiplicative functions 33 Euler’s totient function 34 Fermat’s little theorem and Euler’s theorem 35 Exercises 36 1.4 Solution of congruences 37 Linear congruences 37 Chinese remainder theorem 39 Congruences of order m 40 Exercises 45 1.5 Quadratic residues, Legendre symbol and Jacobi symbol 47 Legendre symbol 47 Jacobi symbol 48 Exercises 49 1.6 Multiplicative orders, primitive roots and indexes 50 Multiplicative order 50 Primitive roots modulo n 51 Indexes 52 Exercises 53 1.7 Continued fractions 54 Exercises 57 Chapter 1: References 58 2. Prime numbers 60 2.1 History of the question 60 2.2 Elementary properties of prime numbers 64 Prime and composite numbers 64 Infiniteness of the set of prime numbers 65 Fundamental theorem of Arithmetics 66 Exercises 67 2.3 How to recognize whether a natural number is a prime? 67 Sieve of Eratosthenes 68 Simplest primality tests 68 Fermat primaliry test; Poulet and Carmichael numbers 70 Solovay-Strassen primality test 72 Miller-Rabin primality test 74 Criterions of prime numbers 76 Exercises 82 2.4 Formulas of primes 83 Prime-generating polynomials 84 Prime formulas of the first kind 86 Primes formulas of the second kind 90 Prime formulas of the third kind 91 Formulas of primes and Fermat and Mersenne numbers 93 Exercises 94 2.5 Prime numbers in the family of special numbers 95 Fibonacci and Lucas primes 95 Prime numbers in Pascal’s triangle 96 Catalan primes 99 Cullen and Woodall primes 100 Bernoulli numbers and Staudt primes 103 Motzkin primes 105 Palindromic and permutable primes 105 Exercises 107 2.6 Open problems 108 Twin primes conjecture 108 Prime gaps conjectures 111 Goldbach’s conjecture 114 Primes in some sequences 116 Riemann hypothesis 117 Landau’s problems 119 Exercises 120 Chapter 2: References 121 3. Mersenne numbers 122 3.1 History of the question 122 3.2 Elementary properties of Mersenne numbers 130 Elementary conditions of primality of Mersenne numbers 131 Last decimal digits of Mersenne numbers 132 Recurrent relations for Mersenne numbers 132 Divisibility properties of Mersenne numbers 133 Other elemantary properties of Mersenne numbers 135 Exercises 138 3.3 Mersenne primes: Prime divisors of Mersenne numbers 139 Properties of prime divisors of Mersenne numbers 139 Mersenne numbers and Sophie Germain primes 143 Exercises 144 3.4 Mersenne primes: Lucas-Lehmer test 144 History of the question 144 Proof of the theorem 145 Practical algorithms of computation 148 Exercises 151 3.5 Mersenne numbers in the family of special numbers 152 Mersenne primes and perfect numbers 152 Mersenne numbers and figurate numbers 153 Mersenne numbers and Pascal’s triangle 154 Double Mersenne numbers 155 Mersenne numbers, Carol numbers and Kynéa numbers 156 Generalized Mersenne numbers 159 Exercises 161 3.6 Open problems 162 Infiniteness of the set of Mersenne primes 162 Lenstra-Pomerance-Wagstaff and Gillies’ conjectures 163 New Mersenne conjecture 165 Other open questions 166 Exercises 169 Chapter 3: References 169 4. Fermat numbers 170 4.1 History of the question 170 4.2 Elementary properties of Fermat numbers 177 Elementary conditions of primality of Fermat numbers 177 Last decimal digits of Fermat numbers 179 Recurrent relations for Fermat numbers 180 Divisibility properties of Fermat numbers 181 Composite relatives of Fermat numbers 182 Additive properties of Fermat numbers 184 Other elementary properties of Fermat numbers 187 Exercises 191 4.3 Fermat primes: Prime divisors of Fermat numbers 191 Properties of prime divisors of Fermat numbers 192 History of the search of prime divisors of Fermat numbers 193 Primality of numbers k · 2m + 1 195 Exercises 197 4.4 Fermat primes: P ́epin’s test 197 Proof of the theorem 198 Practical algorithms of calculation 199 Exercises 202 4.5 Fermat numbers in the family of special numbers 202 Fermat numbers and perfect numbers 202 Fermat numbers and Pascal’s triangle 206 Generalized Fermat numbers 207 Exercises 210 4.6 Open problems 211 Finiteness of the set of Fermat primes 211 Other open questions 213 Exercises 214 Chapter 4: References 215 5. Modern Applications 216 5.1 On place of prime numbers in Mathematics 216 Distribution of prime numbers 217 Prime number theorem 218 Exercises 222 5.2 Problems in Number Theory, connected with Mersenne numbers 223 Mersenne numbers and perfect numbers: history of the question 223 Proof of the Euclid–Euler theorem 225 Properties of perfect numbers 227 Generalizations of perfect numbers 230 Exercises 231 5.3 Problems in Number Theory, connected with Fermat numbers 232 Constructible polygons: history of the question 232 Constructible polygons and constructible numbers 233 Other concepts of constructibility 235 Sketch of a proof of the Gauss–Wantzel theorem 236 Exercises 239 5.4 Prime numbers records and Mersenne numbers 239 The PrimePages: Prime number research and record 240 Mersenne primes and GIMPS 241 Exercises 245 5.5 Mersenne and Fermat numbers in Cryptography 245 Public-key Cryptography and large primes 245 (N − 1)-based primaliy tests 250 (N + 1)-based primality tests 252 Factorization of composite Mersenne numbers 257 Pseudorandom Number Generation and Fermat numbers 259 Exercises 260 5.6 Open problems 261 P versus NP problem 261 Can integer factorization be done in polynomial time on a classical (non-quantum) computer? 263 Is Public-key Cryptography possible? 265 Can the discrete logarithm be computed in polynomial time? 266 Exercises 268 Chapter 5: References 269 6. Zoo of Numbers 270 7. Mini Dictionary 280 8. Exercises 288 Problems, connected with Mersenne numbers 288 Problems, connected with Fermat numbers 291 Other problems 295 Solutions: Problems, connected with Mersenne numbers 296 Solutions: Problems, connected with Fermat numbers 306 Solutions: Other problems 311 Bibliography 316 Index 324 "This book contains a complete detailed description of two classes of special numbers closely related to classical problems of the Theory of Primes. There is also extensive discussions of applied issues related to Cryptography. In Mathematics, a Mersenne number (named after Marin Mersenne, who studied them in the early 17-th century) is a number of the form Mn = 2n - 1 for positive integer n. In Mathematics, a Fermat number (named after Pierre de Fermat who first studied them) is a positive integer of the form Fn = 2k+ 1, k = 2n, where n is a non-negative integer. Mersenne and Fermat numbers have many other interesting properties. Long and rich history, many arithmetic connections (with perfect numbers, with construction of regular polygons etc.), numerous modern applications, long list of open problems allow us to provide a broad perspective of the Theory of these two classes of special numbers, that can be useful and interesting for both professionals and the general audience"-- Provided by publisher