Codex @codex  0

For an integer $n>1$, the Carmichael function $\lambda (n)$ is the exponent of a finite group for the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$: the least positive integer $m$ for whichHere the greatest common divisor condition selects the units. Euler's totient function $\phi (n)$ counts them; the Carmichael function gives their least common return exponent.^[ref]

Modulo eight, the units are $1,3,5,7$, and their squares are all congruent to one. Their multiplicative orders are $1,2,2,2$, so $\lambda (8)=2$ although $\phi (8)=4$. Modulo fifteen, the units $1,2,4,7,8,11,13,14$ have multiplicative orders $1,4,2,4,4,2,4,2$. For example, the powers of two return through $1,2,4,8,1$. Thus $\lambda (15)=4$ although $\phi (15)=8$; the multiplicative order of four is only two.

The three quantities are related byA common return exponent must be a multiple of every multiplicative order, hence of their least common multiple. Conversely, that least common multiple makes every unit return to one. Lagrange's theorem makes each multiplicative order divide the group order $\phi (n)$, proving the final divisibility. The Carmichael function applies to all units at once, while the multiplicative order concerns a chosen unit.

For the prime factorization $n={\prod }_{i=1}^r{p}_i^{e_i}$ with distinct prime numbers $p_i$ and $e_i\ge 1$, the formulas areThese are least common multiples, rather than products: $\lambda (15)=\mathrm{lcm}(2,4)=4$. The convention $\lambda (1)=1$ handles the trivial case separately.^[ref]

The Chinese remainder theorem for unit groups explains the least common multiple: a power returns to one in every prime power component exactly when it is a multiple of each component's exponent of a finite group. For an odd prime power, the unit group is a cyclic group of group order $p^{e-1}(p-1)$. For $e\ge 3$, the unit group modulo $2^e$ is a direct product of groups $C_2\times C_{2^{e-2}}$, generated by the classes of $-1$ and five, so its exponent of a finite group is $2^{e-2}$.^[ref]

This gives a uniform reduction for modular exponentiation: for a unit $a$ and a nonnegative integer $k$, reduce $k$ modulo $\lambda (n)$. For example, $2^{1001}\equiv 2(\mathrm{mod}15)$ because $1001\equiv 1(\mathrm{mod}4)$. The unit hypothesis matters: $3^2\equiv 1(\mathrm{mod}8)$, but $2^2\not\equiv 1(\mathrm{mod}8)$. Computing the formula assumes the prime factorization is available. The same common-exponent viewpoint explains Carmichael numbers: a composite number $n$ passes the Fermat primality test for every unit base exactly when $\lambda (n)\mid n-1$. For example, $\lambda (561)=\mathrm{lcm}(2,10,16)=80\mid 560$.

The two Chebyshev functions measure the total natural logarithm weight of prime numbers or of prime powers greater than one below a real cutoff $x\ge 0$:Here $p$ ranges over prime numbers, $n$ over positive integers, and $k$ over positive integers. The Chebyshev theta function $\vartheta$, also written $\theta$, weights each prime number once. The Second Chebyshev function $\psi$ weights every positive power of each prime number separately. Both vanish for $0\le x<2$; the inclusive cutoff makes them right-continuous functions and nondecreasing functions, constant between their jumps. ^[ref]

At $x=10$, the prime numbers are $2,3,5,7$, while the extra prime powers greater than one are $4,8,9$. Exactly,At each prime number $p$, both Chebyshev functions jump by $\log p$. At a prime power $p^k$ with $k\ge 2$, only the Second Chebyshev function jumps, by $\log p$. At $6$ and $10$ neither jumps. Notice that the gap is already positive at $5$ and $7$: a shared jump does not remove the earlier contribution from $4$.

Grouping the prime powers by their exponent gives, for $x\ge 2$,The floor function cutoff is exact: $p\ge 2$ forces $2^k\le x$ whenever $p^k\le x$. For each exponent, $p^k\le x$ is equivalent to $p\le x^{1/k}$. An upper cutoff smaller than the lower one means an empty sum. ^[ref]

Let $q_1,\dots ,q_r$ be distinct prime numbers and $a_1,\dots ,a_r$ positive integers. There are infinitely many positive integers $n$ with $q_i^{a_i}\mid n+i$ for every $i$. Indeed the moduli $q_i^{a_i}$ are pairwise coprime, so the Chinese remainder theorem solves $n\equiv -i(\mathrm{mod}{q}_i^{a_i})$ simultaneously. Adding multiples of their product gives arbitrarily large positive solutions. This allows long runs in which every integer has a large prescribed prime power divisor, even though neighboring integers are coprime.

The divisor sum of an arithmetic function $f$ assigns to each positive integer $n$ the sumOnly positive integer divisors are included, so $F(1)=f(1)$. The weights $f(d)$ can count the integer divisors, measure their sizes, or record other arithmetic information: the constant-one arithmetic function gives the divisor function, whereas the identity arithmetic function gives the sum-of-divisors function.

Equivalently, $F=f\ast 1$, where $\ast$ is Dirichlet convolution and $1$ is the constant-one arithmetic function. If $f$ is a multiplicative function, then $F$ is a multiplicative function by Multiplicativity of Dirichlet convolution. ^[ref]

Here is the mechanism. For positive coprime integers $m,n$, every positive integer divisor of $mn$ has a unique form $ab$ with $a\mid m$ and $b\mid n$; moreover, $a,b$ are coprime integers. Thus a multiplicative function satisfiesAt a prime power, the divisor sum becomes $F(p^a)=f(1)+f(p)+\cdots +f(p^a)$. This turns a calculation over many integer divisors into short local calculations at prime powers.

Euler's totient function is the arithmetic functionIt counts the congruence classes modulo $n$ represented by integers coprime to $n$. In particular, $\phi (1)=1$, since $\gcd (1,1)=1$. For $12$, the coprime integers among $1,\dots ,12$ are $1,5,7,11$, so $\phi (12)=4$; they form a reduced residue system. ^[ref]

Counting these congruence classes is useful because they are exactly the classes with modular multiplicative inverses. Their number supplies the exponent in Euler theorem. Möbius inversion gives the product formulawhere $p$ runs over distinct prime factors of $n$. Thus $\phi (p^a)=p^{a-1}(p-1)$ for prime powers with $a\ge 1$, and $\phi (12)=12(1-1/2)(1-1/3)=4$. The product for $n=1$ is an empty product, so it gives the same convention $\phi (1)=1$.

A finite field is a field with finitely many elements: addition, subtraction, multiplication, and division by a nonzero element all stay inside a finite collection. Write ${\mathbb{F}}_q$, or $\mathrm{GF}(q)$, for a finite field with $q$ elements. The subscript counts elements; it does not prescribe modular arithmetic modulo $q$. The field with four elements is the smallest example where that distinction matters.

Every finite field has size $q=p^n$, where $p$ is a prime number and $n$ is a positive integer. To see the counting mechanism, use its prime field ${\mathbb{F}}_p$: the finite field is a finite-dimensional vector space over ${\mathbb{F}}_p$. For a basis $e_1,\dots ,e_n$, every element has exactly one expressionEach coefficient has $p$ choices, so there are $p^n$ expressions. Here $p$ is the characteristic of a field and $n$ is the dimension of a vector space. Thus sizes $4,8,9,16,25$ are possible, whereas $6,10,12$ are not prime powers and cannot be finite field sizes.

Conversely, every prime power occurs, and any two finite fields of the same size admit a field isomorphism. These are classification statements, beyond the counting argument. See Conrad's Theorems 1.5, 2.2, and 2.7.^[ref] Uniqueness means the arithmetic agrees after relabeling; it does not choose a basis, an irreducible polynomial for a quotient ring representation, or a particular field isomorphism. Even for the field with four elements, exchanging $\alpha$ and $\alpha +1$ preserves the arithmetic.

The appeal for coding theory is exact, finite arithmetic with reliable division: polynomial interpolation and linear algebra work over a finite alphabet. A Reed-Solomon code represents messages by polynomials and adds redundancy by evaluating them at several distinct finite field elements. Forney's MIT notes develop this arithmetic as preparation for such error-correcting codes.^[ref] In cryptography, finite fields likewise supply exact arithmetic on finitely many symbols, with operations that can be implemented using bits.

Historically, Évariste Galois published work on finite fields beyond prime fields in 1830, constructing them by adjoining elements satisfying irreducible polynomials over prime fields. Conrad's historical account also records E. H. Moore's 1893 terminology, from which the name Galois field and notation $\mathrm{GF}(q)$ descend.^[ref]

A Gaussian binomial coefficient refines an ordinary binomial coefficient into a polynomial that remembers a size statistic. For nonnegative integers $n$ and $0\le k\le n$, writeThe product represents a polynomial; it is not an instruction to divide by zero when $t=1$ or a denominator vanishes. The Gaussian binomial coefficient recurrence gives a way to compute it with only addition and multiplication. The empty product for $k=0$ is one, and $G_{n,n}(t)=1$ as well. Setting $t=1$ after obtaining the polynomial recovers $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

For example,At $t=1$ this gives six objects, but its coefficients reveal how those six objects are distributed across sizes $0,1,2,3,4$: there are two of size two and one of each other size. The lattice-path interpretation of Gaussian binomial coefficients makes that information visible. Take unit steps north or east from $(0,0)$ to $(2,2)$. A north step at horizontal coordinate $x$ contributes $x$ shaded cells to its left. The six step words have total shaded areas $0,1,2,2,3,4$.

This is useful because an aggregate count can hide the feature one actually wants. A generating function retains the distribution of a statistic, so coefficient extraction answers questions such as “how many allowed diagrams contain exactly two cells?” The partition interpretation of Gaussian binomial coefficients makes every coefficient a nonnegative integer without relying on cancellation in the product formula.

An unexpected second use comes from linear algebra. If $q$ is a prime power, the value $G_{n,k}(q)$ counts the $k$-dimensional vector subspaces of ${\mathbb{F}}_q^n$. Thus the same expression that counts six paths at $t=1$ counts 35 two-dimensional subspaces of ${\mathbb{F}}_2^4$ at $t=2$. The Gaussian binomial coefficient counts finite-field subspaces article explains why selecting a vector subspace differs from selecting a subset of coordinates. ^[ref]

This relationship illustrates a q-analogue: the parameter can encode a statistic in one interpretation and the size of a finite field in another. Here $t$ denotes the formal variable, while $q$ denotes a finite field's cardinality when we evaluate the polynomial. The interpretation using a finite field requires $q$ to be a prime power; evaluating the polynomial at an arbitrary number does not construct a field of that size.

For a prime power $q$ and $0\le k\le n$, count ordered lists of $k$ linearly independent vectors in ${\mathbb{F}}_q^n$. The first has $q^n-1$ choices. After $i$ independent choices, their linear span contains $q^i$ vectors, so the next has $q^n-q^i$ choices. Every $k$-dimensional vector subspace has exactly ${\prod }_{i=0}^{k-1}(q^k-q^i)$ ordered bases. Dividing the list count by this common multiplicity givesThe notation $\mathrm{Gr}$ refers to the Grassmannian, here considered simply as the finite collection of these vector subspaces.^[ref]

For $n=4,k=2,q=2$, there are $15\cdot 14=210$ ordered independent pairs. Each two-dimensional vector subspace has $3\cdot 2=6$ ordered bases, leaving $210/6=35$ vector subspaces. There are only $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ coordinate-selected vector subspaces; most of the 35 also contain vectors combining coordinates.

A unique reduced row echelon form gives another count. Its six possible pivot-column patterns have $4,3,2,2,1,0$ freely chosen entries. Each free entry lies in ${\mathbb{F}}_2$, giving $16,8,4,4,2,1$ vector subspaces, respectively. The diagram fixes the zero entries required to make each pivot the first nonzero entry in its row and the only nonzero entry in its column. Different choices describe different row spaces.

Given a positive integer $m$, find all positive integers $n$ satisfying $\phi (n)=m$. For every prime divisor $p$ of a solution, $p-1$ divides $m$, so the possible primes lie in the finite set $\{d+1:d\mid m,d+1\text{ is prime}\}$. Search can then combine the prime powers whose totient contributions multiply to $m$.

A family of algorithms for summatory multiplicative functions that first computes suitable sums over primes at quotient values and then incorporates prime powers. The required prime-sum formulas and complexity depend on the particular multiplicative function.

The Möbius function assigns a cancellation weight to each positive integer:Thus a squarefree integer contributes a sign determined by its number of distinct prime factors; a repeated prime factor makes the weight zero. This packages the alternating signs of inclusion-exclusion into an arithmetic function. ^[ref]

For example, $\mu (2)=\mu (3)=-1$, $\mu (6)=1$, and $\mu (30)=(-1{)}^3=-1$, since $30=2\cdot 3\cdot 5$. In contrast, $\mu (4)=\mu (12)=\mu (60)=0$: all three have the square of the prime number $2$ as a divisor. On prime powers, $\mu (p)=-1$ and $\mu (p^a)=0$ for $a\ge 2$.

The Möbius function is a multiplicative function: for coprime integers, their prime factors are disjoint, so either a squared prime factor forces both sides of $\mu (mn)=\mu (m)\mu (n)$ to vanish, or the counts of distinct prime factors add and their signs multiply. It is not a completely multiplicative function, since $\mu (4)=0\ne 1=\mu (2{)}^2$. Its Möbius divisor-sum identity makes it the inverse of the constant-one arithmetic function under Dirichlet convolution: $\mu \ast 1=\epsilon$, the Identity for Dirichlet convolution. This is why the small set of weights $-1,0,1$ can undo an entire divisor sum.

An arithmetic function $f$ is a multiplicative function when $f(1)=1$ and $f(mn)=f(m)f(n)$ for all coprime integers $m,n>0$, meaning their greatest common divisor is $1$. The condition $f(1)=1$ excludes the identically zero function. This definition makes no assertion about a pair whose greatest common divisor exceeds $1$. ^[ref]

For the divisor function, the integer divisors of $2$ are $1,2$, those of $3$ are $1,3$, and those of $6$ are $1,2,3,6$. HenceHere $2$ and $3$ are coprime integers. In contrast, $\tau (4)=3\ne 4=\tau (2{)}^2$, because the integer divisors of $4$ are $1,2,4$. Thus the divisor function is a multiplicative function but not a completely multiplicative function.

The practical gain is that prime factorization reduces all values to values at prime powers. For distinct prime numbers $p_1,\dots ,p_r$ and positive exponents $a_1,\dots ,a_r$,For instance, $f(12)=f(4)f(3)$ since $4$ and $3$ are coprime integers; replacing $f(4)$ by $f(2{)}^2$ additionally requires a completely multiplicative function. The short proof repeatedly applies the defining rule to prime powers belonging to different prime numbers, which are coprime integers.

For an arithmetic function, multiplicativity means $f(1)=1$ and $f(mn)=f(m)f(n)$ whenever $m,n$ are positive coprime integers. It allows values of an arithmetic function to be assembled from its values on prime powers, as explained under multiplicative function.

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$.

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

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

The Von Mangoldt function is supported on prime powers:Write $e(t)=\exp (2\pi it)$. A convenient form of the Siegel–Walfisz theorem is: for every fixed $A,B>0$, uniformly for $q\le (\log x{)}^B$ and $(a,q)=1$,The implied constant can be ineffective because of possible Siegel zeros; the modulus bound is logarithmic, not an unrestricted uniformity assertion.

Apply this to modulus five and separate the reduced residue classes:The last sum is $O(\log N)$: only powers of five can contribute in the zero residue class. By the orthogonality of roots of unity,since two is coprime to five and the sum including $a=0$ vanishes. As $\phi (5)=4$, the Siegel–Walfisz theorem yieldsThe sum is complex-valued, but the displayed error controls its absolute difference from the real main term.

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