# §27.12 Asymptotic Formulas: Primes

is the th prime, beginning with . is the number of primes less than or equal to .

27.12.1
27.12.2.

where the series terminates when the product of the first primes exceeds .

## ¶ Prime Number Theorem

There exists a positive constant such that

For the logarithmic integral see (6.2.8). The best available asymptotic error estimate (2009) appears in Korobov (1958) and Vinogradov (1958): there exists a positive constant such that

changes sign infinitely often as ; see Littlewood (1914), Bays and Hudson (2000).

The Riemann hypothesis25.10(i)) is equivalent to the statement that for every ,

If is relatively prime to the modulus , then there are infinitely many primes congruent to .

The number of such primes not exceeding is

where depends only on , and is the Euler totient function (§27.2).

A Mersenne prime is a prime of the form . The largest known prime (2009) is the Mersenne prime . 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 , then 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 for which for all . There are infinitely many Carmichael numbers.