27 Functions of Number TheoryMultiplicative Number Theory27.11 Asymptotic Formulas: Partial Sums27.13 Functions

${p}_{n}$ is the $n$th prime, beginning with ${p}_{1}=2$. $\pi \left(x\right)$ is the number of primes less than or equal to $x$.

27.12.1 | $$\underset{n\to \mathrm{\infty}}{lim}\frac{{p}_{n}}{n\mathrm{ln}n}=1,$$ | ||

27.12.2 | $${p}_{n}>n\mathrm{ln}n,$$ | ||

$n=1,2,\mathrm{\dots}$. | |||

27.12.3 | $$ | ||

$x\ge 1$, | |||

where the series terminates when the product of the first $r$ primes exceeds $x$.

As $x\to \mathrm{\infty}$

27.12.4 | $$\pi \left(x\right)\sim \sum _{k=1}^{\mathrm{\infty}}\frac{(k-1)!x}{{(\mathrm{ln}x)}^{k}}.$$ | ||

There exists a positive constant $c$ such that

27.12.5 | $$\left|\pi \left(x\right)-\mathrm{li}\left(x\right)\right|=O\left(x\mathrm{exp}\left(-c{(\mathrm{ln}x)}^{1/2}\right)\right),$$ | ||

$x\to \mathrm{\infty}$. | |||

For the logarithmic integral $\mathrm{li}\left(x\right)$ see (6.2.8). The best available asymptotic error estimate (2009) appears in Korobov (1958) and Vinogradov (1958): there exists a positive constant $d$ such that

27.12.6 | $$\left|\pi \left(x\right)-\mathrm{li}\left(x\right)\right|=O\left(x\mathrm{exp}\left(-d{(\mathrm{ln}x)}^{3/5}{(\mathrm{ln}\mathrm{ln}x)}^{-1/5}\right)\right).$$ | ||

$\pi \left(x\right)-\mathrm{li}\left(x\right)$ changes sign infinitely often as $x\to \mathrm{\infty}$; see Littlewood (1914), Bays and Hudson (2000).

The Riemann hypothesis (§25.10(i)) is equivalent to the statement that for every $x\ge 2657$,

27.12.7 | $$ | ||

If $a$ is relatively prime to the modulus $m$, then there are infinitely many primes congruent to $a\phantom{\rule{veryverythickmathspace}{0ex}}(modm)$.

The number of such primes not exceeding $x$ is

27.12.8 | $$\frac{\mathrm{li}\left(x\right)}{\varphi \left(m\right)}+O\left(x\mathrm{exp}\left(-\lambda (\alpha ){(\mathrm{ln}x)}^{1/2}\right)\right),$$ | ||

$m\le {(\mathrm{ln}x)}^{\alpha}$, $\alpha >0$, | |||

where $\lambda (\alpha )$ depends only on $\alpha $, and $\varphi \left(m\right)$ is the Euler totient function (§27.2).

A Mersenne prime is a prime of the form ${2}^{p}-1$. The largest known prime (2009) is the Mersenne prime ${2}^{43,112,609}-1$. For current records see The Great Internet Mersenne Prime Search.

A pseudoprime test is a test that correctly identifies most composite numbers. For example, if ${2}^{n}\overline{)\equiv}2\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$, then $n$ is composite. Descriptions and comparisons of pseudoprime tests are given in Bressoud and Wagon (2000, §§2.4, 4.2, and 8.2) and Crandall and Pomerance (2005, §§3.4–3.6).

A Carmichael number is a composite number $n$ for which ${b}^{n}\equiv b\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$ for all $b\in \mathbb{N}$. There are infinitely many Carmichael numbers.