Exercise 6.1.8 ($\sum\limits_{(b,b') \in A} (bb')^{-1} = 1$ )

Proof. Consider the set

We must prove that $\underset{(b,b^{\prime })\in A}{\sum <!--\; FUNCTION\; APPLICATION\; -->}{(b{b}^{\prime })}^{-1}=1.$

By section 6.1, all the terms $b_j$ of the Farey sequence of order $n$ satisfy

This shows that all ordered pairs $(b_j,b_{j+1})$ are in $A$, so we may consider the map

• We prove that $\phi$ is surjective (onto). Let $(b,b^{\prime })\in A$, so that

  $$1\le b\le n,1\le b^{\prime }\le n,b\wedge b^{\prime }=1,b+b^{\prime }>n.$$
  • Consider first the particular case $b^{\prime }=1$. Then $b+b^{\prime }>n$ implies $b=n$. By Problem 5, $a_{k-1}∕b_{k-1}=(n-1)∕n$, and $a_k∕b_k=1∕1$, therefore $(b,b^{\prime })=(n,1)=(b_{k-1},b_k)=\phi (k-1)$.

  • We suppose now that $b^{\prime }>1$.

    Since $b\wedge b^{\prime }=1$, there are integers $u,v$ such that $\mathit{bv}-u{b}^{\prime }=1$. Then for all integers $\lambda$,

    $$b(v-\lambda b^{\prime })-(u-\mathit{\lambda b})b^{\prime }=1.$$

    We take for $\lambda$ the quotient of the Euclidean division of $v$ by $b^{\prime }$, so that

    $$v=\lambda b^{\prime }+a^{\prime },0\le a^{\prime }<b^{\prime }.$$

    Then $a^{\prime }=v-\lambda b^{\prime }$ and $0\le a^{\prime }<b^{\prime }$. Put $a=u-\mathit{\lambda b}$. Then

    $$b{a}^{\prime }-a{b}^{\prime }=1,\frac{a}{b}<\frac{a^{\prime }}{b^{\prime }}<1.$$

    It remains to show that $a\ge 0$. If $a<0$ then $1=b{a}^{\prime }-a{b}^{\prime }\ge -a{b}^{\prime }=|a|b^{\prime }>1$ (because $b^{\prime }>1$). This is a contradiction, thus $a\ge 0$, so

    $$0\le \frac{a}{b}<\frac{a^{\prime }}{b^{\prime }}<1,\text{where }b{a}^{\prime }-a{b}^{\prime }=1,1\le b\le n,1\le b^{\prime }\le n.$$

    Then $a\wedge b=1$ and $a^{\prime }\wedge b^{\prime }=1$, so $a∕b$ and $a^{\prime }∕b^{\prime }$ are both fractions of the Farey sequence of order $n$. Moreover $b+b^{\prime }>n$. As in Problem 5, consider any fraction $x∕y(y>0)$ between $a∕b$ and $a^{\prime }∕b^{\prime }$, so that

    $$\begin{array}{lll}\hfill \frac{a}{b}<\frac{x}{y}<\frac{a^{\prime }}{b^{\prime }}.& & \hfill \text{(1)}\end{array}$$

    Since $b{a}^{\prime }-a{b}^{\prime }=1$,

    $$\begin{array}{llll}\hfill \frac{1}{b{b}^{\prime }}=\frac{a^{\prime }}{b^{\prime }}-\frac{a}{b}& =\left(\frac{a^{\prime }}{b^{\prime }}-\frac{x}{y}\right)+\left(\frac{x}{y}-\frac{a}{b}\right)& \hfill & \\ \hfill & =\frac{a^{\prime }y-b^{\prime }x}{b^{\prime }y}+\frac{\mathit{bx}-\mathit{ay}}{\mathit{by}}.& \hfill & \\ \hfill & & \hfill \end{array}$$

    By (1), $a^{\prime }y-b^{\prime }x>0$ and $\mathit{bx}-\mathit{ay}>0$, therefore

    $$\frac{1}{b{b}^{\prime }}\ge \frac{1}{b^{\prime }y}+\frac{1}{\mathit{by}}=\frac{b+b^{\prime }}{b{b}^{\prime }y},$$

    where $b{b}^{\prime }y>0$, thus

    $$y\ge b+b^{\prime }>n,$$

    This shows that no fraction $x∕y$ between $a∕b$ and $a^{\prime }∕b^{\prime }$ is in the Farey sequence of order $n$. Hence $a∕b<a^{\prime }∕b^{\prime }$ are adjacent fractions in this sequence. By definition of the sequence $(b_j)$, this means that there is some $j\in [[1,k-1]]$ such that $(b,b^{\prime })=(b_j,b_{j+1})=\phi (j)$.

  In either case, there is some $j\in [[0,k-1]]$ such that $(b,b^{\prime })=\phi (j)$, so $\phi$ is surjective.

• $\phi$ is injective (one-to-one):

  Suppose that $\phi (j)=\phi (i),1\le i\le k-1,1\le j\le k-1$. Then $(b_j,b_{j+1})=(b_i,b_{i+1})$.

  We write for simplicity

  $$\begin{array}{lll}\hfill \begin{array}{cc}b=b_j=b_i,\hfill & d=b_{j+1}=b_{i+1},\hfill \\ a=a_j,\hfill & a^{\prime }=a_i\hfill \\ c=a_{j+1},\hfill & c^{\prime }=a_{i+1}.\hfill \end{array}& & \hfill \end{array}$$

  We may assume without loss of generality that $a_j\le a_i$, so

  $$\begin{array}{lll}\hfill a\le a^{\prime }.& & \hfill \text{(2)}\end{array}$$

  Since $a_j∕b_j=a∕b$ and $a_{j+1}∕b_{j+1}=c∕d$ are adjacent in the Farey sequence of order $n$ (and also $a_i∕b_j=a^{\prime }∕b$ and $a_{i+1}∕b_{i+1}=c^{\prime }∕d$), we have

  $$\begin{array}{lll}\hfill 0\le & \frac{a}{b}<\frac{c}{d}\le 1,\mathit{cb}-\mathit{ad}=1,b+d>n,& \hfill \text{(3)}\\ \hfill 0\le & \frac{a^{\prime }}{b}<\frac{c^{\prime }}{d}\le 1,c^{\prime }b-a^{\prime }d=1.& \hfill \text{(4)}\end{array}$$

  Then $b(c^{\prime }-c)=d(a^{\prime }-a)$, so $b\mid d(a^{\prime }-a)$, where $b\wedge d=1$, thus $b\mid a^{\prime }-a$, so $a^{\prime }-a=\mathit{\lambda b}$ for some $\lambda \in \mathbb{Z}$, thus $b(c^{\prime }-c)=\mathit{d\lambda b}$, where $b\ne 0$, so $c^{\prime }-c=\mathit{\lambda d}$. This gives

  $$\begin{array}{llll}\hfill a^{\prime }& =a+\mathit{\lambda b},& \hfill & \\ \hfill c^{\prime }& =c+\mathit{\lambda d},& \hfill & \end{array}$$

  and by (2), $\lambda \ge 0$, so $\lambda \in \mathbb{N}$.

  Therefore

  $$\frac{a^{\prime }}{b}=\frac{a}{b}+\lambda ,\frac{c^{\prime }}{d}=\frac{c}{d}+\lambda .$$
  • If $c∕d=1$, then by (4), $c^{\prime }∕d=(c∕d)+\lambda =1+\lambda \le 1$, where $\lambda \ge 0$, thus $\lambda =0$.

  • If $c∕d<1$, then by (3) and (4), $0<c∕d<1$ and $0<(c∕d)+\lambda \le 1,$ thus

    $$\lambda <\frac{c}{d}+\lambda <1+\lambda ,0<\frac{c}{d}+\lambda \le 1,$$

    which gives by transitivity

    $$\lambda <1,0<1+\lambda ,$$

    therefore $\lambda =0$.

  In either case, $\lambda =0$. Hence $a=a^{\prime },c=c^{\prime }$, so $a_j∕b_j=a_i∕b_i$. Since the sequence $(a_j∕b_j)$ is strictly increasing, we obtain $i=j$. This shows that $\phi$ is injective.

We have proved that

is bijective, i.e. for every pair $(b,b^{\prime })\in A$, there is a unique $j$, $1\le j\le k-1$, such that $b=b_j$ and $b^{\prime }=b_{j+1}$. The change of indices $(b,b^{\prime })=\phi (j)$ gives, using the result of Problem 7,

So $\sum <!--\; FUNCTION\; APPLICATION\; -->{(b{b}^{\prime })}^{-1}=1$, where the sum is over all ordered pairs $(b,b^{\prime })$ of integers for which $1\le b\le n,1\le b^{\prime }\le n,g.c.d(b,b^{\prime })=1$, and $b+b^{\prime }>n$. □