Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

7.1: Introduct to Analytic Number Theory

  • Page ID
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    It is well known that the harmonic series \(\sum_{n=1}^{\infty}\frac{1}{n}\) diverges. We therefore determine some asymptotic formulas that determines the growth of the \(\sum_{n\leq x}\frac{1}{n}\). We start by introducing Euler’s summation formula that will help us determine the asymptotic formula.

    We might ask the following question. What if the sum is taken over all the primes. In this section, we show that the sum over the primes diverges as well. We also show that an interesting product will also diverge. From the following theorem, we can actually deduce that there are infinitely many primes.

    Definition: Euler’s Summation Formula

    If \(f\) has a continuous derivative on an interval \([a,b]\) where \(a> 0\), then \[\sum_{a<n\leq b}f(n)=\int_{a}^bf(t)dt+\int_{a}^b(\{t\})f'(t)dt+f(b)(\{b\})-f(a)(\{a\}).\] where \(\{t\}\) denotes the fractional part of \(t\).


    For the proof of Euler’s summation formula see .

    If \(x\geq 1\), we have that: \[\sum_{n\leq x}\frac{1}{n}=\log x+\gamma+O\left(\frac{1}{x}\right)\]

    We use Euler’s summation formula by taking \(f(t)=1/t\). We then get

    \[\begin{aligned} \sum_{n\leq x}\frac{1}{n}&=&\int_{1}^x\frac{1}{t}dt-\int_1^x\frac{\{t\}}{t^2}dt+1+O\left(\frac{1}{x}\right)\\ &=& \log x+1-\int_1^{\infty}\frac{\{t\}}{t^2}dt+\int_x^{\infty}\frac{\{t\}}{t^2}dt+O\left(\frac{1}{x}\right)\end{aligned}\]

    Notice now that \(\{t\}\leq t\) and hence the two improper integrals exist since they are dominated by integrals that converge. We therefore have

    \[0\leq \int_x^\infty\frac{\{t\}}{t^2}dt\leq \frac{1}{x},\]

    we also let


    and we get the asymptotic formula.

    Notice that \(\gamma\) is called Euler’s constant. Notice also that similar steps can be followed to find an asymptotic formulas for other sums involving powers of \(n\).

    We now proceed to show that if we sum over the primes instead, we still get a divergent series.

    Both \(\sum_p\frac{1}{p}\) and \(\prod_p(1-\frac{1}{p})\) diverge.

    Let \(x \geq 2\) and put \[P(x)=\prod_{p\leq x}\left(1-\frac{1}{p}\right)^{-1}, \ \ \ S(x)=\sum_{p\leq x}\frac{1}{p}\] Let \(0<u<1\) and \(m\in \mathbb{Z}\), we have


    Now taking \(u=\frac{1}{p}\), we get

    \[\frac{1}{1-\frac{1}{p}}>1+\frac{1}{p}+...+\left(\frac{1}{p}\right)^m\] As a result, we have that \[P(x)>\prod_{p\leq x}\left(1+\frac{1}{p}+...+\frac{1}{p^m}\right)\]

    Choose \(m>0 \in \mathbb{Z}\) such that \(2^{m-1}\leq x\leq 2^m\). Observe also that

    \[\prod_{p\leq x}\left(1+\frac{1}{p}+...+\frac{1}{p^m}\right)=1+\sum_{p_i\leq x}\frac{1}{p_1^{m_1}p_2^{m_2}...}\]

    where \(1\leq m_i\leq m\). As a result, we get every \(\frac{1}{n}, n\in \mathbb{Z^+}\) where each prime factor of \(n\) is less than or equal to \(x\)(Exercise). Thus we have

    \[\prod_{p\leq x}\left(1+\frac{1}{p}+...+\frac{1}{p^m}\right)>\sum_{n=1}^{2^{m-1}}\frac{1}{n}>\sum_{n=1}^{[x/2]}\frac{1}{n}\]

    Taking the limit as \(x\) approaches infinity, we conclude that \(P(x)\) diverges.

    We proceed now to prove that \(S(x)\) diverges. Notice that if \(u>0\), then


    Thus we have

    \[\log(1/u-1)<u+\frac{u^2}{2}(1/1-u), \ \ \ 0<u<1.\]

    We now let \(u=1/p\) for each \(p\leq x\), then \[\log\left(\frac{1}{1-1/p}\right)-\frac{1}{p}<\frac{1}{2p(p-1)}\] Thus \[\log P(x)=\sum_{p\leq x}log(1/1-p).\] Thus we have \[\log P(x)-S(x)<\frac{1}{2}\sum_{p\leq x}\frac{1}{p(p-1)}<\frac{1}{2}\sum_{n=1}^{\infty}\frac{1}{n(n-1)}\] This implies that \[S(x)>\log P(x)-\frac{1}{2}\] And thus \(S(x)\) diverges as \(x\) approaches infinity.

    [1] For any arithmetic function \(f(n)\), we let \[A(x)=\sum_{n\leq x}f(n)\] where \(A(x)=0\) for \(x<1\). Assume also that \(g\) has a continuous derivative on the interval \([y,x]\), where \(0<y<x\). Then we have

    \[\sum_{y<n\leq x}f(n)g(n)=A(x)g(x)-A(y)g(y)-\int_y^xA(t)g'(t)dt.\]

    The proof of this theorem can be found in .


    1. Show that one gets every \(\frac{1}{n}, n\in \mathbb{Z^+}\) where each prime factor of \(n\) is less than or equal to \(x\) in the proof of Theorem 1.
    2. Write down the proof of Abel’s summation formula in details.


    • Dr. Wissam Raji, Ph.D., of the American University in Beirut. His work was selected by the Saylor Foundation’s Open Textbook Challenge for public release under a Creative Commons Attribution (CC BY) license.