I am trying exercises of Tom M Apostol Modular functions and Dirichlet series in Number Theory (Ch-5)
Adding image of exercise ->
Assuming a/b and c/d to be consecutive, I proved (b, d) belongs to $ T_{n}'$ .
But on the opposite if b, d belongs to $T_{n}'$ , then by Bezout Lemma there exists x, y belonging to integers st xb+dy=1 , one of them must be -ve as b, d are both +ve but how to be sure that y must be -ve and x,- y both belongs to [1, n] .
Can someone please tell how to prove the opposite part.
This problem can be solved by reminding some properties of Farey sequences. To prove that $a/b$ and $c/d$ are consecutive fractions in a Farey sequence if and only if $b,d \in T'_n$, we have to prove that:
Let us begin with the first statement. A relevant property of Farey sequences is that, given two consecutive terms $a/b$ and $c/d$, then
$$bc-ad=1$$
Now let us set $b=b' k$ and $d=d' k$, where $k\geq 1$ is the GCD between $b$ and $d$. Making the substitutions, we get $k(b'c-ad')=1$. Since $k$ and $(b'c-ad')$ are both integers, the only possibility to have a product equal to $1$ is given by $k=1$ and $b'c-ad'=$ $bc-ad=1$. This implies that $b$ and $d$ are coprime.
Now let us consider the second statement. Another property of Farey sequences is that between the fractions $a/b$ and $c/d$ always lies the fraction $(a+c)/(b+d) $ formed by summing their numerators and their denominators (this central fraction is usually called the "mediant"). So, if we consider two fractions $a/b$ and $c/d$, they can be consecutive in a sequence $F_n$ only if $b+d\geq n+1$. In fact, if $b+d\leq n$, then their mediant $(a+c)/(b+d)$ has a denominator $\leq n$ and is necessarily present between them within the sequence.
Lastly, let us assess the third statement. We can note that every sequence $F_n$ includes all fractions included in $F_{n-1}$, plus a group of new fractions of the form $i/n$, where $i$ is any integer ranging from $1$ to $n$ and coprime with $n$. So, for any $F_n$, these new fractions have all denominator $n$. Let us take a fraction of $F_n$ with denominator $b$, such that $b$ is coprime with $n$. If $c$ is chosen among the integers ranging from $1$ to $n$, the terms $bc \pmod n$ represent a complete residue system modulo $n$. So there exists some $c$ such that $bc=1 \pmod n=an+1$. Note that $c$ is coprime with $n$, as well as $a$ is coprime with $b$ (otherwise we would have $bc-an\neq 1$).
Now let us consider the fractions $c/n$ and $a/b$, which are both in their lowest terms and that are necessarily present in $F_n$. The difference between $c/n$ and $a/b$ is $(bc-an)/(bn)$$=1/(bn)$. It can be shown that, within the sequence $F_n$, the fraction $c/n$ has to be placed immediately after $a/b$. To prove this, firstly note that, at the right of $a/b$, a fraction with a denominator $k<n$ cannot be present: in fact, if this was the case, the difference between this fraction and $a/b$ would be $\geq 1/(bk)$, which is larger than $1/(bn)$. So, after $a/b$, there is a fraction with denominator $n$. On the other hand, for given $a,b,n$, the only numerator that satisfies $bc-an=1$ is $c$. Thus, within $F_n$, the fraction $c/n$ must follow $a/b$.
In this way we have shown that, in a sequence $F_n$, for any value $b$ coprime with $n$, there exists a fraction $a/b$ that is followed by a fraction $c/n$. In other words, for any $b$ ranging from $1$ to $n$ and coprime with $n$, a new fraction with denominator $n$ occurs so that a pair of successive denominators $b,n$ is in $F_n$. The same demonstration can also be repeated to show that $F_n$ contains not only such pairs $(b,n)$, but also their symmetric pairs $(n,b)$ (this can also be shown more rapidly by reminding that the series of the denominator in a Farey sequence is symmetric with respect to the central fraction $1/2$).
Based on these considerations, as we pass from $F_1$ to $F_2$, $F_3$, and so on, all possible pairs of coprime $b,d$ with $1 \leq b\leq n$ and $1 \leq d\leq n$ progressively appear as denominators of successive fractions. Interestingly, the new fractions with denominator $n$ that occur in any $F_n$, when inserted within the sequence between two fractions that are consecutive in $F_{n-1}$, do not eliminate pairs of coprime integers present in $T'_{n}$. In fact, all these new fractions in $F_n$ appear between fractions whose denominators have sum equal to $n$: then, none of these "lost" pairs can be present in $T'_n$, whose lattice points by definition include only pairs with sum $\geq n+1$ and $\leq 2n$. Indeed, the loss of these pairs also allows to satisfy the condition that $b+d\geq n+1$, and leads to a one-to-one correspondence between the pairs of successive denominators in $F_n$ and the lattice points of $T'_n$.
For example, for $n=2$, the only possible pairs of integers $b,d$ included in $T'_2$ (i.e., coprime, included in the range between $1$ and $2$ and such that their sum is $\geq 2+1=3$) are $(1,2)$ and its symmetric $(2,1)$. Accordingly, they both appears as pairs of consecutive denominators in
$$F_2\left(\frac{0}{1},\frac{1}{2}, \frac{1}{1}\right) $$
For $n=3$, the possible pairs of integers $b,d$ in $T'_3$ (as above, coprime, included in the range between $1$ and $3$ and such that their sum is $\geq 3+1=4$) include the new pairs $(1,3)$, $(2,3)$ and their symmetric $(3,1)$ and $(3,2)$. Accordingly, they all appear as new pairs of consecutive denominators in
$$F_3\left(\frac{0}{1}, \frac{1}{3},\frac{1}{2},\frac{2}{3}, \frac{1}{1}\right)$$
Note that $(1,2)$ and $(2,1)$ are no longer included in $T_3$ because $2+1$ does not satisfy the criterion $\geq 4$. As expected, they do not appear in $F_3$ because they have been "lost" after the insertion of the new fractions $1/3$ and $2/3$.
For $n=4$, the possible pairs of integers $b,d$ in $T'_4$ include the new pairs $(1,4)$, $(3,4)$ and their symmetric pairs $(4,1)$ and $(4,3)$. In addition, $T'_4$ also includes $(2,3)$ and $(3,2)$ that were already present in $T'_3$. Accordingly, all these appear as pairs of consecutive denominators in
$$F_4\left(\frac{0}{1}, \frac{1}{4}, \frac{1}{3},\frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}\right)$$
Note that $(1,3)$ and $(3,1)$ are no longer included in $T_3$ because $3+1$ does not satisfy the criterion $\geq 5$. As expected, they do not appear in $F_4$ because they have been lost after the insertion of the new fractions $1/4$ and $3/4$.
In conclusion, in any sequence $F_n$, all possible pairs $b,n$ included in $T'_n$ appear as pairs of successive denominators. The third statement is then proved, and the whole proof is completed.