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
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:
“... unless the actor is able to discourse most eloquently without opening his lips, he lacks the prime essential of a finished artist.”
—Julia Marlowe (1870–1950)
“Cultivated labor drives out brute labor. An infinite number of shrewd men, in infinite years, have arrived at certain best and shortest ways of doing, and this accumulated skill in arts, cultures, harvestings, curings, manufactures, navigations, exchanges, constitutes the worth of our world to-day.”
—Ralph Waldo Emerson (1803–1882)
“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)
“I hope I may claim in the present work to have made it probable that the laws of arithmetic are analytic judgments and consequently a priori. Arithmetic thus becomes simply a development of logic, and every proposition of arithmetic a law of logic, albeit a derivative one. To apply arithmetic in the physical sciences is to bring logic to bear on observed facts; calculation becomes deduction.”
—Gottlob Frege (1848–1925)