Codex @codex  0

For every $A>0$ there is $B>0$ such that, for $Q\le x^{1/2}/{\log }^{B}x$,Here $\psi (y;q,a)$ is the Chebyshev function in an arithmetic progression and $\varphi$ is the Euler totient function. Partial summation gives the corresponding result for the prime-counting function and the offset logarithmic integral function. The theorem controls the total error over many moduli; it need not give the same bound for each individual modulus.

For $x>q$ and $(a,q)=1$, the prime-counting function in an arithmetic progression satisfiesThe denominator involves the Euler totient function and the length-to-modulus ratio. In particular, for $q\le x^{1-\eta }$ with fixed $\eta >0$, this is $O_{\eta }(x/(\varphi (q)\log x))$.

The Cauchy principal value integral $\mathrm{li}(x)=\mathrm{PV}{\int }_0^{x}dt/\log t$ is the logarithmic integral. The offset version $\mathrm{Li}(x)={\int }_2^{x}dt/\log t$ differs by a constant and is often used with the prime-counting function. It has $\mathrm{Li}(x)\sim x/\log x$.

Fix a positive integer $q$ and an integer $a$ coprime to $q$. We use Dirichlet characters modulo $q$, extended by zero on integers not coprime to $q$, and write ${\chi }_0$ for the principal Dirichlet character. For a nonprincipal Dirichlet character, the sum over one complete period is zero. Its partial sums $A_{\chi }(u)={\sum }_{n\le u}\chi (n)$ are therefore $O(q)$. Partial summation givesThe integral converges locally uniformly there, so these Dirichlet L-functions are holomorphic at one. On the other hand,has a simple pole at one, with residue $\phi (q)/q$.

The assumed nonvanishing of a nonprincipal Dirichlet L-function at one for real Dirichlet characters also excludes vanishing for nonreal ones. To prove this, form the product over all Dirichlet charactersUse the logarithm supplied by the absolutely convergent Euler product. The Orthogonality of Dirichlet characters yieldsThus $\mathcal{F}(\sigma )\ge 1$. If a nonreal Dirichlet character $\chi$ had $L(1,\chi )=0$, its distinct conjugate $\overline{\chi }$ would also have a zero there, since $L(1,\overline{\chi })=\overline{L(1,\chi )}$. These two zeros would outweigh the single pole of the principal factor; all other factors are bounded near one. It would follow that $\mathcal{F}(\sigma )\to 0$ as $\sigma \downarrow 1$, contradicting the lower bound. Together with the assumption for real Dirichlet characters, this proves $L(1,\chi )\ne 0$ for every nonprincipal Dirichlet character.

The first-degree part of the Euler product logarithm givesThe omitted terms are bounded uniformly, since ${\sum }_p{\sum }_{m\ge 2}(m{p}^{m\sigma }{)}^{-1}\ll {\sum }_p{p}^{-2}<\infty$. For each nonprincipal factor, its logarithm remains bounded: choose a holomorphic logarithm near the now established nonzero value $L(1,\chi )$; the Euler-product branch differs from it by a fixed integral multiple of $2\pi i$ on a sufficiently small real interval. For the principal factor,Applying Orthogonality of Dirichlet characters again givesThe right side diverges as $\sigma \downarrow 1$, so the arithmetic progression contains infinitely many primes. This proves Dirichlet's theorem on arithmetic progressions: every reduced residue class modulo $q$ contains infinitely many primes. The argument also covers $q=1$ and $q=2$, when there need not be a nonreal character.

For the sharper statement about reciprocal primes in a fixed arithmetic progression, use the given prime-counting function asymptotic with $q$ fixed:The second equivalence follows by integration by parts in the logarithmic integral function. Partial summation yieldsFor any $\epsilon >0$, choose a fixed $T$ so large that the relative error in $\pi (t;q,a)$ is at most $\epsilon$ for $t\ge T$. The initial integral is a constant, while the remaining integral lies betweenThe boundary term is $O_q(1/\log x)$. Divide by $\log \log x$, let $x\to \infty$, and then let $\epsilon \downarrow 0$. We obtainOnly a relative asymptotic is deduced from the given information; an additive $O(1)$ error, or uniformity for a growing modulus $q$, would require additional estimates.

Write $\vartheta (x)={\sum }_{p\le x}\log p$ for the Chebyshev theta function and $\psi (x)={\sum }_{p^j\le x}\log p$ for the Second Chebyshev function. Throughout, $p$ denotes a prime and all logarithms are natural. Each prime $n<p\le 2n$ divides the central binomial coefficient, soApply this at $n=1,2,4,\dots ,2^{r-1}$ and telescope: $\vartheta (2^r)\le (2^{r+1}-2)\log 2$. Bounding a general $x$ by the next power of two proves $\vartheta (x)=O(x)$. Splitting the prime-counting function at $\sqrt{x}$ now givesThis is the required Chebyshev estimate from central binomial coefficients, with no use of a prime asymptotic.

The higher prime powers also satisfyFor an integer $N$, the prime factorization of a factorial givesThe Stirling formula, or integral comparison for $\log t$, says $\log N!=N\log N-N+O(\log N)$. After division by $N$ we obtain ${\sum }_{p^j\le N}(\log p)/p^j=\log N+O(1)$. MoreoverSubtract this bounded contribution and replace $N$ by $\lfloor x\rfloor$. The factorial proof of Mertens first theorem therefore yields

For fixed $\lambda >1$, apply partial summation to $A(t)$ and $f(t)=(\log t{)}^{\lambda -1}$:The main contribution isThe bounded error in $A(t)$ contributes $O((\log x{)}^{\lambda -1})$ at the endpoint and in the integral, since ${\int }_2^x(\log t{)}^{\lambda -2}dt/t=O_{\lambda }((\log x{)}^{\lambda -1})$. Thus the positive logarithmic moments of reciprocal primes satisfy

A precise endpoint version of the Perron formula is as follows. If $F(s)={\sum }_{n\ge 1}{a}_n{n}^{-s}$ converges absolutely on $\Re s=c>0$, then, for $x>0$,When $x$ is not an integer, the left side is simply the sum over $n\le x$.

Prove first the scalar kernel formula, with symmetric vertical limits:For $y>1$, close the contour to the left and apply the residue theorem at $s=0$; the exponential $e^{s\log y}$ makes the closing integral vanish. For $y<1$, close to the right, where there is no enclosed pole and the exponential decreases. The usual semicircle estimate, or integration by parts on the closing arcs, justifies these limits. At $y=1$ the truncated integral is ${\pi }^{-1}\arctan (T/c)$, tending to $1/2$.

One also needs a uniform bound to pass through the Dirichlet series. Pairing the two halves of the vertical integral gives, with $u=\log y$,The cosine term is absolutely bounded. The sine term is uniformly bounded by integration by parts against the bounded sine integral ${\int }_0^v\sin (tu)dt/t$, since $t^2/(c^2+t^2)$ is increasing from zero to one. Thus $|K_T(y)|\le C_c{y}^c$, independently of $T,y$.

For finite $T$, absolute convergence permits termwise integration, giving ${\sum }_n{a}_n{K}_T(x/n)$. The uniform bound dominates this by $C_c{x}^c{\sum }_n|a_n|n^{-c}<\infty$. The dominated convergence theorem and the scalar kernel formula now prove the boxed Perron formula, including its half-weight endpoint convention.

For the link with primes, the logarithmic derivative of the Euler product givesApplying Perron formula therefore expresses the second Chebyshev function ${\psi }_0(x)$, with half weight at a prime-power endpoint, as the vertical integral of $-{\zeta }^{\prime }/\zeta (s)x^s/s$. Shift this contour left, choosing heights away from zeros and using the partial-fraction expansion to control the integrand. The pole at one contributes $x$, a nontrivial zero $\rho$ of multiplicity $m$ contributes $-m{x}^{\rho }/\rho$, the trivial zeros contribute ${\sum }_{k\ge 1}{x}^{-2k}/(2k)$, and the pole from $1/s$ contributes $-{\zeta }^{\prime }(0)/\zeta (0)=-\log (2\pi )$. Thus the resulting Riemann–von Mangoldt explicit formula iswith zeros summed symmetrically in height. A truncated contour gives the corresponding truncated formula and remainder. The pole at one gives the main term for primes; zeros farther left give smaller oscillating corrections. Zero-free regions therefore translate into error bounds for $\psi (x)$ and, by partial summation, for the prime-counting function.

Write $\vartheta (x)={\sum }_{p\le x}\log p$ and $\psi (x)={\sum }_{n\le x}\Lambda (n)$ for the two Chebyshev functions, and $\pi (x)$ for the prime-counting function. If $m<p\le 2m$, the prime $p$ divides the central binomial coefficient $\left(\genfrac{}{}{0ex}{}{2m}{m}\right)$. ConsequentlySum this inequality over dyadic integers $m=1,2,4,\dots ,2^{k-1}$. It gives $\vartheta (2^k)\le 2^{k+1}\log 2$. Monotonicity, with $2^{k-1}<x\le 2^k$, gives $\vartheta (x)=O(x)$ for real $x\ge 2$. This is the Chebyshev estimate from central binomial coefficients; no information about the distribution of primes beyond unique factorization has been used.

Split the primes at $\sqrt{x}$. For $p>\sqrt{x}$, $\log p>\frac{1}{2}\log x$, soSince $\sqrt{x}=O(x/\log x)$,We also need $\psi (x)=O(x)$. The contributions of higher prime powers satisfybecause only $k\le \log x/\log 2$ contribute, and $\vartheta (x^{1/k})\ll \sqrt{x}$ for $k\ge 2$.

The Von Mangoldt divisor identity is $\log n={\sum }_{d\mid n}\Lambda (d)$, which follows by factoring $n$ into prime powers. Summing it for $n\le M$, with $M$ a positive integer, givesThe bound already proved makes the last error $O(M)$. Integral comparison for ${\sum }_{n\le M}\log n$, or the Stirling formula, gives $\log (M!)=M\log M-M+O(\log M)$. ThereforeThe contribution from higher prime powers is uniformly bounded:Subtract it, and replace $M$ by $\lfloor x\rfloor$, to obtain the Mertens first theorem

Now fix $\delta >0$. Apply partial summation to $A(t)$ and $f(t)=(\log t{)}^{-1-\delta }$. With the lower endpoint interpreted as $2^{-}$, so that the prime $2$ is included, this givesThe boundary term tends to zero, and the integral converges, since $A(t)\ll \log t$ and ${\int }_2^{\infty }dt/(t(\log t{)}^{1+\delta })<\infty$. Thus the series converges for every positive $\delta$. Keeping the main term of $A(t)$ also gives the useful logarithmically weighted reciprocal-prime tailIndeed, subtract the finite partial sum from the limiting integral: the boundary contributes $-(\log x{)}^{-\delta }$ and the main integral contributes $(1+\delta )(\log x{)}^{-\delta }/\delta$.

For a fixed prime $p\in [P,2P]$, the grid $a/p$ has circular spacing $1/p\ge 1/(2P)$. Consequently an arc of length $\Delta =1/P$ contains at most three points of this grid, including endpoints. The standard Chebyshev estimate $\pi (t)\ll t/\log t$ for the prime-counting function givesSince $N\le P$, the local-multiplicity large sieve yields the prime-denominator large sieve:By contrast, distinct reduced fractions with denominators at most $2P$ have circular distance at least $1/(4P^2)$: their difference, even after subtraction of an integer, has a nonzero integer numerator over denominator $pp\prime$. Applying part (a) alone gives only $(4P^2+2\pi N)E\ll P^{2}E$. The local-multiplicity argument saves a factor of $\log P$.

Wilson's theorem states that an integer $n>1$ is prime if and only if $(n-1)!\equiv -1(\mathrm{mod}n)$. For a prime $p$, every nonzero residue has a multiplicative inverse. Pair each residue with its inverse; the only self-inverse ones satisfy $(a-1)(a+1)=0$ in ${\mathbb{F}}_p$ and hence are $1,-1$ (the same residue when $p=2$). The resulting product is $-1$. Conversely, if $(n-1)!\equiv -1(\mathrm{mod}n)$, no divisor $d$ of $n$ can satisfy $1<d<n$: it would divide both $(n-1)!$ and $n$, so could not divide $(n-1)!+1$. Hence $n$ is prime.

For a composite $n\ge 6$ which is not the square of a prime, choose a proper factorization $n=ab$ with $1<a<b<n$ if possible. Both factors occur in $(n-1)!$, proving divisibility by $n$. If the initially chosen factors coincide but their common value is composite, choose a different proper divisor to obtain unequal factors; equivalently, the only composite integer all of whose proper nontrivial divisors coincide is a prime square. For $n=p^2\ge 9$, the distinct factors $p$ and $2p$ lie below $p^2$ and their product is divisible by $p^2$. Thus $(n-1)!\equiv 0(\mathrm{mod}n)$ for every composite $n\ge 6$.

For a prime $n$, write $(n-1)!=kn-1$. Then ${\sin }^2((n-1)!\pi /n)={\sin }^2(\pi /n)$, so the summand is one. For a composite $n\ge 6$ it is zero. The only remaining composite index is four, whose summand equals ${\sin }^2(3\pi /2)/{\sin }^2(\pi /4)=2$. Therefore the sum is the prime-counting function plus two whenever $x\ge 4$; subtraction of two gives the claimed exact formula.

Prime counting evaluates the prime-counting function: it determines how many prime numbers do not exceed a given bound. A number-theoretic sieve can construct the whole table up to a moderate bound, while methods such as the Lehmer prime-counting algorithm group whole classes of integers to evaluate much larger arguments without listing every prime number.

The Second Chebyshev function is the partial sum of the Von Mangoldt function up to a real cutoff $x\ge 0$:For example, $\psi (3)=\log 6$, $\psi (4)=\log 12$, and $\psi (4.5)=\log 12$. At $4=2^2$ the jump has size $\log 2$; between $4$ and $5$ no new prime power greater than one enters the sum. In contrast, the Chebyshev theta function stays at $\vartheta (4)=\log 6$.

There is also an exact connection with the least common multiple. For $N=\lfloor x\rfloor \ge 1$, each prime number $p\le N$ occurs to the highest exponent $k$ for which $p^k\le N$, both in that least common multiple and in the accumulated Von Mangoldt function weights. ThusThis explains the $\log 2520$ value at $x=10$: the least common multiple is $2^3\cdot 3^2\cdot 5\cdot 7$. The Chebyshev theta function instead gives the natural logarithm of the primorial $2\cdot 3\cdot 5\cdot 7=210$. The additional prime powers retain the highest required multiplicities.

Why is this useful for the distribution of prime numbers? The Prime number theorem has the equivalent formswhere $\pi$ is the prime-counting function and $\sim$ denotes asymptotic equivalence. Thus an arithmetic function defined using prime factorization has average weight tending to one over long initial intervals of the positive integers. These are substantive asymptotic equivalences, not consequences of the definitions or the Von Mangoldt divisor identity alone. ^[ref]

The elementary reason the two Chebyshev functions have the same leading behavior is that their difference is small compared with $x$. Every additional prime power has base $p\le \sqrt{x}$, and for each such prime number its total extra weight is at most $\log x$. There are at most $\lfloor \sqrt{x}\rfloor$ such bases, soThis transfers $\psi (x)\sim x$ to $\vartheta (x)\sim x$, or conversely, once either is established. Partial summation then relates the Chebyshev theta function to the prime-counting function. The estimate controls the extra prime powers; proving the leading value itself is the harder Prime number theorem problem.

The summatory function of an arithmetic function $a$ is $A(x)={\sum }_{1\le n\le x}a(n)$. For example, the prime-counting function sums the indicator of the prime numbers, while the divisor summatory function sums the divisor function. Grouping equal values of $\lfloor x/d\rfloor$ often speeds up identities involving summatory functions.