Farey Series

The Farey series F_N is the set of all fractions in lowest terms between 0 and 1 whose denominators do not exceed N, arranged in order of magnitude. For example, F₆ is

N is known as the order of the series. Farey was a British geologist who in 1816 published the statement to the effect that in the Farey series the middle of any three successive terms is the mediant of the other two. The proof has been eventually supplied by Cauchy. The series nonetheless bears the name of Farey.

To see why the statement is correct, start with F₁ which is 0/1, 1/1. In order to get F₂, insert the mediant into F₁: 0/1, 1/2, 1/1. For F₃ we add two mediants: 0/1,1/3,1/2,2/3,1/1. To get F₄ we also add only 2 fractions: 0/1,1/4,1/3,1/2,2/3,3/4,1/1. Next, add 4 fractions to get F₅: 0/1,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1. As we already saw, it takes additional 2 fractions to get F₆. The general rule is this: to move from F_N-1 to F_N add all possible mediants (that come out to be in the lowest terms) with N in the denominator. Since forming a mediant may only increase the denominator we are led to think that following this rule we indeed will get the whole of F_N. To complete the proof recollect that the Stern-Brocot tree contains all positive fractions. So in the process of constructing Farey series no fraction will be missed either.

When N is prime, the rule adds N-1 fractions. In general, (N) fractions are added. For all reducible fractions m/N will have appeared in one of the earlier series. Check this with F₇

The Farey series furnishes another proof of an important corollary of Euclid's algorithm: for integers m and n with gcd(m,n) = 1 and mn, there exist positive integers a and b such that ma - nb = 1. The proof again depends on the properties of the Stern-Brocot tree. For any two consecutive fractions m₁/n₁ and m₂/n₂ in the Farey series, m₂n₁ - m₁n₂ = 1. So, depending on which of m or n is larger, locate either m/n or n/m in a Farey series and select (as a/b) either the preceding or the following fraction.

An absolutely marvelous geometric interpretation of the Farey series has been invented by Lester R. Ford.

References

1. A. Beck, M.N. Bleicher, D. W. Crowe, Excursions into Mathematics, A K Peters, 2000
2. J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.
3. R.Graham, D.Knuth, O.Patashnik, Concrete Mathematics, 2nd edition, Addison-Wesley, 1994.

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
    • Fractions on a Binary Tree II
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
  • Further examles of divisibility criteria
• Examples
• Equivalence relations
• A real life story

Copyright © 1996-2008 Alexander Bogomolny