Mersenne Numbers and Fermat Numbers

Contents
Notations
Preface
1. Preliminaries
	1.1 Divisibility of integers
		Division algorithm
		Divisibility
		Prime and composite numbers
		Greastest common divisor and least common multiple
		Euclidean Algorithm
		Coprime numbers
		Exercises
	1.2 Modular arithmetics
		Congruence relation
		Congruence classes
		Exercises
	1.3 Arithmetic functions
		Examples of arithmetic functions
		Multiplicative functions
		Euler’s totient function
		Fermat’s little theorem and Euler’s theorem
		Exercises
	1.4 Solution of congruences
		Linear congruences
		Chinese remainder theorem
		Congruences of order m
		Exercises
	1.5 Quadratic residues, Legendre symbol and Jacobi symbol
		Legendre symbol
		Jacobi symbol
		Exercises
	1.6 Multiplicative orders, primitive roots and indexes
		Multiplicative order
		Primitive roots modulo n
		Indexes
		Exercises
	1.7 Continued fractions
		Exercises
	Chapter 1: References
2. Prime numbers
	2.1 History of the question
	2.2 Elementary properties of prime numbers
		Prime and composite numbers
		Infiniteness of the set of prime numbers
		Fundamental theorem of Arithmetics
		Exercises
	2.3 How to recognize whether a natural number is a prime?
		Sieve of Eratosthenes
		Simplest primality tests
		Fermat primaliry test; Poulet and Carmichael numbers
		Solovay-Strassen primality test
		Miller-Rabin primality test
		Criterions of prime numbers
		Exercises
	2.4 Formulas of primes
		Prime-generating polynomials
		Prime formulas of the first kind
		Primes formulas of the second kind
		Prime formulas of the third kind
		Formulas of primes and Fermat and Mersenne numbers
		Exercises
	2.5 Prime numbers in the family of special numbers
		Fibonacci and Lucas primes
		Prime numbers in Pascal’s triangle
		Catalan primes
		Cullen and Woodall primes
		Bernoulli numbers and Staudt primes
		Motzkin primes
		Palindromic and permutable primes
		Exercises
	2.6 Open problems
		Twin primes conjecture
		Prime gaps conjectures
		Goldbach’s conjecture
		Primes in some sequences
		Riemann hypothesis
		Landau’s problems
		Exercises
	Chapter 2: References
3. Mersenne numbers
	3.1 History of the question
	3.2 Elementary properties of Mersenne numbers
		Elementary conditions of primality of Mersenne numbers
		Last decimal digits of Mersenne numbers
		Recurrent relations for Mersenne numbers
		Divisibility properties of Mersenne numbers
		Other elemantary properties of Mersenne numbers
		Exercises
	3.3 Mersenne primes: Prime divisors of Mersenne numbers
		Properties of prime divisors of Mersenne numbers
		Mersenne numbers and Sophie Germain primes
		Exercises
	3.4 Mersenne primes: Lucas-Lehmer test
		History of the question
		Proof of the theorem
		Practical algorithms of computation
		Exercises
	3.5 Mersenne numbers in the family of special numbers
		Mersenne primes and perfect numbers
		Mersenne numbers and figurate numbers
		Mersenne numbers and Pascal’s triangle
		Double Mersenne numbers
		Mersenne numbers, Carol numbers and Kynéa numbers
		Generalized Mersenne numbers
		Exercises
	3.6 Open problems
		Infiniteness of the set of Mersenne primes
		Lenstra-Pomerance-Wagstaff and Gillies’ conjectures
		New Mersenne conjecture
		Other open questions
		Exercises
	Chapter 3: References
4. Fermat numbers
	4.1 History of the question
	4.2 Elementary properties of Fermat numbers
		Elementary conditions of primality of Fermat numbers
		Last decimal digits of Fermat numbers
		Recurrent relations for Fermat numbers
		Divisibility properties of Fermat numbers
		Composite relatives of Fermat numbers
		Additive properties of Fermat numbers
		Other elementary properties of Fermat numbers
		Exercises
	4.3 Fermat primes: Prime divisors of Fermat numbers
		Properties of prime divisors of Fermat numbers
		History of the search of prime divisors of Fermat numbers
		Primality of numbers k · 2m + 1
		Exercises
	4.4 Fermat primes: P´epin’s test
		Proof of the theorem
		Practical algorithms of calculation
		Exercises
	4.5 Fermat numbers in the family of special numbers
		Fermat numbers and perfect numbers
		Fermat numbers and Pascal’s triangle
		Generalized Fermat numbers
		Exercises
	4.6 Open problems
		Finiteness of the set of Fermat primes
		Other open questions
		Exercises
	Chapter 4: References
5. Modern Applications
	5.1 On place of prime numbers in Mathematics
		Distribution of prime numbers
		Prime number theorem
		Exercises
	5.2 Problems in Number Theory, connected with Mersenne numbers
		Mersenne numbers and perfect numbers: history of the question
		Proof of the Euclid–Euler theorem
		Properties of perfect numbers
		Generalizations of perfect numbers
		Exercises
	5.3 Problems in Number Theory, connected with Fermat numbers
		Constructible polygons: history of the question
		Constructible polygons and constructible numbers
		Other concepts of constructibility
		Sketch of a proof of the Gauss–Wantzel theorem
		Exercises
	5.4 Prime numbers records and Mersenne numbers
		The PrimePages: Prime number research and record
		Mersenne primes and GIMPS
		Exercises
	5.5 Mersenne and Fermat numbers in Cryptography
		Public-key Cryptography and large primes
		(N − 1)-based primaliy tests
		(N + 1)-based primality tests
		Factorization of composite Mersenne numbers
		Pseudorandom Number Generation and Fermat numbers
		Exercises
	5.6 Open problems
		P versus NP problem
		Can integer factorization be done in polynomial time on a classical (non-quantum) computer?
		Is Public-key Cryptography possible?
		Can the discrete logarithm be computed in polynomial time?
		Exercises
	Chapter 5: References
6. Zoo of Numbers
7. Mini Dictionary
8. Exercises
	Problems, connected with Mersenne numbers
	Problems, connected with Fermat numbers
	Other problems
	Solutions: Problems, connected with Mersenne numbers
	Solutions: Problems, connected with Fermat numbers
	Solutions: Other problems
Bibliography
Index