Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Farey Series

Date: 10/21/2002 at 09:24:35
From: Clive
Subject: Farey's series

Dear Dr. Math,

I have encountered some difficulties in solving problems about Farey's 
series.

For 3 successive terms in a Farey's series, say a/b, c/d, e/f, how can 
we show that 

    i) c/d = (a+e)/(b+f)
   ii) ad-bc = -1

I can prove that i) implies ii) and ii) implies i), but I cannot prove 
either one independently. Any help will be appreciated. Thank you.

Yours sincerely,
Clive


Date: 12/10/2002 at 01:51:48
From: Doctor Nitrogen
Subject: Re: Farey's series

Hi, Clive:

Here is a suggestion as to how you can prove (i) and (ii) 
independently:

[A] Let a <= b <= n,

[B] e <= f <= n for some n.

Since a/b < e/f, a < b, e < f, and since a + e < b + f, it is also 
true that

[1]  a/b < (a + e)/(b + f) 

   (Why? Hint: look at the inequality a(a + e) < b(b + f), and at 
    (a + e)/(b + f) < b/a). "Manipulate" this inequality around 
    and see what happens.)

Therefore,

     a/b < (a + e)/(b + f).

With a similar argument,

     (a + e)/(b + f) < e/f. Therefore

      a/b < (a + e)/(b + f) < e/f is true.

Now for proving (ii), let GCD(a + e, b + f) = k => 1. then

     (a + e)/(b + f) = kc/kd = c/d, for some integers c and d, 
      with GCD(c, d) = 1.

There is a theorem in number theory that says if GCD(c, d) = 1, then 
the equation

     cx + dy = 1 has a solution for (x, y). 

Similarly, for GCD(a, b) =1, the equation 

     bx + dy = 1 has a solution for (x, y), 

and the solutions will be

     (b, -a), and (c, -d)

respectively (you might have to prove this to convince yourself). 

One reference that has a theorem and proof close to this last result 
is _The Theory of Numbers: An Introduction_, Anthony A. Gioia, Markham 
Publishing. This is an older publication dating back to the sixties. 

In {A] and [B] above, the number n has a connection to Farey series. 
For example, for the Farey Series

  0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 

  1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 

  2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 

  1,

for this Farey series, n = 7.

The conditions [A] and [B] above are actually required for a Farey 
series.

- Doctor Nitrogen, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/