Farey Sequences

Definition: Let $n \in \mathbb{N}$. The Farey Sequence of Order $n$ is the finite sequence $\mathcal F_n$ defined as follows. $\mathcal F_n$ is a strictly increasing sequence of rationals starting at $0$ and ending at $1$ and contains rational numbers $\frac{a}{b}$ in lowest terms where $b$ is at most $n$.

The Farey sequences $\mathcal F_n$ for $n = 1, 2, 3, 4, 5, 6$ are given below:

$n$	$\mathcal F_n$
$1$	$\left \{ \frac{0}{1}, \frac{1}{1} \right \}$
$2$	$\left \{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1} \right \}$
$3$	$\left \{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{2} \right \}$.
$4$	$\left \{ \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1} \right \}$
$5$	$\left \{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right \}$
$6$	$\left \{ \frac{0}{1}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{1}{1} \right \}$

Observe that $\mathcal F_n \subseteq \mathcal F_{n+1}$ for every $n \in \mathbb{N}$.

Also observe that in the Farey sequence $\mathcal F_{n+1}$, if $\frac{a}{b}$ and $\frac{c}{d}$ are consecutive fractions in $\mathcal F_n$ then if $b + d = n + 1$ we add the fraction $\frac{a + c}{b + d}$ between $\frac{a}{b}$ and $\frac{c}{d}$ in $\mathcal F_{n+1}$.

Proposition 1: Let $n \in \mathbb{N}$ and let $\frac{a}{b} \in \mathcal F_n$. The next fraction in the Farey sequence $\mathcal F_n$ is $\frac{x}{y}$ where $x = \frac{ay + 1}{b}$ and $y$ is the unique solution to $y \equiv -a^{-1} \pmod b$ where $n - b < y \leq n$.

• Proof: Let $\frac{a}{b} \in \mathcal F_n$ and let $x = \frac{ay + 1}{b}$ and $y$ be such that $y \equiv -a^{-1} \pmod b$ with $n - b < y \leq n$. First observe that $x \in \mathbb{Z}$. This is because:

(1)

\begin{align} \quad ay + 1 \equiv a(-a^{-1}) + 1 = -1 + 1 = 0 \pmod b \end{align}

• Next, $\frac{x}{y}$ is in lowest terms since $x = \frac{ay + 1}{b}$ implies that $-ay + bx = 1$. If $(x, y) = d$ then $d | -ay$ and $d | -bx$ so $d | 1$ implying that $d = 1$.

• We also have that $\frac{x}{y}$ succeeds $\frac{a}{b}$ since:

(2)

\begin{align} \quad \frac{x}{y} = \frac{ay + 1}{by} > \frac{ay}{by} = \frac{a}{b} \end{align}

• All that is left to show is that there is no fraction $\frac{c}{d}$ in lowest terms with $d \leq n$ such that $\frac{a}{b} < \frac{c}{d} < \frac{x}{y}$. Suppose otherwise. Observe that since $-ay + bx = 1$ (from the definition of $x$) we have that:

(3)

\begin{align} \quad \frac{x}{y} - \frac{a}{b} = \frac{bx - ay}{by} = \frac{1}{by} \quad (*) \end{align}

• Now observe that since $\frac{x}{y} > \frac{c}{d}$ we have that $dx > cy$ and so $dx - cy > 0$. Since $(dx - cy) \in \mathbb{Z}$ we must have that $dx - cy \geq 1$. Hence:

(4)

\begin{align} \quad \frac{x}{y} - \frac{c}{d} = \frac{dx - cy}{dy} \geq \frac{1}{dy} \quad (**) \end{align}

• Similarly, observe that since $\frac{c}{d} > \frac{a}{b}$ we have that $bc > ad$ and so $bc - ad > 0$. Since $(bc - ad) \in \mathbb{Z}$ we must have that $bc - ad \geq 1$. Hence:

(5)

\begin{align} \quad \frac{c}{d} - \frac{a}{b} = \frac{bc - ad}{bd} \geq \frac{1}{bd} \quad (***) \end{align}

• Therefore, using $(**)$ and $(***)$ together, we have that:

(6)

\begin{align} \quad \frac{x}{y} - \frac{a}{b} &= \left [ \frac{x}{y} - \frac{c}{d} \right ] + \left [ \frac{c}{d} - \frac{a}{b} \right ] \\ &\geq \frac{1}{dy} + \frac{1}{bd} \\ &\geq \frac{b + y}{bdy} \end{align}

• Since $y$ is chosen such that $n - b < y \leq n$, we see that $n < b + y$. But $d \leq n$. since $\frac{c}{d}$ is in $\mathcal F_n$. So $\frac{b + y}{d} > 1$. Hence:

(7)

\begin{align} \quad \frac{x}{y} - \frac{a}{b} \geq \frac{b + y}{d} \cdot \frac{1}{by} > \frac{1}{by} \quad (****) \end{align}

• Looking at $(*)$ and $(****)$ we arrive at a contradiction. Hence the assumption that there exists a fraction $\frac{c}{d}$ with $d \leq n$ such that $\frac{a}{b} < \frac{c}{d} < \frac{x}{y}$ is false. Hence $\frac{x}{y}$ is the next Farey fraction in $\mathcal F_n$. $\blacksquare$

Corollary 1: Let $n \in \mathbb{N}$. If $\frac{a}{b}, \frac{c}{d}$ are consecutive Farey fractions in $\mathcal F_n$ then $|ad - bc| = 1$.

• Proof: If $\frac{c}{d}$ is the next Farey fraction after $\frac{a}{b}$ then:

(8)

\begin{align} \quad c = \frac{ad + 1}{b} \end{align}

(9)

\begin{align} \quad d \equiv -a^{-1} \pmod b \quad , \quad n - b < y \leq n \end{align}

• In particular, $bc -ad = 1$. Therefore $ad - bc = -1$. So $|ad - bc| = 1$. $\blacksquare$

Corollary 2: Let $n \in \mathbb{N}$. If $\frac{a}{b}, \frac{c}{d}, \frac{e}{f}$ are consecutive Farey fractions in $\mathcal F_n$ then $\frac{c}{d} = \frac{a + e}{b + f}$.

• Proof: Since $\frac{c}{d}$ comes after $\frac{a}{b}$ we have that $c = \frac{ad + 1}{b}$ and since $\frac{e}{f}$ comes after $\frac{c}{d}$ we have that $e = \frac{cf + 1}{d}$. Therefore:

(10)

\begin{align} \quad \frac{a + e}{b + f} = \frac{a + \frac{cf + 1}{d}}{b + f} = \frac{ad + cf + 1}{d(b + f)} \frac{(ad + 1) + cf}{d(b + f)} = \frac{bc + cf}{d(b + f)} = \frac{c(b + f)}{d(b+f)} = \frac{c}{d} \quad \blacksquare \end{align}