We will prove the statement about coprime random integers, or at least we will prove as much of it as we can without discussing infinite combinations of independent chances. We will also make an assumption about distribution of primes to simplify the proof; one can consider this a sketch, if necessary.

First, we know that \(\gcd(x,y)=1\) is true precisely if \(x\) and \(y\) are never simultaneously congruent to zero modulo \(p\), for any prime \(p\). (If there were such a \(p\), of course it would be a divisor; by the Fundamental Theorem of Arithmetic we need only consider primes.)

For any given prime \(p\), the chances that two integers will both be congruent to zero is \begin{equation*}\left(\frac{1}{p}\right)\left(\frac{1}{p}\right)\, .\end{equation*} This works because the probabilities are independent, since \(p\) is fixed, so we can just multiply probabilities.

Hence the probability that at least one of \(x\) or \(y\) will not be divisible by \(p\) is \begin{equation*}1-\left(\frac{1}{p}\right)\left(\frac{1}{p}\right)=1-\frac{1}{p^2}=1-p^{-2}\, .\end{equation*} (This may remind you of the so-called birthday problem in probability.)

Now comes our assumption. We will suppose that if \(p \neq q\) are both prime, then the probability that any given integer is divisible by \(p\) has nothing to do with whether it is divisible by \(q\). (Such properties are not true in general; if \(n\) is divisible by 4 it has a 100% likelihood of being divisible by 2, while if \(n\) is prime, it has almost no chance of being even.)

In such a case the probabilities are independent, so that (even in this infinitary case) \begin{equation*}\prod_p (1-p^{-2})=1/\prod_p \frac{1}{1-p^{-2}}=1/\zeta(2)=\frac{6}{\pi^2}\, .\end{equation*}

With all the tools we've gained, the proof is nearly completely symbolic at this point!

First, we have the following from the definition of Moebius in Definition 23.1.1, or from Fact 24.5.5: \begin{equation*}\sum_{n=1}^{\infty}\frac{|\mu(n)|}{n^s}=\prod_p\left(1+\frac{1}{p^s}\right)\, .\end{equation*}

Next, let us write \(x=\frac{1}{p^s}\); then we can use the basic identity \((1+x)=\frac{1-x^2}{1-x}\) to rewrite the right-hand side as \begin{equation*}\prod_p\left(1+\frac{1}{p^s}\right)=\frac{\prod_p\left(1-\frac{1}{p^{2s}}\right)}{\prod_p\left(1-\frac{1}{p^s}\right)}\; .\end{equation*} Now we just invert both numerator and denominator to get familiar friends: \begin{equation*}\frac{\prod_p\left(1-\frac{1}{p^{2s}}\right)}{\prod_p\left(1-\frac{1}{p^s}\right)}=\frac{\prod_p 1/(1-\frac{1}{p^s})}{\prod_p 1/(1-\frac{1}{p^{2s}})}\end{equation*} which means the sum will be \(\zeta(s)/\zeta(2s)\).

This is a fairly expanded form of the proofs in [C.1.1, Theorem 9.2] and [C.3.6, Theorem 1.13].

As with many other occasions to prove series divergence, we will focus on the ‘tail’s beyond a point that keeps getting further out. In this case, we'll choose the ‘tail’ beyond the first \(k\) primes, \begin{equation*}T = \sum_{n>k}\frac{1}{p_n}\, .\end{equation*} By examining certain terms in this, and assuming (falsely) that it can be made finite, we will obtain a contradiction.

First, let's consider numbers of the form \begin{equation*}p_1 p_2 p_3\cdots p_k r+1=p_k\#\cdot r+1\end{equation*} (Recall the primorial notation from Definition 22.2.6.) Such a number cannot be divisible by any of those first \(k\) primes, so by the Fundamental Theorem of Arithmetic any number like \(p_k\#\cdot r+1\) may be factored as \begin{equation*}p_{n_1}p_{n_2}\cdots p_{n_{\ell}}\; ,\end{equation*} where all \(n_i>k\) (some may be repeated).

Return to the ‘tail’. Since this \(p_k\#\cdot r+1\) factors with \(\ell\) factors, then somewhere in the \(\ell\)th power of the ‘tail’ we have the following term: \begin{equation*}T^\ell = \left(\sum_{n>k}\frac{1}{p_n}\right)^{\ell} = \frac{1}{p_1 p_2 p_3\cdots p_k r+1}+ \cdots \; .\end{equation*}

Now assume that in fact the prime harmonic series converges; we will derive a contradiction.

First, for some \(k\), the ‘tail’ \(T\) is less than \(\frac{1}{2}\), i.e. \(T =\sum_{n>k}\frac{1}{p_n}<\frac{1}{2}\). Since each term is positive, \(T>0\) and a geometric series involving the \(\ell\)th powers of \(T\) is very precisely bounded: \begin{equation*}0\leq \sum_{\ell=1}^{\infty}T^{\ell}=\sum_{\ell=1}^{\infty}\left(\sum_{n>k}\frac{1}{p_n}\right)^{\ell}\leq \sum_{\ell=1}^{\infty}\frac{1}{2^{\ell}}=2\, .\end{equation*}

Now we bring in the first discussion in this proof; every single term of the form \(\frac{1}{p_1 p_2 p_3\cdots p_k r+1}\) will appear somewhere within this sum of the \(\ell\)th powers, though naturally \(\ell\) in each case will depend heavily upon \(r\).

So the series of reciprocals of just these special terms is bounded. \begin{equation*}0<\sum_{r=1}^{\infty}\frac{1}{p_1 p_2 p_3\cdots p_k r+1}\leq \sum_{\ell=1}^{\infty}\left(\sum_{n>k}\frac{1}{p_n}\right)^{\ell}\leq 2\, .\end{equation*} A bounded series of all positive number should converge (e.g. by comparison).

Here comes the contradiction. The same series is bounded below as follows, for each integer \(k\). \begin{equation*}\sum_{r=1}^{\infty}\frac{1}{p_1 p_2 p_3\cdots p_k r+1}>\sum_{r=1}^{\infty}\frac{1}{p_1 p_2 p_3\cdots p_k r+p_1 p_2 p_3\cdots p_k}\end{equation*}\begin{equation*}=\frac{1}{p_1 p_2 p_3\cdots p_k}\sum_{r=1}^{\infty}\frac{1}{r+1}\end{equation*}This series certainly diverges, as a multiple of the tail of the harmonic series!

Since no matter how big \(k\) is (and hence how far out in the ‘tail’ we go) we report that a certain series both converges and diverges, we have a contradiction. Hence our original assumption that we could choose \(k\) to make \(T\) finite was false, and the prime harmonic series must diverge!

Consider the summation function for \(\phi\), \(\sum_{k=1}^n\phi(n)\). As in Chapter 20, we will think of it as summing things up in two different ways.

In particular, look at the summation once we have replaced with the Moebius sum inside: \begin{equation*}\sum_{k=1}^n\phi(k)=\sum_{k=1}^n\sum_{d\mid k}\mu(d)\frac{k}{d}\end{equation*} Now instead of considering it as a sum over divisors for each \(k\), we can think of it as summing for each divisor over the various hyperbolas \(xy=k\). This yields\begin{equation*}\sum_{k=1}^n\sum_{d\mid k}\mu(d)\frac{k}{d}=\sum_{d=1}^n\mu(d)\left(\sum_{k=1}^{\lfloor \frac{n}{d}\rfloor}k\right)\end{equation*}

Now let's examine the terms of this sum. We will several times use Landau notation as in Definition 20.1.1.

Knowing about the sum of the first few consecutive integers (also used at the end of Subsection 20.3.2), we see that \begin{equation*}\left(\sum_{k=1}^{\lfloor \frac{n}{d}\rfloor}k\right)=\frac{1}{2}\left(\frac{n}{d}\right)^2+O\left(\frac{n}{d}\right)\; .\end{equation*} If we plug that in the double sum, we get \begin{equation*}\sum_{k=1}^n\phi(n)=\frac{1}{2}n^2\sum_{d=1}^n\frac{\mu(d)}{d^2}+nO\left(\sum_{d=1}^n\frac{\mu(d)}{d}\right)\; .\end{equation*}

Let's examine this.

• The first term goes to \(\frac{6}{\pi^2}\) as \(n\to\infty\). Further, its error is \(O(1/n)\), because \(\mu(n)/n^2<1/n^2\) and \(\int x^{-2}\, dx=-x^{-1}\).

• The second term is certainly \(O(n\log(n))\), since it is \(n\) times a sum which is less than something \(O(\log(n))\) (namely, \(\zeta\)).

Plugging everything in, we get that \begin{equation*}\sum_{k=1}^n\phi(n) = \frac{1}{2}n^2\frac{6}{\pi^2}+O(\text{ stuff less than }n^2)\end{equation*} Dividing by \(n\) and taking the limit, we get the asymptotic result. \begin{equation*}\lim_{n\to\infty}\frac{\frac{1}{n}\sum_{k=1}^n\phi(n)}{\frac{3}{\pi^2}n}\end{equation*}\begin{equation*}=\lim_{n\to\infty} \frac{ \frac{1}{2}\frac{n^2}{n}\frac{6}{\pi^2} +\frac{1}{n}O(\text{stuff less than }n^2)} {\frac{3}{\pi^2}n}\end{equation*}\begin{equation*}=\lim_{n\to\infty}\frac{\frac{3}{\pi^2}n+O(\text{ stuff less than }n)}{\frac{3}{\pi^2}n}=1\; .\end{equation*}