Prime Numbers in Farey Sequences

What a Farey Sequence Contains

The Farey sequence of order n, written F_n, contains every reduced fraction a/b between 0 and 1 whose denominator is at most n. The fractions are arranged in increasing numerical order.

The greatest-common-divisor condition matters because Farey sequences contain fractions in reduced form. Fractions such as 2/6 and 3/6 are not separate terms; they reduce to 1/3 and 1/2.

For example:

This explains where prime numbers enter the structure. A denominator can contribute a fraction only when its numerator is coprime to that denominator.

Prime Denominators Keep Every Possible Numerator

Suppose the denominator is a prime p. Every integer from 1 through p − 1 is coprime to p because a prime has no positive divisors other than 1 and itself.

Therefore all of these fractions are reduced:

For p = 7, the denominator 7 introduces:

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

None can be reduced. All six appear for the first time when the Farey order reaches 7.

Prime and Composite Orders Behave Differently

The contrast at 6 shows what changes for a composite denominator. The possible fractions 2/6, 3/6, and 4/6 reduce to fractions that already occur at lower Farey orders. Only 1/6 and 5/6 remain reduced.

Euler’s Totient Function Counts the New Fractions

The exact number of fractions introduced by denominator n is given by Euler’s totient function φ(n). It counts the positive integers below n that are coprime to n.

This identity follows directly from the definition of a Farey sequence. Every reduced fraction a/n with 1 ≤ a < n is absent from F_n−1 because its reduced denominator is n. Exactly φ(n) numerators satisfy gcd(a,n) = 1.

The total number of terms in F_n is therefore:

The initial 1 and the totient sum account for the endpoints and every group of reduced fractions introduced as the allowed denominator increases.

Farey Growth Characterizes Prime Numbers

A prime p is coprime to every positive integer smaller than itself, so:

Conversely, if n > 1 is composite, it has a prime divisor smaller than n. At least that divisor is not coprime to n, so φ(n) cannot equal n − 1.

Combining this with the Farey growth formula gives:

A prime order therefore produces the largest possible increase: every numerator from 1 through n − 1 survives the coprimality test.

Prime Factorization Controls Composite Farey Growth

For a composite denominator, the size of the Farey contribution depends on its distinct prime factors. Euler’s product formula makes this explicit:

The product runs over the distinct prime divisors of n. Each prime divisor removes numerators that share that factor with the denominator.

Example: Denominator 12

The prime factorization is:

12 = 2² × 3

Its totient value is:

The four new Farey fractions with denominator 12 are:

1/12, 5/12, 7/12, 11/12

The other numerators from 1 through 11 share a factor of 2 or 3 with 12 and therefore produce reducible fractions.

Prime Powers Produce a Regular Pattern

If the denominator is a power of one prime, n = p^k, the only numerators excluded are those divisible by p. The totient becomes:

For 8 = 2³, only odd numerators survive:

1/8, 3/8, 5/8, 7/8

so φ(8) = 4.

For 9 = 3², the numerators divisible by 3 are removed. The six surviving fractions are:

1/9, 2/9, 4/9, 5/9, 7/9, 8/9

and φ(9) = 6.

This is why a composite Farey order does not have one fixed growth pattern. Its contribution reflects the prime divisors of the denominator.

How Many Farey Fractions Have Prime Denominators?

A prime denominator p contributes exactly p − 1 reduced fractions. Therefore the number of fractions in F_n whose reduced denominator is prime is:

For F₁₀, the available prime denominators are 2, 3, 5, and 7. Their contributions are:

1 + 2 + 4 + 6 = 13

So F₁₀ contains 13 fractions with prime denominators:

This count is different from the total length of F₁₀. Composite denominators also contribute reduced fractions, so prime denominators form only one part of the sequence.

Prime Orders Are Peaks in the Farey Increment

The function φ(n) can be viewed as the number of new Farey points introduced at order n. For every n > 1:

φ(n) ≤ n − 1

Equality occurs exactly at prime values of n. If the points (n, φ(n)) were plotted together with the line y = n − 1, every prime order would touch that line while every composite order would lie below it.

The distance below the line also carries arithmetic information. A composite number with several small prime factors tends to lose many possible numerators because many integers below it share one of those factors.

For example:

• φ(11) = 10, so all ten possible positive numerators survive.
• φ(12) = 4, because factors 2 and 3 eliminate most candidates.
• φ(13) = 12, so the increment immediately returns to its maximum at the next prime.

Farey Size and Coprime Density

The total length of a Farey sequence is controlled by accumulated totient values:

For large n, its size satisfies the asymptotic relation:

The constant is closely connected with coprimality. The limiting probability that two positive integers are coprime is 6/π², which can also be written through an Euler product over all primes:

Primes therefore influence Farey sequences on two levels. Individually, the prime factors of a denominator decide which numerators survive. Collectively, all primes appear in the density law behind the total number of reduced fractions.

Prime-Denominator Fractions Become Relatively Sparser

The number of fractions with prime denominator at most n is:

Σ_p≤n(p − 1)

The prime number theorem implies that this quantity grows on the scale of:

Meanwhile, the whole Farey sequence grows on the scale of 3n²/π². Comparing these two growth rates gives an approximate prime-denominator proportion of:

This proportion tends to 0 as n increases. The number of prime-denominator fractions continues to grow, but composite denominators collectively contribute an even larger share of the increasingly dense Farey sequence.

Prime Numbers Do Not Determine Farey Adjacency

Prime denominators explain an important part of Farey growth, but primality is not the rule that decides whether two fractions are neighbors.

If a/b and c/d are consecutive terms of a Farey sequence with a/b < c/d, they satisfy:

This determinant-one relation depends on the numerators and denominators together. Neither denominator has to be prime.

Farey sequences also have a mediant structure. For suitable neighboring fractions a/b and c/d, the fraction:

lies between them and appears when the permitted denominator becomes large enough. This mechanism explains how new rational numbers fill gaps between existing Farey terms, while the totient function determines how many genuinely new reduced fractions arrive at each order.