Prime number
A natural number greater than one cannot be written as the product of two smaller natural numbers. This simple restriction creates a unique class of integers known as prime numbers. Consider the number five. It stands alone because no pair of smaller whole numbers multiplies to produce it. Contrast this with four, which splits cleanly into two times two. That ability to break apart defines composite numbers. The distinction matters deeply for all of mathematics. Every integer larger than one is either prime or can be broken down into primes in exactly one way. This rule is called the fundamental theorem of arithmetic. It treats primes as the basic building blocks of the entire number system. Without them, the structure of arithmetic would collapse into chaos.
Ancient Greek mathematicians around 300 BC began studying these special numbers systematically. Euclid wrote Elements and proved that there are infinitely many primes using a clever logical argument. He showed that any finite list of primes could always be extended by multiplying them together and adding one. Islamic scholars later expanded this work significantly. Ibn al-Haytham discovered Wilson's theorem around 1000 AD while working on characterizing prime numbers. Pierre de Fermat stated his famous little theorem without proof in 1640. Christian Goldbach formulated his conjecture about even numbers in a letter to Leonhard Euler in 1742. Legendre and Gauss made early guesses about how primes distribute themselves among large numbers at the start of the 19th century. Bernhard Riemann published his groundbreaking paper on the zeta function in 1859. Hadamard and de la Vallée Poussin completed the proof of the prime number theorem in 1896. Modern computers have found massive primes since 1951 through distributed projects like the Great Internet Mersenne Prime Search.
The sequence of prime numbers never ends according to Euclid's theorem from over two millennia ago. This infinitude means mathematicians can always find larger examples no matter how far they count. The distribution of these numbers follows statistical patterns described by the prime number theorem. That theorem states that the probability of a randomly chosen large number being prime is inversely proportional to its logarithm. Gaps between consecutive primes vary wildly yet follow predictable trends. Twin primes are pairs differing by exactly two, and their existence remains an open question known as the twin prime conjecture. Polignac's conjecture generalizes this idea to any positive integer difference. Large gaps occur much earlier than simple arguments suggest. For instance, the first gap of length eight appears between eighty-nine and ninety-seven. These irregularities hide deep order within apparent randomness. Euler showed that the sum of reciprocals of primes grows without bound even though individual terms shrink toward zero. Brun's theorem proves that the sum of reciprocals of twin primes converges to a finite value.
Goldbach's conjecture asserts that every even integer greater than two equals the sum of two primes. Mathematicians have verified this statement for all numbers up to four times ten to the eighteen but lack a general proof. Vinogradov's theorem confirms that sufficiently large odd integers decompose into three primes. Chen's theorem shows that every sufficiently large even number splits into a prime plus a semiprime. The Riemann hypothesis asks where the zeros of the zeta function lie in the complex plane. If true, it would confirm precise bounds on how regularly primes distribute themselves. Legendre's conjecture suggests the largest gap from one to n stays below approximately square root of n. Cramér's conjecture proposes an even tighter limit based on logarithmic growth. Hardy and Littlewood formulated conjectures about patterns called prime tuples appearing across differences among multiple primes. No quadratic polynomial has been proven to generate infinitely many prime values despite Euler noting that x squared plus x plus forty yields primes for small inputs. These open problems drive research forward while resisting centuries of effort.
Trial division checks primality by dividing a given integer by each number from two up to its square root. This method works perfectly but becomes impractical for large numbers because tests grow exponentially with digit count. Modern algorithms like Miller-Rabin offer speed at the cost of tiny error probabilities. Repeating such probabilistic tests reduces failure chances dramatically. Deterministic methods guarantee correctness forever. The AKS primality test developed in 2002 runs in polynomial time yet remains slower than elliptic curve proving in practice. Special forms allow faster verification. Mersenne numbers use Lucas-Lehmer testing since nineteen ninety-two when the largest known prime became a Mersenne prime. Distributed computing projects found massive examples recently. Luke Durant discovered a Mersenne prime with over forty-one million digits in October twenty-twenty-four. Peter Szabolcs identified a Proth prime exceeding nine million digits in late twenty-sixteen. Quantum computers running Shor's algorithm can factor integers efficiently though current technology handles only very small cases like twenty-one so far.
Public-key cryptography emerged publicly in the nineteen seventies and revolutionized digital security. Algorithms like RSA rely on multiplying two large primes while keeping their product secret. Breaking this code requires factoring that enormous composite back into original components. No efficient classical algorithm exists to perform this reverse operation today. Diffie-Hellman key exchange uses modular exponentiation alongside discrete logarithm hardness assumptions. Twenty-four hundred bit primes are common standards for modern encryption systems. Hash tables utilize random linear functions modulo large primes to distribute data evenly. International Standard Book Numbers employ checksums based on division by eleven. Adler-32 checksums use arithmetic modulo sixty-five thousand five hundred twenty-one, the largest prime below sixty-five thousand five hundred thirty-six. Pseudorandom number generators including the Mersenne Twister depend heavily on prime properties. These practical applications shattered G.H. Hardy's earlier belief that number theory held no military significance whatsoever.
Prime concepts extend beyond ordinary integers into rings and algebraic structures. Gaussian integers form a ring where some rational primes split further into factors. The number two decomposes into complex conjugates involving imaginary units. Primes congruent to three modulo four remain prime within Gaussian integers while those congruent to one modulo four do not. Prime ideals generalize these ideas to subsets containing all sums of pairs and products with ring elements. Unique factorization fails in certain rings like quadratic integer domains but holds in unique factorization domains. Chebotarev's density theorem addresses how many integer primes factor into multiple prime ideals within algebraic fields. Sylow theorems imply subgroups exist whenever prime powers divide group orders. Knot theory defines prime knots as indecomposable objects unable to split into connected sums of nontrivial components. Cicadas of genus Magicicada emerge after seven thirteen or seventeen years using prime cycles to avoid predator synchronization. French composer Olivier Messiaen created ametrical music employing motifs of lengths forty-one forty-three forty-seven and fifty-three inspired by natural phenomena.
Common questions
What is a prime number?
A natural number greater than one cannot be written as the product of two smaller natural numbers. This simple restriction creates a unique class of integers known as prime numbers.
When did Euclid prove that there are infinitely many primes?
Euclid wrote Elements and proved that there are infinitely many primes around 300 BC using a clever logical argument. He showed that any finite list of primes could always be extended by multiplying them together and adding one.
Who discovered Wilson's theorem and when was it found?
Ibn al-Haytham discovered Wilson's theorem around 1000 AD while working on characterizing prime numbers. Islamic scholars later expanded this work significantly after ancient Greek mathematicians began studying these special numbers systematically.
How does public-key cryptography use prime numbers for security?
Public-key cryptography emerged publicly in the nineteen seventies and revolutionized digital security through algorithms like RSA that rely on multiplying two large primes. Breaking this code requires factoring that enormous composite back into original components without an efficient classical algorithm existing today.
When did Luke Durant discover a Mersenne prime with over forty-one million digits?
Luke Durant discovered a Mersenne prime with over forty-one million digits in October twenty-twenty-four. Modern computers have found massive primes since 1951 through distributed projects like the Great Internet Mersenne Prime Search.