Understanding Prime Numbers

• A prime number is a natural number greater than 1 that cannot be written as the product of two smaller natural numbers.
• Numbers greater than 1 that are not prime are called composite numbers.
• A prime number can only be divided evenly by 1 and itself.
• An equivalent definition of prime numbers: numbers with exactly two positive divisors (1 and itself).
• The number 1 is not considered a prime number.
• The first 25 prime numbers (less than 100) are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
• No even number greater than 2 is prime, since it can be expressed as 2 multiplied by another number.
• All prime numbers other than 2 are odd and called odd primes.
• Prime numbers larger than 5 end in 1, 3, 7, or 9 when written in decimal.
• The earliest study of prime numbers comes from ancient Greek mathematicians, who called them prōtos arithmòs.
• Euclid's Elements proves the infinitude of primes and the fundamental theorem of arithmetic.
• The Sieve of Eratosthenes is used to construct lists of primes.
• Around 1000 AD, Ibn al-Haytham (Alhazen) found Wilson's theorem, characterizing primes as numbers 'n' that evenly divide (n-1)! + 1.
• Ibn al-Banna' al-Marrakushi observed the sieve of Eratosthenes can be sped up by considering prime divisors up to the square root of the upper limit.
• Fibonacci's Liber Abaci (1202) describes trial division for primality testing, using divisors up to the square root.
• Pépin's test, Proth's theorem, the Lucas–Lehmer primality test, and the generalized Lucas primality test are primality tests restricted to specific number forms.
• The fundamental theorem of arithmetic states every integer larger than 1 can be written as a product of one or more primes.
• This prime factorization is unique, meaning any two factorizations of the same number have the same numbers of copies of the same primes.
• Primes are considered the "basic building blocks" of natural numbers.
• Euclid's lemma: If a prime number p divides a product ab, then p divides a or b (or both).
• Euclid's theorem proves the infinitude of prime numbers.
• Euclid's proof involves multiplying primes in a list and adding 1; the resulting number's prime factors cannot be in the original list.
• Numbers formed by adding one to the products of the smallest primes are called Euclid numbers.
• There is no known efficient formula for primes, or non-constant polynomial that takes only prime values.
• Wilson's theorem can be used to create a formula that generates the number 2 many times and all other primes exactly once.

Unsolved Conjectures Involving Primes

• Goldbach's conjecture: Every even integer greater than 2 can be written as a sum of two primes. (Verified up to 4 * 10^18 as of 2014).
• Vinogradov's theorem: Every sufficiently large odd integer can be written as a sum of three primes.
• Chen's theorem: Every sufficiently large even number can be expressed as the sum of a prime and a semiprime (product of two primes).
• Any even integer greater than 10 can be written as the sum of six primes.
• Twin Prime Conjecture: There are infinitely many twin primes (pairs differing by 2).
• Polignac's conjecture: For every positive integer k, there are infinitely many pairs of consecutive primes differing by 2k.
• Andrica's, Brocard's, Legendre's, and Oppermann's conjectures suggest the largest gaps between primes from 1 to n should be at most approximately the square root of n.
• Cramér conjecture sets the largest gap size at O((log n)^2).

Distribution of Primes

• Analytic number theory studies number theory using continuous functions, limits, and infinite series.
• Euler solved the Basel problem, finding the value of the infinite sum 1 + 1/4 + 1/9 + 1/16 + ... to be π^2 / 6.
• The reciprocal of this number, 6 / π^2, is the limiting probability that two random numbers are relatively prime.
• The prime number theorem describes the distribution of primes, estimating how many primes are smaller than a given threshold, but no efficient formula for the nth prime is known.
• Dirichlet's theorem on arithmetic progressions states linear polynomials with relatively prime integers a and b take infinitely many prime values.
• Euler showed that for any real number x, there exists a prime p for which the sum of the reciprocals of primes up to p is greater than x, indicating there are infinitely many primes.
• Mertens' second theorem describes the growth rate of this sum.
• Brun's theorem states that the sum of the reciprocals of twin primes converges to Brun's constant.
• The prime-counting function π(n) is the number of primes not greater than n.
• The prime number theorem states π(n) is asymptotic to n / log n.
• Likelihood that a randomly chosen number less than n is prime is inversely proportional to the number of digits in n.
• The nth prime number is proportional to n log n, and the average size of a prime gap is proportional to log n.
• A more accurate estimate for π(n) is given by the offset logarithmic integral.
• An arithmetic progression is a sequence of numbers with the same difference (modulus) between consecutive numbers.
• In an arithmetic progression, all numbers have the same remainder when divided by the modulus.
• The infinite progression can have more than one prime only when its remainder and modulus are relatively prime.
• Dirichlet's theorem asserts that if the remainder and modulus are relatively prime, the progression contains infinitely many primes.
• The Green–Tao theorem shows there are arbitrarily long finite arithmetic progressions consisting only of primes.
• Hardy–Littlewood conjecture F predicts the density of primes among values of quadratic polynomials.

Riemann Hypothesis and Zeta Function

• The Riemann hypothesis concerns the location of zeros of the Riemann zeta function ζ(s).
• The zeta function is an analytic function on complex numbers.
• For complex numbers s with real part greater than one, it equals both an infinite sum over all integers and an infinite product over the prime numbers (Euler product).
• The Euler product is derived from the fundamental theorem of arithmetic, showing the connection between the zeta function and primes.
• The Riemann hypothesis states that the zeros of the zeta-function are either negative even numbers or complex numbers with real part equal to 1/2.

Modular Arithmetic and p-adic Numbers

• Modular arithmetic uses numbers {0, 1, 2, ..., n-1} for a modulus n.
• Any natural number is mapped into this system by replacing it with its remainder after division by n.
• Division by all nonzero numbers is possible if and only if the modulus is prime.
• Modular arithmetic modulo a prime number forms a field, while other moduli give a ring but not a field.
• Fermat's little theorem states that if a is not congruent to 0 (mod p), then a^(p-1) is congruent to 1 (mod p).
• Wilson's theorem says that an integer p > 1 is prime if and only if the factorial (p-1)! is congruent to -1 mod p.
• The p-adic order νp(n) of an integer n is the number of copies of p in the prime factorization of n.
• The p-adic absolute value |q|_p of any rational number q is defined as p^(-νp(q)).
• The p-adic distance measures how close two rational numbers are based on how divisible their difference is by a power of p.

Primes in Abstract Algebra

• In commutative rings, prime numbers are generalized to prime elements and irreducible elements.
• An element p of a ring R is prime if it is nonzero, has no multiplicative inverse, and if p divides xy, it also divides x or y.
• An element is irreducible if it is neither a unit nor the product of two other non-unit elements.
• In the ring of integers, prime and irreducible elements are the same.
• All prime elements are irreducible, but the converse holds only for unique factorization domains.
• The Gaussian integers Z[i] are complex numbers of the form a + bi, where a and b are integers; their prime elements are Gaussian primes.
• Prime ideals are generalizations of prime elements, used in commutative algebra, algebraic number theory, and algebraic geometry.
• The Lasker–Noether theorem generalizes the fundamental theorem of arithmetic to ideals in Noetherian commutative rings.

Applications of Prime Numbers

• Prime numbers are used in public-key cryptography algorithms like RSA and Diffie-Hellman.
• They are used in computing for checksums, hash tables, and pseudorandom number generators.
• Prime numbers have applications in abstract algebra and elementary geometry.
• The prime field of a given field is its smallest subfield containing 0 and 1 and the field of rational numbers or prime number of elements.
• Applications may also extend to quantum mechanics, and have been used metaphorically in the arts and literature.

Primality Testing

• Trial division tests primality by dividing by all numbers up to the square root.
• The sieve of Eratosthenes is a method for generating a list of primes.
• Probabilistic algorithms like the Solovay–Strassen test have a small chance of error.
• Deterministic algorithms like the AKS primality test guarantee a correct answer.
• The elliptic curve primality test is the fastest guaranteed-correct test in practice.
• Lucas–Lehmer primality test is used for Mersenne numbers.
• Shor's algorithm can factor integers in polynomial time on a quantum computer.

Miscellaneous

• Fermat primes are primes of the form 2^(2^k) + 1.
• A regular n-gon is constructible with straightedge and compass if its odd prime factors are distinct Fermat primes.
• The zeros of the Riemann zeta function may be connected to energy levels of quantum systems.
• Magicicada cicadas use prime-numbered breeding cycles to avoid predator synchronization.