stigler’s law of eponymy

April 23, 2014 in Cool Tricks, Number Theory

6.1.5
Let a, b, c, & d
be integers satisfying
b > 0, d > 0, and
ad – bc = 1.
Let n = max{b,d}.
Then a/b and c/d are consecutive
fractions in the n^th Farey Sequence.

Proof:
Since ad-bc=1, we have
ad/(bd) = (1+bc)/(bd), hence
a/b = 1/(bd) + c/d and so
a/b > c/d.

Note that (cf. Corollary 6.2)
ad-bc = 1 also implies
(a,b) = 1 and (c,d) = 1;
our fractions are in
“lowest terms” (and hence
appear in F_n).

Now suppose c/d & a/b are *not* adjacent.
Then there is at least one fraction,
which we may assume is in “lowest terms”,
“p/q”, say, with (p,q) = 1, such that
p/q is *between* c/d and a/b
in the Farey sequence F_n:
F_n = { …, c/d, …, p/q, …, a/b, …}.

Then
q = (ad-bc)q
= adq ___________ – bqc
= adq – bdp + bdp – bcq
= d(aq-bp) + b(dp-cq)
(*).

But a/b > p/q implies
aq – pb > 0, and so
(since the variables are integers)
we have that
aq – bp is greater-or-equal to 1
(aq – bp \ge 1).
The same computation with different
letters shows that
[p/q > c/d] \implies [dp – cq \ge 1].

These inequalities together with (*) give
q = d(aq-bp) + b(dp-cq)
q \ge d + b.

Recall that n = max{b,d}.
It follows that d + b > n.
This gives us q > n, a contradiction
(“p/q” cannot be in F_n with q > n).

Hence a/b and c/d *are* adjacent in F_n; done.

Advertisement