# 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

_{6}

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 _{1}** which is

**F**, insert the mediant into

_{2}**F**:

_{1}**F**we add two mediants:

_{3}**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

_{4}**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

_{5}**F**. The general rule is this: to move from

_{6}**F**to

_{N-1}**F**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

_{N}**F**. 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.

_{N}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 _{7}**

The Farey series furnishes another proof of an important corollary of Euclid's algorithm: for integers m and n with _{1}/n_{1} and m_{2}/n_{2} in the Farey series,
_{2}n_{1} - m_{1}n_{2} = 1.

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

## References

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

- Modular Arithmetic
- Chinese Remainder Theorem
- Euclid's Algorithm
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Examples
- Equivalence relations
- A real life story

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

64494761 |