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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}} , 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. Concerning ourselves only with the positive integers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \mathbb{Z}^+} , 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.

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \Z \,} 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² × 3. So neither 2 × 3 × 2 nor (–1)²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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \,} , the value of the prime counting function Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \pi(n) \,} is approximately

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \pi(n) \approx \frac{n}{\log n - 1}, \,}

or equivalently

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{n}{\pi(n)} \approx {\log \frac{n}{e}}. \,}

n-th prime

The Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \,} ^th prime is asymptotically

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_n \sim n \, \log n,\quad n \ge 1.}

The Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle 2^n \,} ^th prime is asymptotically

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p_{\{2^n\}} \sim 2^n \, \log 2^n \sim (\log 2) \, n \, 2^n,\quad n \ge 0.}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{p_{\{2^{n+1}\}}}{p_{\{2^n\}}} \sim 2 \, (1 + \tfrac{1}{n}),\quad n \ge 1.}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \frac{x}{\log x} \,}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lim_{x \to \infty} \frac{\pi(x)}{\left( \frac{x}{\log x} \right)} = 1. \,}

Prime gaps

The Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \,} ^th prime gap Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p_{n+1} \,-\, p_n} has the asymptotic mean

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \frac{1}{n} \, \sum_{k=1}^{n} (p_{k+1} - p_k) = \frac{1}{n} \, (p_{n+1} - p_1) \sim \frac{1}{n} ((n+1) \, \log (n+1) - 2) \sim \log n,\quad n \ge 1.}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p_{n+1} \,-\, p_n} can exceed Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle \log^2(n)} . (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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p_i \,} diverges (similarly to sum of reciprocals of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle i \log i \,} since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p_i \,\sim\, i \log i \,} ), i.e.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \lim_{n \to \infty} \sum_{i=1}^{n} \frac{1}{p_i} \to \infty,\quad \lim_{n \to \infty} \sum_{i=2}^{n} \frac{1}{i \log i} \to \infty, \,}

albeit very very slowly, both with asymptotic growth

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle O\left( {\scriptstyle \sum_{i=1}^{n} \frac{1}{p_i}} \right) = O\left( {\scriptstyle \sum_{i=1}^{n} \frac{1}{i \log i}} \right) = \log \log n, \,}

this implies that there are an infinity of primes.

Replacing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p_i \,} by Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p_i \log p_i \,} gives a converging series (see A137245) (similarly to sum of reciprocals of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle i (\log i)^2 \,} since Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle p_i \log p_i \,\sim\, i \log i (\log i + \log \log i) \,} )

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{i=1}^{\infty} \frac{1}{p_i \log p_i} = 1.636616323351260868569658\ldots, \,}

while (see A115563)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{i=2}^{\infty} \frac{1}{i (\log i)^2} = 2.10974280123689197447925\ldots, \,}

and (see A??????)

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \sum_{i=2}^{\infty} \frac{1}{i \log i (\log i + \log \log i)} = 2.93839982086091752090205661925125\ldots. \,}

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p = a^2 - b^2} has only one solution in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b} .

Proof. We can expand Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p = a^2 - b^2} as Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p = (a + b)(a - b)} . Since we stipulated that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p} is prime, it follows that either Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a + b = 1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a - b = p} or Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a + b = p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a - b = 1} Assuming the former, we can solve Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle a = \frac{p + 1}{2}} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle b = \frac{-(p - 1)}{2}} Thus it follows that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle p = \left(\frac{p + 1}{2}\right)^2 - \left(\frac{p - 1}{2}\right)^2 = a^2 - b^2} as specified by the theorem. □

For example, 7 = 4² – 3².

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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle n \,} of the form Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle xy \,} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle x \,>\, 1 \,} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \scriptstyle y \,>\, 1. \,}
• 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

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.