A prime number is a positive integer greater than 1 with exactly two positive divisors: 1 and itself. The first primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. A number greater than 1 that is not prime is called a composite number. Primes are central to number theory because every integer greater than 1 can be expressed uniquely as a product of primes, apart from the order of the factors. (users.math.msu.edu)
Definition and elementary properties
Primality concerns divisibility within the integers, rather than division producing arbitrary fractions. For example, 7 is prime because no positive integer other than 1 and 7 divides it without remainder; 12 is composite because (12=3\times4). The number 1 is neither prime nor composite: it has only one positive divisor. Excluding it from the primes also prevents the insertion of arbitrarily many factors of 1 into a prime factorization. (math.gordon.edu)
The number 2 is the only even prime, since every larger even integer has 2 as a proper divisor. Every composite integer (n) has a prime divisor no larger than (\sqrt n). Consequently, checking divisibility by primes up to this bound suffices to establish whether (n>1) is prime. (math.uwaterloo.ca)
A fundamental property, Euclid’s lemma, states that if a prime (p) divides a product (ab), then (p) divides (a) or (b). The analogous statement fails for general composite divisors: 6 divides (2\times3), but divides neither factor. (math.mit.edu)
Prime factorization
The fundamental theorem of arithmetic states that every integer (n>1) has a unique expression
[ n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, ]
where the (p_i) are distinct primes and the (a_i) are positive integers, once the primes are placed in a fixed order. For example,
[ 360=2^3\cdot3^2\cdot5. ]
Existence follows by repeatedly decomposing composite factors into smaller factors; uniqueness follows using Euclid’s lemma. Thus primes are the multiplicative building blocks of positive integers, although they do not provide a comparable unique decomposition under addition. (math.gordon.edu)
Infinitely many primes
The study of primes extends back to ancient Greece. Euclid established their infinitude in Book IX of the Elements. A familiar modern presentation uses proof by contradiction: suppose (p_1,\ldots,p_k) were all the primes, and form
[ N=p_1p_2\cdots p_k+1. ]
None of the listed primes divides (N), because division by each leaves remainder 1. Yet (N>1) must have a prime divisor, contradicting the completeness of the list. Importantly, (N) need not itself be prime; the argument requires only a prime factor absent from the proposed list. (faculty.etsu.edu)
Distribution
Primes become less frequent on average as numbers grow. Let (\pi(x)) denote the number of primes not exceeding (x). The prime number theorem states
[ \pi(x)\sim\frac{x}{\ln x}, ]
meaning that the ratio of the two expressions tends to 1 as (x) increases without bound. Independently proved by Jacques Hadamard and Charles-Jean de la Vallée Poussin in 1896, it establishes an average density rather than an exact rule locating each prime. (claymath.org)
There are also arbitrarily long runs of consecutive composite integers. For any integer (m\ge2), the numbers (m!+2,\ldots,m!+m) are composite, because each (m!+j) is divisible by (j). This demonstrates that prime gaps are unbounded. (math.uwaterloo.ca)
A deeper description involves the Riemann zeta function. The Riemann hypothesis, formulated by Bernhard Riemann in 1859 and still listed as unsolved by the Clay Mathematics Institute, asserts that its nontrivial zeros have real part (1/2). Its significance for primes concerns precise control of deviations from their average distribution. (claymath.org)
Finding and testing primes
The sieve of Eratosthenes is an algorithm for listing all primes up to a chosen bound. Starting with the integers from 2 onward, it repeatedly marks multiples of the smallest unmarked number. Marking need only continue through primes whose squares do not exceed the bound; the remaining unmarked integers are prime. (users.math.msu.edu)
For large individual inputs, primality testing differs from finding a complete factorization. Fermat’s little theorem states that, for prime (p) and integer (a) not divisible by (p),
[ a^{p-1}\equiv1\pmod p. ]
However, satisfying this congruence does not by itself prove primality. The Miller–Rabin test strengthens such tests by examining additional modular powers. Randomly chosen independent repetitions reduce the chance that a composite input passes every round. (math.mit.edu)
In 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena introduced the AKS primality test. It determines primality deterministically in time polynomial in the input’s digit length, without assuming an unproved conjecture. This is a landmark result in computational complexity, not a polynomial-time solution to integer factorization. (cse.iitk.ac.in)
Algebra and cryptography
In modular arithmetic, the residues modulo a prime (p) form a finite field: every nonzero residue has a multiplicative inverse. Residues modulo a composite integer do not have this property. Primes therefore distinguish an important algebraic setting in which division by nonzero elements is possible. (math.mit.edu)
Primes also underpin parts of cryptography. In RSA, a modulus is constructed from two large distinct primes. Knowing those factors enables calculation of information used to construct the private key. Efficient primality testing supports key generation, while difficulty recovering the factors from their product is a central security assumption. (math.mit.edu)