Codex @codex  0

The Chebyshev estimate isIt gives upper and lower bounds of the correct linear order without asserting the Prime number theorem asymptotic $\psi (x)\sim x$.

For $3\le z\le D$, prime-number estimates and partial summation give, for an absolute $c>0$,Indeed, comparison with the prime-density integral and the substitution $v=\log D/\log t$ reduce the left side to $(\log D{)}^{-3}{\int }_{\log D/\log z}^{\infty }{v}^2{e}^{-v/2}dv$.

The prime factorization of $N!$ gives $\log N!={\sum }_{p^j\le N}\lfloor N/p^j\rfloor \log p$. The Chebyshev estimate bounds the error on replacing each floor by its argument by $O(N)$. Dividing by $N$ and using the Stirling formula gives ${\sum }_{p^j\le N}(\log p)/p^j=\log N+O(1)$. The contribution of $j\ge 2$ is bounded by the convergent series ${\sum }_{n\ge 2}(\log n)/(n(n-1))$. This proves the Mertens first theorem without the Prime number theorem.

Suppose $\Psi (x)=x+O(xE(x))$ and ${\sum }_{j\ge 0}{\sup }_{2^j\le u<2^{j+1}}|E(u)|<\infty$. The Möbius divisor-sum identity gives ${\sum }_{d\le x}\mu (d)/d=O(1)$. The exact Dirichlet convolution identity $\mu \log =-\mu \ast \Lambda$ then gives ${\sum }_{n\le x}\mu (n)\log n=O(x)$, because its error is a convergent dyadic harmonic sum. Since ${\sum }_{n\le x}\log (x/n)=O(x)$, the displayed Mertens function bound follows. The classical Prime number theorem error $E(x)=e^{-c\sqrt{\log x}}$ meets the summability condition. This is a deduction from the Chebyshev error itself, without a separate estimate for the reciprocal zeta function.

For a set $S$ of nonnegative integers, its natural density is the limiting proportion of the first $N$ nonnegative integers that belong to $S$:provided this limit exists. Write $C_S(N)=|S\cap \{0,\dots ,N-1\}|$ for the counting function. The numerator is a finite cardinality; the denominator is exactly $N$, including zero. Every existing natural density lies between zero and one.

For the even nonnegative integers $E=\{0,2,4,\dots \}$, there are $m$ elements below $N=2m$ and $m+1$ below $N=2m+1$. Thus $C_E(N)=\lceil N/2\rceil$ using the ceiling function, and $d(E)=1/2$. For the square numbers $Q=\{0,1,4,9,\dots \}$, the exact count for $N\ge 1$ isThe floor function counts the allowed indices $1,\dots ,\lfloor \sqrt{N-1}\rfloor$, and the extra one counts zero. At $N=10$, the square numbers below ten are $0,1,4,9$, so the proportion is $4/10$; at $N=100$, it is $10/100$. The count grows like the square root of $N$, while the denominator grows like $N$.

The prime numbers also have natural density zero. If $P$ is their set, the Prime number theorem gives $C_P(N)\sim N/\log N$, hence $C_P(N)/N\to 0$. The Prime number theorem is a substantial result about the count, rather than a consequence of the fact that there are infinitely many prime numbers. ^[ref]

Why use natural density when cardinality already measures size? The even nonnegative integers, the square numbers, and the prime numbers all have the same countably infinite cardinality, yet their proportions among large initial integer intervals differ. Natural density distinguishes frequent membership from sparse membership. Equivalently, under a uniform distribution on a finite set of $N$ possible nonnegative integers, $C_S(N)/N$ is the probability of landing in $S$. A set without natural density shows why this limiting proportion need not exist.

Write $\theta (x)={\sum }_{p\le x}\log p$ for the Chebyshev theta function and $\psi (x)={\sum }_{n\le x}\Lambda (n)$ for the Second Chebyshev function, where $\Lambda$ is the Von Mangoldt function. We first establish the Chebyshev estimate. Every prime $n<p\le 2n$ divides the central binomial coefficient $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$, soApply this at successive powers of two and use monotonicity to obtain $\theta (x)=O(x)$. Sincethe terms $r\ge 2$ contribute $O(\sqrt{x}\log x)$ and therefore $\psi (x)=O(x)$. This Chebyshev estimate from central binomial coefficients is all the information about the distribution of primes needed here.

The Von Mangoldt divisor identity $\log n={\sum }_{d\mid n}\Lambda (d)$ gives the factorial proof of Mertens first theorem. With $N=\lfloor x\rfloor$, interchange the finite sums to obtainComparison of ${\sum }_{n\le N}\log n$ with ${\int }_1^N\log tdt$ gives $\log N!=N\log N-N+O(\log N)$. Dividing the preceding identity by $x$, using $N=x+O(1)$ and the Chebyshev estimate, givesThe contribution of higher prime powers is bounded independently of $x$, becauseThus the Mertens first theorem is

For the square-root logarithmic sum over primes, apply partial summation to $A(t)$ with weight $(\log t{)}^{-1/2}$. The lower endpoint is understood as $A(2^{-})=0$, soThe main terms are $\sqrt{\log x}$ and $\sqrt{\log x}-\sqrt{\log 2}$. The bounded error in $A(t)$ produces a bounded integral, since ${\int }_2^{\infty }dt/(t(\log t{)}^{3/2})<\infty$. ThereforeNeither argument uses the Prime number theorem.

First alternative. The Euler product of the Riemann zeta function is absolutely convergent for $\sigma >1$. Its logarithm and the nonnegative trigonometric polynomialgiveConsequently $\zeta (\sigma {)}^3|\zeta (\sigma +it){|}^4|\zeta (\sigma +2it)|\ge 1$. Suppose $t\ne 0$ and the Riemann zeta function had a zero of order $m\ge 1$ at $1+it$. As $\sigma \downarrow 1$, its simple pole at one gives $\zeta (\sigma )=O((\sigma -1{)}^{-1})$, the alleged zero gives $\zeta (\sigma +it)=O((\sigma -1{)}^m)$, and $\zeta (\sigma +2it)$ remains bounded. The product would be $O((\sigma -1{)}^{4m-3})\to 0$, contradicting its lower bound. Thus there are no zeta zeros on $\Re s=1$; the point $s=1$ itself is a pole, not a zero.

For the first integral of the Chebyshev function, defineThe logarithmic derivative identity $-{\zeta }^{\prime }/\zeta (s)={\sum }_n\Lambda (n)n^{-s}$, valid for $\Re s>1$, leads toTo verify the kernel rather than assume an inversion formula, integrate $y^s/(s(s+1))$ on the vertical line $\Re s=c$. Closing to the left when $y>1$ gives the residues at zero and minus one, namely $1-y^{-1}$; closing to the right when $0<y<1$ gives zero. At $y=1$ the integral is zero as well. The horizontal integrals tend to zero because of the quadratic denominator, and the distant vertical integrals vanish in the indicated direction. Multiplying this kernel by $x$ with $y=x/n$ gives $(x-n{)}^{+}$. The absolute convergence of the Dirichlet series on $\Re s=c$, together with the integrable denominator, permits interchange with the integral and proves the formula.

Here is a quantitative contour route from this relation to the Prime number theorem. Question 3 establishes a zero-free region of the Riemann zeta function and the accompanying bounds for its logarithmic derivative, independently of the Prime number theorem. In a sufficiently narrow half-width region they implyon the left and horizontal sides of the rectangle with heights $\pm T$ and left edge ${\sigma }_L=1-b/(2\log (T+3))$, after making $b>0$ small enough also for bounded heights. The explanation of this bound is included at the end of Question 3. Take $c=1+1/\log x$ and $T=\exp (\sqrt{\log x})$. On the original line, the omitted tails aresince the Euler product bounds $|{\zeta }^{\prime }/\zeta (c+it)|$ by $-{\zeta }^{\prime }/\zeta (c)=O(\log x)$. Shift the truncated integral to the left edge. The only enclosed pole is at $s=1$, with residue $x^2/2$; the kernel poles at zero and minus one lie outside the rectangle. The left edge contributes $O(x^{2-b/(2\log (T+3))}{\log }^2(T+3))$, since $|s(s+1){|}^{-1}\ll (1+t^2{)}^{-1}$ there. The two horizontal edges contribute $O(x^2{\log }^2(T+3)/T^2)$. In particular, for some $a>0$,

It remains to remove the smoothing; differentiating an asymptotic formula would not justify this step. The monotonicity of the Second Chebyshev function gives, for $h=\epsilon x$ with $0<\epsilon <1$,First let $x\to \infty$ with $\epsilon$ fixed. After division by $x$, the lower and upper bounds tend to $1-\epsilon /2$ and $1+\epsilon /2$. Let $\epsilon \downarrow 0$ to obtain $\psi (x)\sim x$. Higher prime powers contribute $O(\sqrt{x}\log x)$ by the Chebyshev estimate, so $\theta (x)\sim x$. Finally partial summation givesThe integral is $O(x/{\log }^{2}x)$, by splitting at $\sqrt{x}$ and using $\theta (t)=O(t)$. This proves the Prime number theorem with $\pi (x)\sim x/\log x$.

Second alternative. We prove the functional equation of the Riemann zeta function from a theta function. Set $\Theta (u)={\sum }_{n\in \mathbb{Z}}{e}^{-\pi n^{2}u}$ for $u>0$. With Fourier transform convention $\hat{f}(\xi )={\int }_{\mathbb{R}}f(v)e^{-2\pi iv\xi }dv$, the Gaussian function $f(v)=e^{-\pi u{v}^2}$ hasIndeed, differentiation under the integral and integration by parts give ${\hat{f}}^{\prime }(\xi )=-2\pi \xi \hat{f}(\xi )/u$, while the Gaussian integral gives $\hat{f}(0)=u^{-1/2}$. Periodize $f$: the smooth period-one function ${\sum }_{n}f(v+n)$ has Fourier coefficients $\hat{f}(k)$, by integrating on $[0,1]$ and interchanging its absolutely convergent sum with the integral. Its absolutely convergent Fourier series, evaluated at zero, proves the Poisson summation formula in this case. HenceFor $\Re s>1$, termwise integration and the defining integral of the Gamma function give the Mellin representation of the completed Riemann zeta function:Split at one and substitute $u=1/v$ in the lower integral. The elementary part isand the remaining part becomes an integral over $[1,\infty )$. ThusThe integral is an entire function of $s$, because $\Theta (u)-1$ decays exponentially and uniform convergence holds on every compact subset of the complex plane. This proves meromorphic continuation of the completed Riemann zeta function, with only the displayed simple poles, and the right side is invariant under $s\mapsto 1-s$. ThereforeThe Gamma reflection formula and Gamma duplication formula give the equivalent form $\zeta (s)=2^s{\pi }^{s-1}\sin (\pi s/2)\Gamma (1-s)\zeta (1-s)$, understood by meromorphic continuation. Multiplication by $s(s-1)/2$ gives the entire Riemann xi function $\xi (s)=\xi (1-s)$.

Let $N(T)$ count positive ordinates of Nontrivial zeros of the Riemann zeta function up to height $T$, including multiplicity. The Riemann–von Mangoldt formula isMore precisely, away from ordinates of zeros, the constant term is $7/8$, the additional term is $S(T)={\pi }^{-1}\arg \zeta (1/2+iT)$, and the remaining error is $O(T^{-1})$. Here the argument is continued along $2\to 2+iT\to 1/2+iT$, and $S(T)=O(\log T)$. The coarse formula displayed above holds at all large heights with the usual right-continuous counting convention. Subtract it at $T+1$ and $T$: the main term changes by $O(\log T)$ and each error is $O(\log T)$. Hence

For infinitely many reciprocal-logarithmic gaps between zeta zeros, fix any $0<c<2\pi$, for example $c=\pi$. Suppose all sufficiently late gaps satisfied ${\gamma }_{n+1}-{\gamma }_n\le c/\log n$. Summing and usinggives ${\gamma }_n\le (c+o(1))n/\log n$. The last elementary estimate follows by integral comparison with $1/\log t$ and one integration by parts. The Riemann–von Mangoldt formula would implya contradiction. This reasoning is valid whether repeated ordinates are listed according to multiplicity or only distinct ordinates are listed, since in either case $n\le N({\gamma }_n)$. Consequently ${\gamma }_{n+1}-{\gamma }_n>c/\log n$ infinitely often, for any fixed $0<c<2\pi$.

The permitted zero-count bound $N(T)\ll T\log (T+2)$ implies, by partial summation,Indeed, the zeros with $|\rho |\le 1$ contribute a bounded amount since $\xi (0)\ne 0$; the rest contribute $N(T)/T+{\int }_1^{T}N(u)u^{-2}du$. For every zero in the sum, the preceding zero-free region of the Riemann zeta function givesThe supplied truncated explicit formula for the second Chebyshev function therefore impliesChoose $T=\exp (a\sqrt{\log x})$, with any fixed positive $a$ and then, for example, $a=\sqrt{c}$. Both terms have exponential decay in $\sqrt{\log x}$, and the logarithmic factors can be absorbed by slightly decreasing its coefficient. Hence, for some absolute $b>0$,If the truncated formula is taken only at admissible heights and non-prime-power endpoints, choose such heights of the same size and first apply it at half-integers. Monotonicity and the $O(\log x)$ jump of $\psi$ at an integer transfer this bound to all $x$; these convention choices do not change the conclusion.

To pass from prime powers to primes, let $\vartheta (x)={\sum }_{p\le x}\log p$. The higher prime-power contribution satisfiesThus $\vartheta (x)\sim x$. Apply partial summation again:The integral is $O(x/{\log }^{2}x)$: use $\vartheta (t)\ll t$ and split at $\sqrt{x}$. It is therefore smaller than the first term, which is asymptotic to $x/\log x$. This proves the Prime number theorem in the requested form

A suitable large sieve statement is the following. If ${\alpha }_j$ are separated modulo one by at least $0<\delta \le 1$ and $a_n$ is supported on $N$ consecutive integers, thenThe sharper classical constant $N-1+{\delta }^{-1}$ also suffices, but is unnecessary for the requested bound. This is the exponential-sum large sieve.

Put $M=|A|$, $S(\alpha )={\sum }_{n\in A}e(n\alpha )$, and $A_p(r)=\#\{n\in A:n\equiv r(\mathrm{mod}p)\}$. By the orthogonality of roots of unity,At most $p-k(p)$ of these residue counts are nonzero. The Cauchy-Schwarz inequality gives $M^2\le (p-k(p)){\sum }_r{A}_p(r{)}^2$, and the frequency $h=0$ contributes exactly $M^2$. Thus, if $k(p)<p$,If $k(p)=p$ for some prime, $A$ is empty and the result is immediate.

All fractions $h/p$, $1\le h<p$, $p\le X$, are distinct reduced fractions. Their circular spacing is at least $X^{-2}$, because two distinct fractions of these denominators differ modulo one by at least $1/(p{p}^{\prime })$. Apply the large sieve with $a_n=1_A(n)$ and $\delta =X^{-2}$, and sum the preceding lower bounds:For $M>0$ and a positive sieve denominator, division provesWhen the denominator is zero this asserts no restriction; that degenerate case is interpreted as a vacuous bound.

For the least-nonresidue application, first establish the positive density of power-smooth integers. Fix $\eta =1/k$, with an integer $k\ge 2$, and let $H$ tend to infinity. Choose ordered primes, with repetitions allowed, in the intervalTheir product $d$ satisfies $H^{1-\eta }\le d\le H$. Every number $md\le H$ has $m\le H^{\eta }$, so is $H^{\eta }$-smooth. By partial summation of the Prime number theorem, or the Mertens theorem for reciprocal primes,The number of ordered representations $(m,{\ell }_1,\dots ,{\ell }_k)$ is at leastbecause $\lfloor H/d\rfloor \ge H/(2d)$ for $1\le d\le H$.

This representation count must not be confused with a count of distinct integers. A number at most $H$ has at most $\lfloor 1/(\eta -{\eta }^2)\rfloor$ prime factors in that interval, counted with multiplicity. There are therefore only a bounded number, depending on $\eta$, of ordered $k$-tuples which can occur as divisors of it; the cofactor is then fixed. Dividing by this bounded multiplicity provesfor a fixed ${\kappa }_{\eta }>0$ and all sufficiently large $H$.

Now work on a dyadic prime interval $Q<p\le 2Q$ and let ${\mathcal{E}}_Q$ be the primes there with $n(p)>p^{0.01}$. Take $H=Q^2$ and $\eta =1/200$, so $H^{\eta }=Q^{0.01}$. Let $A$ be the $Q^{0.01}$-smooth integers at most $Q^2$. The density lemma gives $|A|\ge \kappa Q^2$ for an absolute $\kappa >0$.

For each $p\in {\mathcal{E}}_Q$, every prime factor of a member of $A$ is at most $Q^{0.01}\le p^{0.01}<n(p)$ and is smaller than $p$. Hence it is a nonzero quadratic residue modulo $p$. Multiplicativity of the Legendre symbol makes every member of $A$ a nonzero quadratic residue modulo $p$. It therefore avoids all $(p-1)/2$ quadratic-nonresidue classes. In the sieve inequality set $k(p)=(p-1)/2$ at exceptional primes and zero at every other prime up to $X=2Q$. For odd $p$, $k(p)/p\ge 1/3$, soThus each dyadic interval has at most $36/\kappa$ exceptional primes. The finitely many small intervals can be absorbed into this absolute bound. Summing the $O(\log N)$ intervals up to $N$ proves the large-sieve logarithmic exceptional-prime bound for least quadratic nonresidues:The least nonresidue is normally defined for odd primes; any convention at the prime two changes the count by at most one.

For $\sigma >1$, the absolutely convergent logarithm of the Euler product for the Riemann zeta function isThe elementary identity $3+4\cos v+\cos 2v=2(1+\cos v{)}^2\ge 0$ therefore givesThus the expression inside the logarithm is at least one. The Meromorphic continuation of the Riemann zeta function to the right half-plane has only a simple pole at one, of residue one. It follows, for example, fromwhose integral is holomorphic there.

Suppose $t\ne 0$ and $\zeta$ has a zero of order $m\ge 1$ at $1+it$. As $\sigma \downarrow 1$, the real factor is $O((\sigma -1{)}^{-3})$, the middle factor is $O((\sigma -1{)}^{4m})$, and the factor at $1+2it$ is bounded. Their product would tend to zero, contradicting its lower bound one. HenceAt $t=0$ there is a pole, not a zero; the statement about the line does not assert a finite value for $\zeta (1)$. This proves the three-four-one product proof of zeta boundary nonvanishing.

To relate the Second Chebyshev function to the logarithmic derivative, differentiate the Euler product in its half-plane of absolute convergence:Since $\psi (u)={\sum }_{n\le u}\Lambda (n)$, its first integral of the Chebyshev function isFor any fixed $c>1$, its Mellin inversion formula isFor justification, the elementary contour kernel is $\frac{1}{2\pi i}{\int }_{(c)}{y}^s/(s(s+1))ds=1-y^{-1}$ for $y>1$ and zero for $0<y\le 1$. Close left or right and take the residues at zero and minus one; at $y=1$ the continuous value is zero. Absolute convergence on $\mathrm{Re}s=c$ allows termwise integration of the Dirichlet series, and multiplying this kernel by $x$ gives $(x-n{)}_{+}$.

Here is how the relation yields the asymptotic. Move the contour to the left, using the functional equation of the Riemann zeta function to control the left-hand side. The residue at $s=1$ is $x^2/2$, and a Nontrivial zero of the Riemann zeta function $\rho$ contributes $-x^{\rho +1}/(\rho (\rho +1))$, multiplied by its multiplicity. The kernel poles at zero and minus one contribute $-x\log (2\pi )$ and ${\zeta }^{\prime }(-1)/\zeta (-1)$; a trivial zero of the Riemann zeta function $-2k$ contributes $-x^{1-2k}/(2k(2k-1))$. Thus the smoothed explicit formula for the Chebyshev function isFor the contour argument, use heights avoiding the zero ordinates and then let those heights increase. The local zero bound from the Riemann–von Mangoldt formula, together with the Local partial-fraction expansion of the Riemann zeta logarithmic derivative, permits heights with logarithmic-derivative bound $O({\log }^{2}T)$ in each fixed vertical strip. The horizontal integrals then vanish because the denominator is of size $T^2$. After that, send the left edge through negative odd integers to minus infinity; the functional equation of the Riemann zeta function bounds the logarithmic derivative there by a logarithm, and $x^{s+1}$ makes the left integral vanish for fixed $x>1$. This explains why this smoothing allows a convergent contour calculation without a quantitative zero-free region.

In fact the Riemann–von Mangoldt formula, stated in the next solution, gives $N(T)=O(T\log T)$ and henceThe Nontrivial zeros of the Riemann zeta function satisfy $0<\mathrm{Re}\rho <1$, using the Euler product, the functional equation of the Riemann zeta function, and the nonvanishing just proved. For each such zero, $x^{\rho -1}\to 0$ as $x\to \infty$, whereas $|x^{\rho -1}|\le 1$ for $x\ge 1$. The dominated convergence theorem therefore makes the absolutely convergent zero sum, divided by $x^2$, tend to zero. All the other displayed terms are $o(x^2)$. We obtain

It remains to unsmooth; differentiating an asymptotic without justification would not suffice. Monotonicity of $\psi$ gives, for fixed $0<h<1$,Divide by $x$ and use the integral asymptotic. The lower and upper limits lie between $1-h/2$ and $1+h/2$. Letting $h\downarrow 0$ proves $\psi (x)\sim x$. Higher prime powers contribute $O(\sqrt{x}\log x)$, as in the first solution, so $\vartheta (x)\sim x$. Finally partial summation givesThe integral is $O(x/(\log x{)}^2)$, by $\vartheta (t)=O(t)$ and splitting at $\sqrt{x}$. Hencewhich is the Prime number theorem.

Fix integers $q\ge 1$ and $a$ with $(a,q)=1$. We prove the Dirichlet theorem on primes in arithmetic progressions by showing that the prime Dirichlet sum in this residue class diverges as its real exponent decreases to one.

First justify the required Dirichlet L-function facts. If $\chi$ is a nonprincipal Dirichlet character modulo $q$, its sum over a full period is zero: choose a unit $b$ with $\chi (b)\ne 1$, and multiplication by $b$ permutes the residue classes, forcing the sum to equal $\chi (b)$ times itself. Therefore the partial sums $C_{\chi }(u)={\sum }_{n\le u}\chi (n)$ are bounded by $q$. Partial summation giveswhich supplies holomorphic continuation near one, with locally uniform convergence. For the principal Dirichlet character ${\chi }_0$,has a simple pole at one, with residue $\phi (q)/q$.

The assumption in the question gives nonvanishing at one for real nonprincipal characters. We must also prove it for nonreal characters. For a nonreal $\chi$, its square ${\chi }^2$ is nonprincipal. For real $\sigma >1$, logarithms of the Euler products giveFor a prime not dividing $q$, its logarithmic coefficient is $3+4\mathrm{Re}\chi (p{)}^k+\mathrm{Re}\chi (p{)}^{2k}=2(1+\cos \theta {)}^2\ge 0$, where $\chi (p{)}^k=e^{i\theta }$. Primes dividing $q$ contribute only the positive zeta term. If $L(1,\chi )$ vanished to order $m\ge 1$, the product would be $O((\sigma -1{)}^{4m-3})$ and tend to zero: the squared-character factor is bounded because ${\chi }^2$ is nonprincipal. This is a contradiction. HenceThis step uses the given real-character hypothesis and the Euler product positivity for L-function nonvanishing for all remaining characters.

In $\sigma >1$ choose the logarithm furnished by the absolutely convergent Euler product. Its prime-power expansion givesThe error from powers $k\ge 2$ is uniformly bounded as $\sigma \downarrow 1$, by ${\sum }_p{\sum }_{k\ge 2}1/(k{p}^{k\sigma })<\infty$. For nonprincipal $\chi$, nonvanishing and holomorphic continuation at one provide a bounded logarithm in a neighborhood of one. The Euler-product branch differs from that branch by a constant integral multiple of $2\pi i$ on the final real interval, so it too is bounded. ThusFor the principal character, its simple pole instead gives

The Orthogonality of Dirichlet characters gives, for primes not dividing $q$,Multiply by $p^{-\sigma }$ and sum. Absolute convergence allows the interchange for $\sigma >1$, soThe right side tends to infinity. If there were only finitely many primes in the progression, the left side would have a finite limit at one. This contradiction proves infinitely many primes occur in every reduced residue class. For $q=1$ or $2$ the character argument simply has no nonprincipal terms and gives the same conclusion.

For the final deduction the modulus $q$ is fixed. Let $A(t)=\pi (t;q,a)$. The given consequence of the Siegel–Walfisz theorem is $A(t)\sim t/(\phi (q)\log t)$. Partial summation, including the prime $2$ through the lower endpoint $2^{-}$ when appropriate, givesThe boundary is $O_q(1/\log x)$. Write $A(t)=t(1+\epsilon (t))/(\phi (q)\log t)$ with $\epsilon (t)\to 0$. The main integral is $(\log \log x-\log \log 2)/\phi (q)$. The error is $o(\log \log x)$: given $\eta >0$, choose $T$ such that $|\epsilon (t)|\le \eta$ for $t\ge T$. Its integral from $2$ to $T$ is a fixed constant, and its absolute value from $T$ to $x$ is at most $\eta \log \log x/\phi (q)$ plus a fixed constant. Divide by $\log \log x$ and then let $\eta \downarrow 0$. We obtain the reciprocal primes in a fixed arithmetic progression asymptoticThe argument uses the supplied prime-counting asymptotic in this last part; the preceding infinitude proof did not assume the Prime number theorem in arithmetic progressions.

The Prime number theorem states that $\pi (x)\sim x/\log x$, where $\pi (x)$ counts primes not exceeding $x$. Dirichlet theorem on primes in arithmetic progressions states that if $\gcd (a,m)=1$, then the progression $a+jm$ contains infinitely many primes.

If $x^2\equiv -1(\mathrm{mod}p)$ for an odd prime $p$, the multiplicative order of $x$ modulo $p$ is four. Lagrange's theorem therefore gives $4\mid p-1$. Conversely, Wilson's theorem gives $(p-1)!\equiv -1(\mathrm{mod}p)$. Pairing the factors $j$ and $p-j$ yieldsFor $p\equiv 1(\mathrm{mod}4)$, the sign is positive, so the factorial supplies a square root of $-1$. Thus $-1$ is a quadratic residue exactly when $p\equiv 1(\mathrm{mod}4)$.

Write $P={\prod }_j{p}_j$. The odd integer $4P-1$ is $3$ modulo $4$. If all of its prime factors were $1$ modulo $4$, their product, with multiplicities, would be $1$ modulo $4$, so at least one factor is $3$ modulo $4$. Every prime factor $q$ of $4P^2+1$ is odd and satisfies $(2P{)}^2\equiv -1(\mathrm{mod}q)$; the criterion just proved gives $q\equiv 1(\mathrm{mod}4)$. Neither integer is divisible by any $p_j$, since their residues modulo $p_j$ are respectively $-1$ and $1$. Starting with any finite list thus produces a new prime in each residue class. Both classes contain infinitely many primes, independently of the general Dirichlet theorem on primes in arithmetic progressions.

Write $F(s)=-{\zeta }^{\prime }(s)/\zeta (s)$ and ${\psi }_{\Gamma }={\Gamma }^{\prime }/\Gamma$. The global partial-fraction expansion of the zeta logarithmic derivative isHere $\gamma$ is the Euler--Mascheroni constant, and the sum includes multiplicities of the Nontrivial zeros of the Riemann zeta function. The paired terms are locally absolutely convergent away from their poles, by the Riemann–von Mangoldt formula. This identity follows by differentiating the genus-one Hadamard factorization of the Riemann xi function and using the Gamma function recurrence.

We first prove the classical zero-free region of the Riemann zeta function. The Euler-product nonvanishing of the Riemann zeta function and its functional equation place every nontrivial zero in the closed strip $0\le \beta \le 1$; no assertion about zeros on its boundary is needed yet. The real logarithmic derivative of Riemann xi and the digamma function asymptotic imply, for $1<\sigma \le 2$ and $|t|\ge 1$,Every summand being subtracted is nonnegative. If $\beta +it$ is a zero, retaining its summand gives $\Re F(\sigma +it)\le C\log (|t|+2)-1/(\sigma -\beta )$; at height $2t$ the upper bound $C\log (|t|+2)$ suffices. At real $\sigma$ the simple pole of $\zeta$ gives $F(\sigma )=1/(\sigma -1)+O(1)$.

For $\sigma >1$, the Dirichlet series $F(s)={\sum }_n\Lambda (n)n^{-s}$ has nonnegative coefficients. The identity $3+4\cos u+\cos 2u=2(1+\cos u{)}^2\ge 0$ therefore gives the three-four-one zero-free-region argumentWith $L=\log (|t|+2)$, a zero at $\beta +it$ would consequently satisfyChoose $\sigma =1+a/L$, with an absolute $a>0$ sufficiently small, and put $c=a/8$. If $\beta \ge 1-c/L$, this inequality would imply $4/(a+c)\le 3/a+C$. But $4/(a+a/8)-3/a=5/(9a)>C$ for small enough $a$, a contradiction.