§27.12 Asymptotic Formulas: Primes

There exists a positive constant $c$ such that

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

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

If $a$ is relatively prime to the modulus $m$, then there are infinitely many primes congruent to $a(modm)$.

The number of such primes not exceeding $x$ is

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 (2018) is the Mersenne prime $2^{82,589,933}-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\cancel{\equiv }2(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(modn)$ for all $b\in \mathbb{N}$. There are infinitely many Carmichael numbers.