Exercise 13, § 1

The Farey series of order $n$ ($n$ an integer > o) is the set $F_n$ of rational numbers $p/q$ in their lowest terms such that $0 \leq p \leq q \leq n$, arranged in increasing order (i.e., the Farey series is a sequence).

a) Show that if two rational numbers $r = p/q, r' = p'/q'$ are such that $p'q - pq' = \pm 1$, then every pair of integers $(p'', q'')$ can be expressed in the form $p'' = px + p'y, q'' = qx + q'y$ where $x$ and $y$ are integers. The fraction $p''/q''$ belongs to the closed interval with end-points $r$ and $r'$ if and only if $x$ and $y$ have the same sign.

b) Deduce from a) that if $r = p/q$ and $r' = p'/q'$ are two rational numbers in $[0, 1]$ such that $q > 0$ and $q' > 0$ and $qp' - pq' = \pm 1$, then $r$ and $r'$ are consecutive elements in the sequence $F_n$, where $n = \max(q, q')$. Furthermore, the smallest integer $m$ such that the open interval with end-points $r$ and $r'$ contains a point of $F_m$ is $m = q + q'$, and there is only one point of $F_{q+q'}$ in this interval, namely the fraction $(p + p')/(q + q')$.

c) Show that conversely, if $r$ and $r'$ are two consecutive elements of $F_n$, we have $p'q - pq' = \pm 1$ (use induction on $n$).

d) Deduce from c) that, for each real number $\theta \in [0, 1]$ and each integer $n \geq 1$, there is at least one fraction $p/q$ in its lowest terms such that $1 \leq q \leq n$ and $|\theta - p/q| \leq 1/(n + 1)q$ (cf. Exercise 10).

e) If $p/q$ is a fraction in its lowest terms such that $|\theta - p/q| < 1/q^2$, then $\theta$ belongs to the open interval whose end-points are the two terms of the Farey series $F_q$ consecutive to $p/q$.