Skip to main content

Section 3.4 Chebychev's Theorem

Let \(L, l\) be the common upper and lower limits of the three quotients \(\frac{\pi(x)\log(x)}{x},\) \(\frac{\theta(x)}{x}\) and \(\frac{\varphi(x)}{x}.\) Consider

\begin{equation*} N =\binom{2n}{n}. \end{equation*}

\(N\) is the greatest coefficient of the binomial expansion of \((1 + 1)^{2n},\) so that

\begin{equation} N\lt 2^{2n}\lt (2n + 1)N\text{.}\label{Eqn_3_2}\tag{3.4.1} \end{equation}

Now also \(N\) is divisible by all primes \(p\) in the interval \(n \lt p \leq 2n,\) and so by their product, thus

\begin{equation*} N\geq \prod_{n\lt p\leq 2n} p. \end{equation*}

This combined with (3.4.1) gives

\begin{equation*} 2n\log(2)\gt \log(N)\gt \sum_{n\lt p\leq 2n} \log(p)=\theta(2n)-\theta(n). \end{equation*}

Putting \(n=2^{r-1}\) and summing from \(r = 1\) to \(r = m\) gives

\begin{equation*} \sum_{r=1}^{m}2^r\log(2)\gt\sum_{r=1}^{m}\theta(2^r)-\theta(2^{r-1}) \end{equation*}

which in turn gives

\begin{equation*} \theta(2^m)\lt \sum_{r=1}^{m}2^r\log(2)\lt 2^{m+1}\log(2). \end{equation*}

If \(x\gt 1\) and \(m\) is an integer defined by \(2^{m-1}\leq x\lt 2^m,\) then

\begin{equation*} \theta(x)\lt \theta(2^m)\lt 2^{m+1}\log(2)\leq 4x\log(2). \end{equation*}

Division by \(x\) gives

\begin{equation*} \frac{\theta(x)}{x}\leq 4\log(2), \end{equation*}

so that \(L\leq 4\log(2).\)

For the other inequality, note that \(p\vert m!\) exactly \(\sum_{r=1}^{\infty}\left\lfloor\frac{m}{p^r}\right\rfloor\) times. Since

\begin{equation*} N=\binom{2n}{n}=\frac{(2n)!}{(n!)^2}, \end{equation*}

we have

\begin{equation*} N=\prod_{p\leq 2n} p^{\sum_{r=1}^{\infty}\left\lfloor\frac{2n}{p^r}\right\rfloor-2\sum_{r=1}^{\infty}\left\lfloor\frac{n}{p^r}\right\rfloor}. \end{equation*}

Each of the sums can be terminated at the \(M_p\)th term, where \(M_p=\left\lfloor\frac{\log(2n)}{\log(p)}\right\rfloor\) since for \(0\lt x\lt 1,\) \(\lfloor x\rfloor =0.\) This gives

\begin{equation*} \sum_{r=1}^{\infty} \left(\left\lfloor\frac{2n}{p^r}\right\rfloor-2\left\lfloor\frac{n}{p^r}\right\rfloor\right)\leq M_p \end{equation*}

since \(\lfloor 2x\rfloor-2\lfloor x\rfloor =0\) or \(1.\) Now

\begin{equation*} \prod_{p\leq 2n}p^{M_p}=\prod_{p\leq 2n}e^{M_p\log(p)}=\prod_{p\leq 2n}e^{\left\lfloor\frac{\log(2n)}{\log(p)}\right\rfloor\log(p)}=e^{\varphi(2n)}, \end{equation*}

so \(N\vert e^{\varphi(2n)}\) and the right inequality of (3.4.1) gives

\begin{equation*} 2n\log(2)-\log(2n+1)\lt \log(N)\lt \varphi(2n). \end{equation*}

Now if \(x\gt 2\) and \(n =\left\lfloor\frac{x}{2}\right\rfloor,\) then

\begin{equation*} \varphi(x)\geq\varphi(2n)\gt (x-2)\log(2)-\log(x-1). \end{equation*}

Dividing by \(x\) yields

\begin{equation*} \frac{\varphi(x)}{x}\gt \frac{x-2}{x}\log(2)-\frac{1}{x}\log(x-1). \end{equation*}

Since \(\frac{x-2}{x}\rightarrow 1\) and \(\frac{1}{x}\log(x-1)\rightarrow \) as \(x\rightarrow \infty,\) we have \(\log(2)\leq l.\) So there exists constants \(L,l,\) such that

\begin{equation*} l\frac{x}{\log(x)}\lt \pi(x)\lt L\frac{x}{\log(x)}. \end{equation*}

Let \(p_n\) be the \(n\)th prime. Chebychev's estimate for the Prime Number Theorem gives, for some \(a\lt 1,\)

\begin{equation*} \pi(x)\gt a\frac{x}{\log(x)}, \end{equation*}

for \(x\) sufficiently large. It follows that

\begin{equation*} n = \pi(p_n) \gt a\frac{p_n}{\log(p_n)}\gt \sqrt{p_n} \end{equation*}

for \(n\) sufficiently large. Now \(n^2\gt p_n\) gives \(\log(p_n)\lt 2\log(n),\) so

\begin{equation*} ap_n\lt n\log(p_n)\lt 2n\log(n) \end{equation*}

when \(n\) is large. Inverting and summing gives

\begin{equation*} 2\sum_{n=1}^{\infty}\frac{1}{p_n}\gt a\sum_{n=2}^{\infty}\frac{1}{n\log(n)}, \end{equation*}

and since the series on the right is divergent, by comparison, the sum of the reciprocals of the primes diverges.

Note that for \(\sigma\gt 1\) we have

\begin{equation*} \zeta(\sigma)=\prod_{p}\frac{1}{1-p^{-\sigma}}, \end{equation*}

so

\begin{align*} \log(\zeta(\sigma)) \amp =-\sum_{p}\log(1-p^{-\sigma})\\ \amp =\sum_{p}\sum_{n=1}^{\infty}\frac{1}{np^{n\sigma}}\\ \amp =\sum_{p}\frac{1}{p^{\sigma}}+\sum_{p}\sum_{n=2}^{\infty}\frac{1}{np^{n\sigma}}. \end{align*}

Since the series converge absolutely the rearrangement is permissible. Now for any prime \(p\) and \(\sigma\geq 1,\) \(1-1/p^{\sigma}\geq 1/2,\) so

\begin{align*} \sum_{p}\sum_{n=2}^{\infty}\frac{1}{np^{n\sigma}}\amp \lt \sum_{p}\sum_{n=2}^{\infty}\frac{1}{p^{n\sigma}}\\ \amp = \sum_{p}\frac{1}{p^{2\sigma}}\frac{1}{1-p^{-\sigma}}\\ \amp \leq 2\sum_{p}\frac{1}{p^{2\sigma}}\\ \amp \leq 2\zeta(2\sigma)\\ \amp \lt 2\zeta(2) \end{align*}

which shows that the double sum is bounded for any \(\sigma\geq 1.\) Thus

\begin{equation*} \log(\zeta(\sigma))=\sum_{p} \frac{1}{p^{\sigma}}+O(1). \end{equation*}

But \(\log(\zeta(\sigma))\rightarrow\infty\) as \(\sigma\rightarrow 1^{+},\) so that \(\sum_{p}\frac{1}{p^{\sigma}}\rightarrow\infty,\) and so

\begin{equation*} \sum_{p}\frac{1}{p} \end{equation*}

is divergent.

It is sufficient to show this for just two integers of this form. So let \(4n + 1, 4m + 1\in\mathbb{Z}.\) Then

\begin{equation*} (4n + 1)(4m + 1) = 16mn + 4m + 4n + 1 = 4(4mn + m + n) + 1, \end{equation*}

which is what we were trying to show.

Here we note that all odd numbers fall into two classes. They are either of the type \(4n + 1\) or \(4n + 3\) for integers \(n.\) It is interesting question to ask whether there are infinitely many primes of either type. The \(4n + 3\) case is easy enough for us, so we proceed thence.

This is similar to our previous theorem on the infinitude of primes. Toward a contradiction, suppose that are finitely many primes of the form \(4k + 3,\) say \(q_1, q_2,...,q_s.\) Consider the positive integer

\begin{equation*} n = 4q_1q_2...q_s-1 = 4(q_1q_2...q_s-1) + 3 \end{equation*}

with prime factorization \(n = d_1d_2...d_r.\) Because \(n\) is odd it has no even factors, thus \(d_i\) is odd for each \(i.\) Also, by the lemma if all of the prime factors of \(n\) where of the form \(4k + 1\) then n would be also. Thus there must exist a prime factor of \(n\) with the form \(4k + 3.\) This factor is not one of \(q_1, q_2,...,q_s,\) a contradiction. Thus there are infinitely many primes of the form \(4k + 3.\)