A Combinatorial Identity Using Finite Fields

Achyut Bharadwaj

September 2022

Introduction #

Consider a prime $p$. For what integers $n$ does $p$ divide all of $$\binom{n}{1}, \binom n 2, \binom n 3, \dots, \binom{n}{n-1}?$$ Can we characterize all such $n$ given a value of $p$? It turns out that this happens if and only if $n$ is a perfect power of $p$. How do we prove this? In fact, there exists a simple proof using elementary methods. But as always, it is both fun as well as good to prove everything twice. In this article I present an interesting way to characterize all such $n$ using concepts of finite fields.

The Elementary Proof #

In this section, we prove that

(1) $$p\mid\binom{n}{k}\forall k \in [1, n-1]\cap\mathbb{Z}$$

if and only if $n=p^\alpha$ for some positive integer $\alpha$ using elementary methods.

Notice that we have two directions to prove. The first being that if $n=p^\alpha$ for some positive integer $\alpha$, then $p$ divides all of $\binom{n}{k}$ with $k$ being an integer strictly between $0$ and $n$.

Before we proceed, I state a notation and list some properties related to it. I will not be proving the properties in this article.

Let $v_p(m)$ denote the highest power of $p$ in the prime factorization of $m$. In other words,

(2) $$p^{v_p(m)}\mid m \text{ but } p^{v_p(m) + 1} \nmid m$$

The following are true:

(3) $$v_p(n!) = \sum_{j=1}^\infty \left\lfloor \frac{n}{p^j} \right\rfloor$$
(4) $$v_p(ab) = v_p(a) + v_p(b)$$
(5) $$v_p(a/b) = v_p(a) - v_p(b)$$

Now, let $n=p^\alpha$ since we are proving the first direction. So,

(6) $$v_p(n!) = \sum_{j=1}^\infty \left\lfloor \frac{p^\alpha}{p^j} \right\rfloor = \sum_{j=1}^\alpha \left\lfloor p^{\alpha - j} \right\rfloor = p^{\alpha-1} + p^{\alpha-2}+\cdots+1$$

Now,

(7) $$\begin{aligned} v_p(k!(n-k)!) &= v_p(k!)+v_p((n-k)!) \\ &= \sum_{j=1}^\infty\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right) \\ &= \sum_{j=1}^\alpha \left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right)\end{aligned}$$

since $k$ and $n-k$ are both less than $n$ by assumption. We can take the term $j=\alpha$ outside the summation to get

(8) $$v_p(k!(n-k)! = \sum_{j=1}^{\alpha-1}\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right) + \left\lfloor \frac{k}{p^\alpha} \right\rfloor + \left\lfloor 1-\frac{k}{p^\alpha} \right\rfloor$$

Since $0<\frac{k}{p^\alpha}<1$,

(9) $$\left\lfloor \frac{k}{p^\alpha} \right\rfloor + \left\lfloor 1-\frac{k}{p^\alpha} \right\rfloor = 0 + 0 = 0$$

Hence,

(10) $$v_p(k!(n-k)! = \sum_{j=1}^{\alpha-1}\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right)$$

Now, we use the identity that $\left\lfloor x+y \right\rfloor\geq \left\lfloor x \right\rfloor + \left\lfloor y \right\rfloor$ in the above to get that

(11) $$\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\leq \left\lfloor \frac{k}{p^j}+\frac{n-k}{p^j} \right\rfloor = \left\lfloor \frac{n}{p^j} \right\rfloor$$

Since $n=p^\alpha$, $n/p^j = p^{\alpha - j} \in \mathbb{Z}$. Thus,

(12) $$\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\leq p^{\alpha - j}$$

Plugging this into the summation, we get

(13) $$v_p(k!(n-k)!)\leq \sum_{j=1}^{\alpha - 1}p^{\alpha - j}=p^{\alpha - 1}+p^{\alpha - 2} + \cdots + p$$

The RHS of the above equation is strictly less than $p^{\alpha-1} + p^{\alpha-2}+\cdots+1$. Thus,

(14) $$v_p(k!(n-k)!) < v_p(n!)$$

Hence,

(15) $$v_p(n!) - v_p(k!(n-k)!) = v_p\left(\frac{n!}{k!(n-k)!}\right)=v_p\binom{n}{k}>0$$

This implies that $p\mid \binom nk$ for all $k$ strictly between 0 and $n$, thus completing the first direction of our proof. We now proceed to proving the other direction of the proof. That is, given that $p\mid \binom nk$ for all $k$ strictly between $0$ and $n$, we prove that $n=p^\alpha$.

The most natural way to proceed is by setting up a contradiction. Assume for the sake of contradiction, that $p\mid \binom nk$ for all $k$ strictly between $0$ and $n$ and $n=p^\alpha m$ where $m$ is an integer such that $1<m<\alpha$. We aim to prove that there exists some value of $k$ for which $p \nmid \binom nk$. The best strategy to do so is to construct such a $k$.

We claim that $k=p^\alpha$ ensures that $p \nmid \binom{n}{k}$.

Similar to as in the previous part, we see that

(16) $$v_p(n!) = m(p^{\alpha-1} + p^{\alpha - 2} + \cdots 1)$$

Now,

(17) $$v_p(k!(n-k!)) = \sum_{j=1}^\alpha\left(\left\lfloor \frac{k}{p^j} \right\rfloor + \left\lfloor \frac{n-k}{p^j} \right\rfloor\right)$$

Since $k = p^\alpha$, we may simplify the RHS of the above equation to get

(18) $$v_p(k!(n-k)!) = \sum_{j=1}^\alpha p^{\alpha - j}m = m(p^{\alpha-1}+p^{\alpha - 2} + \cdots + 1)=v_p(n!)$$

Thus, $v_p\binom{n}{k} = 0$, which implies that $p \nmid \binom nk$. If $m\neq1$, then $k$ is between $0$ and $n$. Contradiction. This completes our proof.

An Elegant Proof Using Finite Fields #

A theorem about finite fields is that all automorphisms of a finite field are maps of the form

(19) $$\sigma \colon y \mapsto y^{p^\alpha}$$

where $p$ is the characteristic of the finite field $F$ that $\sigma$ is acting on. This theorem will be used throughout this proof.

Our goal is to prove that $p \mid \binom nk$ for all $k$ between 0 and $n-1$ if and only if $n=p^\alpha$ for some positive integer $\alpha$. Notice that $\binom{n}{k}$ for each $k$ between 0 to $n$ are successive binomial coefficients of the polynomial $(x+1)^n$.

Consider the map

(20) $$\sigma \colon y \mapsto y^n$$

If $\sigma$ is an automorphism, by definition,

(21) $$\sigma(x+1) = \sigma(x)+\sigma(1) \quad \text{and} \quad \sigma(x\cdot1)=\sigma(x)\cdot\sigma(1)$$

The second condition is automatically satisfied for all values of $n$ since $(x\cdot1)^n = x^n\cdot 1^n$. Therefore, $\sigma$ is an automorphism if and only if the first condition is satisfied. In order for the first condition to be satisfied, we must have:

(22) $$(x+1)^n = \sum_{j=0}^n \binom nj x^j = x^n + 1^n$$

By taking the first and last terms of the above summation out of the summation, we get

(23) $$P(x)=\sum_{j=1}^{n-1}\binom njx^j = 0$$

The above must hold true for all values of $x\in F$. In other words, all elements of $F$ are roots of $P(x)\in F[x]$. Since $F$ is a finite field and all elements of $F$ are roots of $P(x)$, we must have $P(x)$ be the zero polynomial. Thus, each of $\binom nj$ must be equal to $0$ over the finite field for $j \in [1, n-1]\cap\mathbb{Z}$. This happens if and only if $p=\text{char}({F})$ divides each of $\binom nj$. In other words, $\sigma$ is an automorphism if and only if $\text{char}(F) \mid \binom nj$ for all $j\in [1, n-1]\cap \mathbb{Z}$.

Moreover, by our theorem, we know that $\sigma$ is an automorphism if and only if $n = p^k$ for some positive integer $k$. Thus, we may conclude that $n=p^k$ if and only if $p\mid\binom{n}{j}$ for all $j\in[1,n-1]\cap\mathbb{Z}$. This very elegantly proves our desired result.