Prime Numbers

Definition and Basic Properties

Definition

Prime number: natural number greater than 1 with exactly two positive divisors: 1 and itself. Composite number: natural number with more than two divisors. Unit (1): neither prime nor composite.

Basic Properties

Uniqueness: primes are irreducible elements in integers. Infinitude: infinite primes proven by Euclid. Divisibility: prime divisor divides product implies divides a factor. GCD: prime factors determine greatest common divisors.

Examples

Small primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31...

Historical Background

Ancient Mathematics

Euclid’s Elements (~300 BCE): proof of infinite primes. Eratosthenes’ sieve: early prime finding algorithm. Ancient Greek focus on primes for number theory foundations.

Medieval to Renaissance

Development of factorization concepts. Arab mathematicians contributed to primality and factorization studies. Euler's work linked primes and zeta function.

Modern Era

19th-20th centuries: analytic number theory development. Riemann hypothesis connects primes to complex zeros. Computational advances enable large prime discoveries.

Fundamental Theorem of Arithmetic

Statement

Every integer greater than 1 can be uniquely represented as a product of prime numbers, up to order.

Implications

Uniqueness establishes primes as "building blocks" of integers. Basis for factorization algorithms and cryptographic systems.

Proof Sketch

Existence: factor by smallest prime divisor repeatedly. Uniqueness: prime divides product implies divides one factor; contradiction if different factorizations exist.

Distribution of Prime Numbers

Prime Number Theorem

Asymptotic density: number of primes ≤ n approximates n / ln(n). Error terms studied in analytic number theory.

Chebyshev’s Bounds

Bounds for prime counting function π(n) provide early approximations. Establish existence of primes in intervals.

Riemann Hypothesis

Conjecture on zeros of Riemann zeta function implies tight bounds on prime distribution. Central open problem in number theory.

Primality Testing Algorithms

Trial Division

Divide candidate by primes up to √n. Simple but inefficient for large n.

Probabilistic Tests

Miller-Rabin: probabilistic with adjustable error. Solovay-Strassen: Euler’s criterion based.

Deterministic Tests

AKS primality test: polynomial time, deterministic. Elliptic Curve Primality Proving (ECPP) for large primes.

Prime Factorization Methods

Trial Division

Divide by primes ≤ √n. Suitable for small numbers.

Pollard’s Rho Algorithm

Randomized algorithm efficient for moderate-size integers. Uses pseudorandom sequences to find nontrivial factors.

Quadratic Sieve and General Number Field Sieve

Advanced sub-exponential algorithms for large integers. Basis for breaking RSA cryptosystem security.

Special Classes of Primes

Mersenne Primes

Primes of form 2^p - 1 where p is prime. Connection to perfect numbers.

Fermat Primes

Primes of form 2^(2^n) + 1. Only five known; related to constructible polygons.

Safe Primes and Sophie Germain Primes

Safe prime: p where (p-1)/2 is also prime. Sophie Germain prime: p where 2p+1 is prime. Important in cryptography.

Applications of Prime Numbers

Cryptography

RSA and Diffie-Hellman rely on large primes for security. Difficulty of factorization underpins encryption.

Hashing and Random Number Generation

Prime moduli used in hashing functions and pseudorandom number generators for uniformity.

Mathematical Proofs and Algorithms

Used in proofs by induction, primality-based algorithms, and combinatorial constructions.

Open Problems in Prime Number Theory

Goldbach’s Conjecture

Every even integer > 2 is sum of two primes. Verified for large numbers but unproven generally.

Twin Prime Conjecture

Infinite primes p such that p+2 is prime. Recent progress but full proof absent.

Legendre’s and Other Conjectures

Primes in intervals and arithmetic progressions. Riemann Hypothesis remains central.

Tables of Small Primes and Properties

Note: Index refers to position in ascending prime sequence.

Algorithms and Pseudocode

Sieve of Eratosthenes

Input: integer n > 1Create list of integers 2 to nFor p = 2 to √n: If p is not marked: Mark all multiples of p (p^2, p^2+p, ...) up to nOutput unmarked numbers as primes

Miller-Rabin Primality Test (Probabilistic)

Input: odd integer n > 2, number of rounds kWrite n-1 as 2^r * d with d oddFor i = 1 to k: Pick random a in [2, n-2] x = a^d mod n If x = 1 or x = n-1: continue next iteration Repeat r-1 times: x = x^2 mod n If x = n-1: break If x ≠ n-1: compositeReturn probably prime

References

• Hardy, G.H., & Wright, E.M. An Introduction to the Theory of Numbers, Oxford University Press, 2008, pp. 45-78.
• Ribenboim, P. The New Book of Prime Number Records, Springer-Verlag, 1996, pp. 12-56.
• Davenport, H. Multiplicative Number Theory, Graduate Texts in Mathematics, Springer, 2000, pp. 101-130.
• Crandall, R., & Pomerance, C. Prime Numbers: A Computational Perspective, Springer, 2005, pp. 23-65.
• Granville, A. "Prime Number Races," The American Mathematical Monthly, vol. 113, no. 1, 2006, pp. 1-33.