This site is supported by donations to The OEIS Foundation.

# Prime numbers

This article needs more **work**.

Please help by expanding it!

“It will be another million years at least before we understand the primes.”—Paul Erdős

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, ...}

In a given ring of integers, the **prime numbers** are those numbers which are divisible only by themselves, their associates and the units of the ring, but are themselves not units. For example, in the ring of integers , 47 is a prime number because it is divisible only by –47, –1, 1 and itself, and no other integers. 48, on the other hand, is not prime because, besides being divisible by –48, –1, 1 and itself, it is also divisible by –24, –16, –12, etc. Numbers like 48 are called composite numbers. If the prime numbers are the multiplicative "atoms" of the integers, the composite numbers are the "molecules."

Until the beginning of the 20^{th} century, 1 was considered a prime number. The former definition allowed units to be considered primes. The new definition, excluding units from the set primes, stems from the development of abstract algebra at the turn of the 20^{th} century, is now accepted by most mathematicians.^{[1]} Concerning ourselves only with the positive integers , this meant a change from requiring a prime number to be divisible only by 1 and itself (a requirement that 1 meets trivially) to requiring a prime to have exactly two distinct divisors. For example, 47 has two distinct divisors (1 and 47 itself), while 1 has only one divisor, itself.

## Contents

## Zero, units, primes and composites

Zero is divisible by all (infinite number of) nonzero integers (thus 0 is neither prime nor composite), and it is also not the product of nonzero integers. Zero is also non-invertible (thus 0 is not a unit).

A unit (i.e. invertible integer) is neither prime nor composite since it is divisible by no nonunit whatsoever, thus the units −1 and 1 of are neither prime nor composite.

The integers are either

- Negative composite numbers: {−4, −6, −8, −9, −10, −12, −14, −15, −16, −18, −20, −21, −22, −24, −25, −26, −27, −28, ...} (−1 × A002808)
- Negative prime numbers: {−2, −3, −5, −7, −11, −13, −17, −19, −23, −29, −31, −37, −41, −43, −47, -53, -59, ...} (−1 × A000040)
- Negative unit: {−1}
- Zero: {0}
- Positive unit: {1}
- Positive primes numbers: {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, ...} (A000040)
- Positive composite numbers: {4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, ...} (A002808)

## Fundamental theorem of arithmetic

*Main article page: Fundamental theorem of arithmetic*

The fundamental theorem of arithmetic asserts that every nonzero integer can be written as a product of primes in a unique way, up to ordering and multiplication by units. For example, the only factorization of 12 is 2^{2} × 3. So neither 2 × 3 × 2 nor (–1)^{2}2^{2}3 constitutes a different factorization: the former is a different ordering while the latter multiplies by the unit –1.

## Infinitude of primes

*Main article page: Euclid's proof that there are infinitely many primes*

In Book IX of the Elements, Euclid proved that there are infinitely many prime numbers: he showed that if we assume the set of prime numbers to be finite, it leads to a contradiction. There are other ways to prove this fact, but Euclid's way is still considered the most elegant.

## Density of primes

For a given positive number , the value of the prime counting function is approximately

or equivalently

## n-th prime

The ^{th} **prime** is asymptotically

The ^{th} **prime** is asymptotically

A033844 Prime(2^n), n >= 0.

- {2, 3, 7, 19, 53, 131, 311, 719, 1619, 3671, 8161, 17863, 38873, 84017, 180503, 386093, 821641, 1742537, 3681131, 7754077, 16290047, 34136029, 71378569, 148948139, ...}

### Prime number theorem

*Main article page: Prime number theorem*

The prime number theorem asserts that the asymptotic density of primes is

## Prime gaps

The ^{th} **prime gap** has the asymptotic mean

A prime gap of 1 happens only once, i.e. between 2 and 3, all other prime gaps being even since all primes other than 2 are odd. It is conjectured that all even prime gaps happen infinitely often.

A prime gap of 2 (between the twin primes) is conjectured to happen infinitely often, this being the twin primes conjecture.

### Large prime gaps

Prime gaps can exceed . (Infinitely often?)

A182315 Primes prime(n) such that prime(n+1) - prime(n) > log(n)^2.

- {2, 3, 5, 7, 13, 23, 31, 113, 1327, 31397, 370261, 492113, 2010733, 20831323, 25056082087, 42652618343, 2614941710599, 19581334192423, ...}

## Sum of reciprocals of primes

Since the sum of reciprocals of primes diverges (similarly to sum of reciprocals of since ), i.e.

albeit very very slowly, both with asymptotic growth

this implies that there are an infinity of primes.

Replacing by gives a converging series (see A137245) (similarly to sum of reciprocals of since )

while (see A115563)

and (see A??????)

## Other facts about prime numbers

Theorem.(Fermat)An odd prime number can be represented as the difference of two squares in one and only one way. This is to say that has only one solution in and .

Proof.We can expand as . Since we stipulated that is prime, it follows that either and or and Assuming the former, we can solve and Thus it follows that as specified by the theorem. □

For example, 7 = 4^{2} – 3^{2}.

## Sequences

A137245 Decimal expansion of sum 1/(p * log p) over the primes p = 2, 3, 5, 7, 11, ...

- {1, 6, 3, 6, 6, 1, 6, 3, 2, 3, 3, 5, 1, 2, 6, 0, 8, 6, 8, 5, 6, 9, 6, 5, 8, 0, 0, 3, 9, 2, 1, 8, 6, 3, 6, 7, 1, 1, 8, 1, 5, 9, 7, 0, 7, 6, 1, 3, 1, 2, ...}

Note that this is almost (a tiny bit less than) 1 + 2/Pi = 1.63661977236758... (coincidence or not?)

## See also

- A008578 Prime numbers at the beginning of the 20
^{th}century (today 1 is no longer regarded as a prime, but as a unit). - A002808 The composite numbers: numbers of the form for and
- Gaussian integers, Gaussian primes and Gaussian composites
- Eisenstein integers, Eisenstein primes and Eisenstein composites
- Sieve of Eratosthenes
- Characteristic function of prime numbers
- Classifications of prime numbers
- Irreducible elements

## Notes

- ↑ 1 and Prime Numbers - Numberphile, YouTube.

## External links

- Weisstein, Eric W., Prime Number, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/PrimeNumber.html]
- The Prime Pages (prime number research, records and resources)
- http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Prime_numbers.html
- Michael Coons, Yet another proof of the infinitude of primes, I.