SafekipediaA prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it can be written as 2 × 2, where both numbers are smaller than 4. Primes are very important in number theory because of a key idea called the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes in a way that is unique up to their order.
There are infinitely many primes, as demonstrated by Euclid around 300 BC. Even though we know primes go on forever, no one has found a simple formula to tell us which numbers are prime and which are not. However, we can make good guesses about how often primes appear among larger numbers. One important idea is the prime number theorem, which tells us that for very large numbers, the chance of a number being prime is about one divided by the number of its digits.
Primes are also very useful in the real world. For example, they help keep information safe on the internet through something called public-key cryptography. This method relies on how hard it is to break down very large numbers into their prime factors. Even today, mathematicians are still trying to solve big mysteries about primes, like whether there are infinitely many pairs of primes that are only two numbers apart, known as the twin prime conjecture.
Definition and examples
Main article: List of prime numbers
A natural number greater than 1 is called a prime number if it cannot be written as the product of two smaller natural numbers. Numbers greater than 1 that are not prime are called composite numbers. For example, 2, 3, and 5 are prime numbers because they can only be divided evenly by 1 and themselves. The number 1 is not prime because it only has one divisor, which is itself.
The first few prime numbers are 2, 3, 5, 7, 11, and 13. One special fact is that except for the number 2, all prime numbers are odd. This is because any even number greater than 2 can be divided by 2.
History
The study of prime numbers dates back thousands of years. Ancient records, like the Rhind Mathematical Papyrus, show early interest in these special numbers. The ancient Greek mathematicians were among the first to deeply study primes, calling them prōtos arithmòs. Euclid’s work, around 300 BC, proved there are infinitely many primes and showed how to build perfect numbers from a special kind of prime called a Mersenne prime. The Greeks also created the Sieve of Eratosthenes, a clever method still used today to find primes.
Later, mathematicians like Ibn al-Haytham in Islam discovered new properties of primes, and Fibonacci brought these ideas to Europe. Over time, many famous mathematicians contributed to our understanding of primes, creating theorems and tests to identify them. Today, finding ever-larger primes is a popular challenge, often done through big computer projects like the Great Internet Mersenne Prime Search.
Elementary properties
Main article: Fundamental theorem of arithmetic
A prime number is a number greater than 1 that can only be divided by 1 and itself. For example, the number 5 is prime because the only ways to write it as a product are 1 × 5 or 5 × 1. Writing a number as a product of prime numbers is called a prime factorization. The same prime number can appear more than once in this product. For example, the number 50 can be written as 2 × 5 × 5, which is the same as 2 × 52.
Prime numbers are important because every number larger than 1 can be written as a product of prime numbers. This product is unique, meaning any two ways of writing the same number as a product of primes will use the same primes, even if the order is different. This idea is known as the fundamental theorem of arithmetic.
Main article: Euclid's theorem
There are infinitely many prime numbers. This means the list of primes — 2, 3, 5, 7, 11, 13, and so on — never ends. This fact is called Euclid’s theorem, named after the ancient Greek mathematician Euclid, who first proved it. One simple way to understand this is to imagine taking any list of primes, multiplying them together, and then adding 1. The resulting number will always have a prime factor that is not in the original list, showing that the list was incomplete. Because no finite list can include all primes, there must be infinitely many.
Analytic properties
Analytic number theory is a branch of mathematics that studies numbers using methods from continuous functions, limits, infinite series, and other advanced math ideas.
This area started with the mathematician Leonhard Euler. One of his big discoveries was solving a problem about adding up special fractions. This work helped connect prime numbers to a very important math idea called the Riemann zeta function, which is linked to one of the biggest unsolved problems in math today, known as the Riemann hypothesis.
We know that prime numbers are spread out in a certain way among larger numbers, thanks to something called the prime number theorem. But we don’t have a simple formula to tell us exactly where every prime number is.
Abstract algebra
Modular arithmetic and finite fields
Main article: Modular arithmetic
Modular arithmetic is a way of doing math where we only use numbers from 0 up to some number n, called the modulus. For example, with modulus 7, we only use the numbers 0, 1, 2, 3, 4, 5, and 6.
In this system, division is possible for all non-zero numbers only when the modulus is a prime number. For example, with modulus 7, dividing by 3 works because 2 divided by 3 equals 3. But with modulus 6, dividing by 3 does not work because there is no clear answer.
p-adic numbers
Main article: p-adic number
p-adic numbers are another way to look at numbers, similar to how we think about real numbers. They help us understand numbers by looking at how many times a prime number divides into them. This idea can be used to create a new kind of number system, just like the real numbers, but with different rules.
Prime elements of a ring
Main articles: Prime element and Irreducible element
In algebra, we can think about prime numbers in different settings called rings. In these settings, prime numbers can behave differently. For example, in a special kind of ring called Gaussian integers, the number 2 can be broken down into smaller parts, unlike in regular whole numbers.
Prime ideals
Main article: Prime ideals
Prime ideals are special sets of numbers in rings that help us understand how numbers can be broken down into smaller parts. They are useful in advanced areas of math like algebraic number theory and geometry.
Group theory
In the study of groups, which are collections of elements that can be combined in certain ways, prime numbers play a key role. For example, if the size of a group is a power of a prime number, the group will have smaller groups of that exact size. This helps mathematicians understand the structure of groups better.
Computational methods
Prime numbers used to be studied just for fun in math, with no real-life uses except maybe for making gear teeth wear out evenly. This changed in the 1970s when people found that prime numbers could lock and unlock secret messages in public-key cryptography. Because of this, scientists have worked hard to find quick ways to tell if a number is prime, called primality testing.
The simplest way to check if a number is prime is called trial division. You divide the number by every integer from 2 up to its square root. If any of these divisions work perfectly, the number isn’t prime. This method works but gets slow for very large numbers.
Other methods, like the sieve of Eratosthenes, help list out all prime numbers up to a certain point. Some tests, such as the Solovay–Strassen primality test, use chances and probabilities to guess if a number is prime, while others, like the AKS primality test, always give the right answer.
| Test | Developed in | Type | Running time |
|---|---|---|---|
| AKS primality test | 2002 | deterministic | O ( ( log n ) 6 + ε ) {\displaystyle O((\log n)^{6+\varepsilon })} |
| Elliptic curve primality proving | 1986 | Las Vegas | O ( ( log n ) 4 + ε ) {\displaystyle O((\log n)^{4+\varepsilon })} heuristically |
| Baillie–PSW primality test | 1980 | Monte Carlo | O ( ( log n ) 2 + ε ) {\displaystyle O((\log n)^{2+\varepsilon })} |
| Miller–Rabin primality test | 1980 | Monte Carlo | O ( k ( log n ) 2 + ε ) {\displaystyle O(k(\log n)^{2+\varepsilon })} |
| Solovay–Strassen primality test | 1977 | Monte Carlo | O ( k ( log n ) 2 + ε ) {\displaystyle O(k(\log n)^{2+\varepsilon })} |
| Type | Prime | Number of decimal digits | Date | Found by |
|---|---|---|---|---|
| Mersenne prime | 2136,279,841 − 1 | 41,024,320 | October 12, 2024 | Luke Durant, Great Internet Mersenne Prime Search |
| Proth prime | 10,223 × 231,172,165 + 1 | 9,383,761 | October 31, 2016 | Péter Szabolcs, PrimeGrid |
| factorial prime | 208,003! − 1 | 1,015,843 | July 2016 | Sou Fukui |
| primorial prime | 1,098,133# − 1 | 476,311 | March 2012 | James P. Burt, PrimeGrid |
| twin primes | 2,996,863,034,895 × 21,290,000 ± 1 | 388,342 | September 2016 | Tom Greer, PrimeGrid |
Other applications
Prime numbers are very important in mathematics and have many uses. They help solve problems in areas like abstract algebra and geometry. For example, prime numbers can be used to arrange points on a grid so that no three are in a line, or to make sure every triangle formed by three points has large area.
Prime numbers also appear in other fields. In quantum mechanics, they might help explain energy levels in tiny systems. In nature, some cicadas live underground for prime numbers of years — like 7, 13, or 17 years — before emerging. Scientists think this helps them avoid predators. Artists and writers, such as Olivier Messiaen and Carl Sagan, have used prime numbers in their work to create unique patterns and ideas.
Images
This article is a child-friendly adaptation of the Wikipedia article on Prime number, available under CC BY-SA 4.0.
Images from Wikimedia Commons. Tap any image to view credits and license.