Understanding Binomial Coefficients and Divisibility by Prime Numbers

We are asked to find the probability that the binomial coefficient $C(n, 7)$, also written as \(\binom{n}{7}\), is a multiple of 7, given that \(n > 7\).

A key concept for determining the divisibility of binomial coefficients by a prime number is Lucas' Theorem. A simpler result derived from Lucas' Theorem states that for a prime \(p\), the binomial coefficient \(\binom{n}{k}\) is divisible by \(p\) if and only if at least one "borrow" is required when subtracting \(k\) from \(n\) in base \(p\). Alternatively, using Legendre's formula, \(\binom{n}{k}\) is divisible by \(p\) if and only if the exponent of \(p\) in the prime factorization of \(\binom{n}{k}\) is greater than 0. The exponent of a prime \(p\) in \(\binom{n}{k}\) is given by the formula \(\frac{S_p(k) + S_p(n-k) - S_p(n)}{p-1}\), where \(S_p(m)\) is the sum of the digits of \(m\) in base \(p\). \(\binom{n}{k}\) is divisible by \(p\) if and only if \(S_p(k) + S_p(n-k) - S_p(n) > p-1\).

Applying Lucas' Theorem to C(n, 7) Modulo 7

In our problem, the prime is \(p=7\) and \(k=7\). We want to know when \(\binom{n}{7}\) is divisible by 7.

Let's write \(n\) and \(k=7\) in base 7. The base-7 representation of 7 is \(10_7\), which means \(7 = 1 \times 7^1 + 0 \times 7^0\).

Let the base-7 representation of \(n\) be \(n = (n_m n_{m-1} \dots n_1 n_0)_7\), where \(0 \le n_i \le 6\). So, \(n = n_m 7^m + \dots + n_1 7^1 + n_0 7^0\).

According to Lucas' Theorem, \(\binom{n}{k} \equiv \prod_{i=0}^m \binom{n_i}{k_i} \pmod p\). For \(k=7=(10)_7\) and $p=7$, we have \(k_1=1\), \(k_0=0\), and \(k_i=0\) for \(i \ge 2\).

So, \(\binom{n}{7} \equiv \binom{n_m}{0} \dots \binom{n_2}{0} \binom{n_1}{1} \binom{n_0}{0} \pmod 7\).

We know that \(\binom{a}{0} = 1\) for any non-negative integer \(a\), and \(\binom{a}{1} = a\) for any non-negative integer \(a\). Also, \(\binom{a}{b} = 0\) if \(a < b\).

Thus, \(\binom{n}{7} \equiv 1 \times \dots \times 1 \times \binom{n_1}{1} \times 1 \pmod 7\).

This simplifies to \(\binom{n}{7} \equiv \binom{n_1}{1} \pmod 7\). Since \(n_1\) is a base-7 digit, \(0 \le n_1 \le 6\).

• If \(n_1 \ge 1\), then \(\binom{n_1}{1} = n_1\). So \(\binom{n}{7} \equiv n_1 \pmod 7\). For \(\binom{n}{7}\) to be a multiple of 7, we need \(n_1 \equiv 0 \pmod 7\), which means \(n_1 = 0\) (since \(1 \le n_1 \le 6\)). This is a contradiction.
• If \(n_1 = 0\), then \(\binom{n_1}{1} = \binom{0}{1} = 0\). So \(\binom{n}{7} \equiv 0 \pmod 7\). In this case, \(\binom{n}{7}\) is a multiple of 7.

Therefore, \(\binom{n}{7}\) is a multiple of 7 if and only if the digit \(n_1\) in the base-7 expansion of \(n\) is 0.

The Base-7 Representation of n and the \(n_1\) Digit

The base-7 expansion of \(n\) is \(n = \dots n_2 7^2 + n_1 7^1 + n_0 7^0\). The digit \(n_1\) is the coefficient of \(7^1\). We can find \(n_1\) using modular arithmetic:

\(n = n_m 7^m + \dots + n_2 49 + n_1 7 + n_0\)

\(n \pmod{49} = n_1 7 + n_0\)

So, \(n_1 = \lfloor (n \pmod{49}) / 7 \rfloor\). Equivalently, \(n_1 = \lfloor n/7 \rfloor \pmod 7\).

The condition that \(\binom{n}{7}\) is a multiple of 7 is equivalent to \(n_1 = 0\), which means \(\lfloor n/7 \rfloor \pmod 7 = 0\).

Calculating the Probability for n Greater Than 7

We are interested in the probability that \(n_1 = \lfloor n/7 \rfloor \pmod 7 = 0\) for \(n > 7\). The set of integers \(n > 7\) is \(\{8, 9, 10, \dots\}\).

Let's look at the values of \(n_1 = \lfloor n/7 \rfloor \pmod 7\) for the first few integers \(n > 7\):

The value \(n_1 = \lfloor n/7 \rfloor \pmod 7\) is 0 if and only if \(\lfloor n/7 \rfloor\) is a multiple of 7.

\(\lfloor n/7 \rfloor = 7k\) for some non-negative integer \(k\). This is equivalent to \(7k \le n/7 < 7k+1\), which means \(49k \le n < 49k+7\). So, \(n \in [49k, 49k+6]\).

Since \(n > 7\), we must have \(49k \ge 8\), which implies \(k \ge 1\).

Thus, \(\binom{n}{7}\) is a multiple of 7 if and only if \(n\) falls into one of the intervals \([49, 55], [98, 104], [147, 153], \dots, [49k, 49k+6], \dots\) for \(k \ge 1\). Each of these intervals contains 7 integers.

These intervals occur periodically among the integers. For any large range of integers, approximately 7 out of every 49 consecutive integers (starting from a multiple of 49) will fall into one of these intervals where \(n_1=0\). The integers not in these intervals have \(n_1 \in \{1, 2, 3, 4, 5, 6\}\).

Considering the integers \(n > 7\), as we look at larger and larger ranges of \(n\), the proportion of integers for which \(n_1 = 0\) approaches the frequency of the condition \(n \pmod{49} \in \{0, 1, 2, 3, 4, 5, 6\}\) among integers greater than 7.

For any integer \(n\), the value of \(n \pmod{49}\) can be any integer from 0 to 48, each with approximately equal likelihood over a large range. There are 49 possible values for \(n \pmod{49}\).

The condition \(n_1 = 0\) is equivalent to \(n \pmod{49} \in \{0, 1, 2, 3, 4, 5, 6\}\). There are 7 such values.

The integers \(n\) such that \(n \pmod{49} \in \{0, 1, \dots, 6\}\) form the set \(\{49k+r \mid k \in \mathbb{Z}_{\ge 0}, r \in \{0, \dots, 6\}\} = \{0, \dots, 6, 49, \dots, 55, 98, \dots, 104, \dots\}\).

The condition \(n > 7\) excludes the values \(\{0, \dots, 6\}\). The remaining values \(\{49, \dots, 55, 98, \dots, 104, \dots\}\) all satisfy \(n > 7\) and \(n_1 = 0\).

Over the set of integers \(n > 7\), the property \(n_1 = 0\) holds for integers in the intervals \([49k, 49k+6]\) for \(k \ge 1\). The integers for which \(n_1 \ne 0\) are in the intervals \([49k+7, 49k+48]\) for \(k \ge 1\) and also in the initial range \([8, 48]\).

In the long run, the integers are approximately uniformly distributed modulo 49. Out of 49 consecutive integers, 7 will satisfy \(n \pmod{49} \in \{0, \dots, 6\}\).

Thus, the probability that \(n_1 = 0\) for \(n > 7\) is the proportion of integers \(n > 7\) where this condition holds. As \(N \to \infty\), the number of integers \(n \in [8, N]\) for which \(n_1 = 0\) is approximately \((N-7) \times \frac{7}{49} = (N-7) \times \frac{1}{7}\). The total number of integers is \(N-7\). The probability is \(\frac{(N-7)/7}{N-7} = \frac{1}{7}\).

Conclusion: The Probability Value

Based on the analysis using base-7 representation and its connection to the divisibility of binomial coefficients by 7, the probability that \(C(n, 7)\) is a multiple of 7 for \(n > 7\) is the proportion of integers \(n > 7\) whose \(7^1\) digit in base 7 is 0. This proportion is \(\frac{1}{7}\).

Revision Table: Binomial Coefficient Divisibility

Additional Information: Lucas' Theorem and Base-p Digits

Lucas' Theorem provides a way to compute binomial coefficients modulo a prime number \(p\). If \(n = n_m p^m + \dots + n_0\) and \(k = k_m p^m + \dots + k_0\) are the base-\(p\) expansions of \(n\) and \(k\), then

\[ \binom{n}{k} \equiv \prod_{i=0}^m \binom{n_i}{k_i} \pmod p \]

where \(\binom{n_i}{k_i} = 0\) if \(n_i < k_i\). A significant consequence is that \(\binom{n}{k}\) is divisible by \(p\) if and only if there exists at least one index \(i\) such that the \(i\)-th digit of \(n\) in base \(p\) (\(n_i\)) is less than the \(i\)-th digit of \(k\) in base \(p\) (\(k_i\)). This corresponds to requiring a "borrow" when subtracting \(k\) from \(n\) in base \(p\).

In our problem, \(p=7\) and \(k=7\). The base-7 expansion of \(k=7\) is \(10_7\), so \(k_1=1\) and \(k_0=0\). For \(\binom{n}{7}\) to be divisible by 7, there must be a borrow when subtracting \(10_7\) from \(n\) in base 7. Let \(n = (\dots n_2 n_1 n_0)_7\). Subtracting \((10)_7\) involves subtracting 0 from \(n_0\) (no borrow here unless \(n_0 < 0\), which is not possible for a digit) and subtracting 1 from \(n_1\). A borrow at the \(7^1\) position is needed if \(n_1 < 1\), i.e., if \(n_1 = 0\). If \(n_1 > 0\), no borrow is needed at this position. Borrows at higher positions only occur if there's a chain of borrows originating from \(n_1-1\). The condition simplifies to checking if a borrow is initiated at the \(7^1\) place or higher due to subtracting the \(7^1\) component of $k$. The only non-zero digit in \(k=7=(10)_7\) is the \(k_1=1\). A borrow is needed at the \(7^1\) place if \(n_1 < k_1\), i.e., \(n_1 < 1\), which means \(n_1=0\). For higher digits \(k_i=0\) for \(i \ge 2\), so no borrow is ever needed for those positions unless required by a borrow propagating from a lower position. However, the divisibility condition simplifies directly from the product form of Lucas' Theorem: \(\binom{n}{7} \equiv \binom{n_1}{1} \binom{n_0}{0} \pmod 7 \equiv n_1 \cdot 1 \pmod 7 \equiv n_1 \pmod 7\). This is zero if and only if \(n_1=0\).