Editing Prime number theorem (section)

== Prime number theorem for arithmetic progressions ==
Let {{math|''π''<sub>''d'',''a''</sub>(''x'')}} denote the number of primes in the [[arithmetic progression]] {{math|''a'', ''a'' + ''d'', ''a'' + 2''d'', ''a'' + 3''d'', ...}} that are less than {{mvar|x}}. Dirichlet and Legendre conjectured, and de la Vallée Poussin proved, that if {{mvar|a}} and {{mvar|d}} are [[coprime]], then
: <math>\pi_{d,a}(x) \sim \frac{ \operatorname{Li}(x) }{ \varphi(d) } \ ,</math>
where {{mvar|φ}} is [[Euler's totient function]]. In other words, the primes are distributed evenly among the residue classes {{math|[''a'']}} [[modular arithmetic|modulo]] {{mvar|d}} with {{math|gcd(''a'', ''d'') {{=}} 1}}&nbsp;. This is stronger than [[Dirichlet's theorem on arithmetic progressions]] (which only states that there is an infinity of primes in each class) and can be proved using similar methods used by Newman for his proof of the prime number theorem.<ref>{{cite web |first=Ivan |last=Soprounov |year=1998 |title=A short proof of the Prime Number Theorem for arithmetic progressions |publisher=[[Cleveland State University]] |citeseerx=10.1.1.179.460 |place=Ohio |url=https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3A3AC2628B7212E6FC4392A189008AE7?doi=10.1.1.179.460&rep=rep1&type=pdf}}</ref>

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

Bennett ''et al.''<ref>{{cite journal | first1 = Michael A. | last1 = Bennett | first2 = Greg | last2 = Martin | first3 = Kevin | last3 = O'Bryant | first4 = Andrew | last4 = Rechnitzer | title = Explicit bounds for primes in arithmetic progressions | journal = Illinois J. Math. | volume = 62 | issue = 1–4 | date = 2018 | pages = 427–532 | doi = 10.1215/ijm/1552442669 | arxiv = 1802.00085 | s2cid = 119647640 }}</ref>
proved the following estimate that has explicit constants {{mvar|A}} and {{mvar|B}} (Theorem 1.3):
Let {{mvar|d}} <math>\ge 3</math> be an integer and let {{mvar|a}} be an integer that is coprime to {{mvar|d}}. Then there are positive constants {{mvar|A}} and {{mvar|B}} such that
: <math> \left | \pi_{d,a}(x) - \frac{\ \operatorname{Li}(x)\ }{\ \varphi(d)\ } \right | < \frac{A\ x}{\ (\log x)^2\ } \quad \text{ for all } \quad x \ge B\ ,</math>
where
: <math> A = \frac{1}{\ 840\ } \quad \text{ if } \quad 3 \leq d \leq 10^4 \quad \text{ and } \quad A = \frac{1}{\ 160\ } \quad \text{ if } \quad d > 10^4 ~,</math> 
and
: <math>B = 8 \cdot 10^9  \quad \text{ if } \quad  3 \leq d \leq 10^5 \quad \text{ and } \quad B = \exp(\ 0.03\ \sqrt{d\ }\ (\log{d})^3 \ ) \quad \text{ if } \quad d > 10^5\ .</math>

=== Prime number race ===
[[File:Chebyshev bias.svg|thumb|Plot of the function <math>\ \pi(x;4,3)-\pi(x;4,1) \ </math> for {{math|''n'' ≤ {{val|30000}}}}]]

Although we have in particular
: <math>\pi_{4,1}(x) \sim \pi_{4,3}(x) \ ,</math>
empirically the primes congruent to 3 are more numerous and are nearly always ahead in this "prime number race"; the first reversal occurs at {{math|''x'' {{=}} 26861}}.<ref name="Granville Martin MAA">
{{cite journal
 | doi = 10.2307/27641834
 | last1 = Granville | first1 = Andrew | author1-link = Andrew Granville
 | last2 = Martin | first2 = Greg
 | year = 2006
 | title = Prime number races
 | journal = [[American Mathematical Monthly]]
 | volume = 113 | issue = 1 | pages = 1–33
 | jstor = 27641834 | mr = 2202918
 | url = http://www.dms.umontreal.ca/%7Eandrew/PDF/PrimeRace.pdf
}}</ref>{{Rp|1–2}} However Littlewood showed in 1914<ref name="Granville Martin MAA"/>{{Rp|2}} that there are infinitely many sign changes for the function
: <math>\pi_{4,1}(x) - \pi_{4,3}(x) ~,</math>
so the lead in the race switches back and forth infinitely many times. The phenomenon that {{math|''π''<sub>4,3</sub>(''x'')}} is ahead most of the time is called [[Chebyshev's bias]]. The prime number race generalizes to other moduli and is the subject of much research; [[Pál Turán]] asked whether it is always the case that {{math|''π''<sub>''c'',''a''</sub>(''x'')}} and {{math|''π''<sub>''c'',''b''</sub>(''x'')}} change places when {{mvar|a}} and {{mvar|b}} are coprime to {{mvar|c}}.<ref name=GuyA4>{{cite book |last=Guy | first=Richard K. | author-link=Richard K. Guy | year=2004 | title=Unsolved Problems in Number Theory | publisher=[[Springer-Verlag]] |edition=3rd |isbn=978-0-387-20860-2 | zbl=1058.11001 | at=§A4, p. 13–15}}  This book uses the notation {{math|''π''(''x'';''a'',''c'')}} where this article uses {{math|''π''<sub>''c'',''a''</sub>(''x'')}} for the number of primes congruent to {{mvar|a}} modulo {{mvar|c}}.</ref> [[Andrew Granville|Granville]] and Martin give a thorough exposition and survey.<ref name="Granville Martin MAA" />
[[File:Prime race of last digit up to 10000.png|thumb|Graph of the number of primes ending in 1, 3, 7, and 9 up to {{math|''n''}} for {{math|''n'' < {{val|10000}}}}]]
Another example is the distribution of the last digit of prime numbers. Except for 2 and 5, all prime numbers end in 1, 3, 7, or 9. Dirichlet's theorem states that asymptotically, 25% of all primes end in each of these four digits. However, empirical evidence shows that, for a given limit, there tend to be slightly more primes that end in 3 or 7 than end in 1 or 9 (a generation of the Chebyshev's bias).<ref>{{cite journal |last1=Lemke Oliver |first1=Robert J. |last2=Soundararajan |first2=Kannan |date=2016-08-02 |title=Unexpected biases in the distribution of consecutive primes |journal=Proceedings of the National Academy of Sciences |language=en |volume=113 |issue=31 |pages=E4446-54 |doi=10.1073/pnas.1605366113 |doi-access=free |issn=0027-8424 |pmc=4978288 |pmid=27418603 |arxiv=1603.03720 |bibcode=2016PNAS..113E4446L }}</ref> This follows that 1 and 9 are [[quadratic residue]]s modulo 10, and 3 and 7 are quadratic nonresidues modulo 10.