Prime number

A 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.

There are infinitely many primes, as demonstrated by Euclid around 300 BC. 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.

Definition and examples

Main article: List of prime numbers

Demonstration, with Cuisenaire rods, that 7 is prime, because none of 2, 3, 4, 5, or 6 divide it evenly

A natural number bigger than 1 is called a prime number if it cannot be divided by any number except 1 and itself. Numbers bigger 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. A 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

People have studied prime numbers for thousands of years. Old writings, like the Rhind Mathematical Papyrus, show that they were interested in these special numbers. The ancient Greek mathematicians were some of the first to study primes a lot, and they called them prōtos arithmòs. Euclid showed, around 300 BC, that there are infinitely many primes. He also showed how to use a special kind of prime, called a Mersenne prime, to build perfect numbers. The Greeks made a smart method called the Sieve of Eratosthenes to find primes, and we still use it today.

Later, mathematicians like Ibn al-Haytham found new things about primes, and Fibonacci shared these ideas in Europe. Many famous mathematicians have helped us learn more about primes. Today, finding bigger and bigger primes is a fun challenge, often done with 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 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 × 5².

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.

Analytic properties

Analytic number theory is a part of math that studies numbers using ideas from continuous functions, limits, and infinite series.

This area began with the mathematician Leonhard Euler. He made an important discovery about adding special fractions. His work helped connect prime numbers to a key math idea called the Riemann zeta function. This is related to a big unsolved problem in math today, the Riemann hypothesis.

We know that prime numbers appear in a certain pattern among larger numbers, thanks to something called the prime number theorem. But we do not have a simple way to find every prime number exactly.

Abstract algebra

Modular arithmetic and finite fields

Main article: Modular arithmetic

Modular arithmetic is a way to do math using only numbers from 0 up to a certain number, called the modulus. For example, with modulus 7, we only use the numbers 0, 1, 2, 3, 4, 5, and 6.

In this system, dividing works for all non-zero numbers only when the modulus is a prime number. For example, with modulus 7, dividing by 3 works. 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 a different way to think about numbers, similar to 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.

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, the number 2 can be broken down into smaller parts.

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. They are useful in advanced areas of math.

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 were once studied just for fun in math. They had few real-life uses, like helping gears wear out evenly. This changed in the 1970s when people discovered that prime numbers could help lock and unlock secret messages in public-key cryptography. Because of this, scientists have worked to find quick ways to tell if a number is prime, called primality testing.

The easiest way to check if a number is prime is called trial division. You divide the number by every whole number from 2 up to its square root. If any division works perfectly, the number isn’t prime. This method works but can be slow for very large numbers.

Other methods, like the sieve of Eratosthenes, help list 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 correct 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	2^136,279,841 − 1	41,024,320	October 12, 2024	Luke Durant, Great Internet Mersenne Prime Search
Proth prime	10,223 × 2^31,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 × 2^1,290,000 ± 1	388,342	September 2016	Tom Greer, PrimeGrid

Other applications

Prime numbers are important in math and have many uses. They help solve problems in areas like abstract algebra and geometry. For example, prime numbers can arrange points on a grid so that no three are in a line. They can also make sure every triangle formed by three points has large area.

Prime numbers appear in other fields too. 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 coming out. 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 special patterns and ideas.