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 $\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 $\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 $\scriptstyle \mathbb {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 $\scriptstyle n\,$, the value of the prime counting function $\scriptstyle \pi (n)\,$ is approximately

$\pi (n)\approx {\frac {n}{\log n-1}},\,$

or equivalently

${\frac {n}{\pi (n)}}\approx {\log {\frac {n}{e}}}.\,$

n-th prime

The $\scriptstyle n\,$^th prime is asymptotically

$p_{n}\sim n\,\log n,\quad n\geq 1.$

The $\scriptstyle 2^{n}\,$^th prime is asymptotically

$p_{\{2^{n}\}}\sim 2^{n}\,\log 2^{n}\sim (\log 2)\,n\,2^{n},\quad n\geq 0.$

${\frac {p_{\{2^{n+1}\}}}{p_{\{2^{n}\}}}}\sim 2\,(1+{\tfrac {1}{n}}),\quad n\geq 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 $\scriptstyle {\frac {x}{\log x}}\,$

$\lim _{x\to \infty }{\frac {\pi (x)}{\left({\frac {x}{\log x}}\right)}}=1.\,$

Prime gaps

The $\scriptstyle n\,$^th prime gap $\scriptstyle p_{n+1}\,-\,p_{n}$ has the asymptotic mean

${\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\geq 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 $\scriptstyle p_{n+1}\,-\,p_{n}$ can exceed $\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 $\scriptstyle p_{i}\,$ diverges (similarly to sum of reciprocals of $\scriptstyle i\log i\,$ since $\scriptstyle p_{i}\,\sim \,i\log i\,$), i.e.

$\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

$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 $\scriptstyle p_{i}\,$ by $\scriptstyle p_{i}\log p_{i}\,$ gives a converging series (see A137245) (similarly to sum of reciprocals of $\scriptstyle i(\log i)^{2}\,$ since $\scriptstyle p_{i}\log p_{i}\,\sim \,i\log i(\log i+\log \log i)\,$)

$\sum _{i=1}^{\infty }{\frac {1}{p_{i}\log p_{i}}}=1.636616323351260868569658\ldots ,\,$

while (see A115563)

$\sum _{i=2}^{\infty }{\frac {1}{i(\log i)^{2}}}=2.10974280123689197447925\ldots ,\,$

and (see A??????)

$\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 $p=a^{2}-b^{2}$ has only one solution in $a$ and $b$.

Proof. We can expand $p=a^{2}-b^{2}$ as $p=(a+b)(a-b)$. Since we stipulated that $p$ is prime, it follows that either $a+b=1$ and $a-b=p$ or $a+b=p$ and $a-b=1$ Assuming the former, we can solve $a={\frac {p+1}{2}}$ and $b={\frac {-(p-1)}{2}}$ Thus it follows that $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 $\scriptstyle n\,$ of the form $\scriptstyle xy\,$ for $\scriptstyle x\,>\,1\,$ and $\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.