Prime Number Theorem - Prime Number Theorem For Arithmetic Progressions

Prime Number Theorem For Arithmetic Progressions

Let denote the number of primes in the arithmetic progression a, a + n, a + 2n, a + 3n, … less than x. Dirichlet and Legendre conjectured, and Vallée-Poussin proved, that, if a and n are coprime, then

\pi_{n,a}(x) \sim \frac{1}{\phi(n)}\mathrm{Li}(x),

where φ(·) is the Euler's totient function. In other words, the primes are distributed evenly among the residue classes modulo n with gcd(a, n) = 1. This can be proved using similar methods used by Newman for his proof of the prime number theorem.

The Siegel–Walfisz theorem gives a good estimate for the distribution of primes in residue classes.

Read more about this topic:  Prime Number Theorem

Famous quotes containing the words prime, number, theorem and/or arithmetic:

    “What was lost in the European cataclysm was not only the Jewish past—the whole life of a civilization—but also a major share of the Jewish future.... [ellipsis in source] It was not only the intellect of a people in its prime that was excised, but the treasure of a people in its potential.”
    —Cynthia Ozick (b. 1928)

    “I have known a number of Don Juans who were good studs and who cavorted between the sheets without a psychiatrist to guide them. But most of the busy love-makers I knew were looking for masculinity rather than practicing it. They were fellows of dubious lust.”
    —Ben Hecht (1893–1964)

    “To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
    —Albert Camus (1913–1960)

    “O! O! another stroke! that makes the third.
    He stabs me to the heart against my wish.
    If that be so, thy state of health is poor;
    But thine arithmetic is quite correct.”
    —A.E. (Alfred Edward)