## Some Stirling Number Congruences

Here is Problem 51, parts and b, in Chapter 6 of the classic text Concrete Mathematics:

51.  Let p be a prime number.

a.  Prove that $\displaystyle \left\{p \atop k \right\} \equiv \left[p \atop k \right] \equiv 0 \pmod p$, for $1 < k< p$.
b.  Prove that $\displaystyle \left[ p-1 \atop k \right] \equiv 1 \pmod p$, for $1 \leq k < p$.

In this post I will show that the converses of these hold.  In other words,

51a (converse).  If $p > 1$, and $\displaystyle \left\{p \atop k \right\} \equiv \left[p \atop k \right] \equiv 0 \pmod p$ for $1 < k< p$, then p is prime.
51b (converse).  If $p > 1$, and $\displaystyle \left[ p-1 \atop k \right] \equiv 1 \pmod p$ for $1 \leq k < p$, then p is prime.

Theorem 1: If $p > 1$, and $\displaystyle \left[ p \atop k \right] \equiv 0 \pmod p$ for all $1 < k < p$, then p is prime.

Proof: We know from basic properties of Stirling numbers that $\displaystyle \left[ p \atop 1 \right] = (p-1)!$ and $\displaystyle \left[ p \atop p \right] = 1$ for each integer p.  Therefore, if $\displaystyle \left[ p \atop k \right] \equiv 0 \pmod{p}$ for all $1 < k < p$, then

$\displaystyle p! \equiv \sum_{k=1}^p \left[ p \atop k \right] \equiv \left[ p \atop k \right] + \left[ p \atop 1 \right] \equiv (p-1)! + 1 \pmod p$.

Since $p! \equiv 0 \pmod{p}$ for all integers p, $(p-1)! \equiv -1 \pmod{p}$.  By Wilson’s Theorem, $(p-1)! \equiv -1 \pmod{p}$ if and only if p is prime. Therefore, p must be prime.

Theorem 2: If $p > 1$, and $\displaystyle \left\{ p \atop k \right\} \equiv 0 \pmod{p}$ for all $1 < k < p$, then p is prime.

Proof: The Stirling numbers obey the following inversion formula:
$\displaystyle \sum_k \left\{ p \atop k \right\} \left[ k \atop q \right] (-1)^{p-k} = [p = q].$

Also, $\displaystyle \left\{p \atop 1\right\} = \left\{p \atop p \right\} = 1$ for each integer p. Thus, if $\displaystyle \left\{p \atop k \right\} \equiv 0 \pmod p$ for all $1 < k < p$, we have, for $q=1$ and $p>1$:

$\displaystyle 0 \equiv \sum_{k=1}^p \left\{ p \atop k \right\} \left[ k \atop 1 \right] (-1)^{p-k} \equiv \left\{ p \atop 1 \right\} \left[ 1 \atop 1 \right] (-1)^{p-1} + \left\{ p \atop p \right\} \left[ p \atop 1 \right] (-1)^0 \equiv (-1)^{p-1} + (p-1)! \pmod p.$

The set of solutions to this congruence is the set of primes, as $\displaystyle (p-1)! \equiv \begin{cases} -1 \pmod p, & \text{ if } p \text{ is prime;} \\ 2 \pmod p, & \text{ if } p = 4; \\ 0 \pmod p, & \text{ otherwise.} \end{cases}$

Therefore, p must be prime.

Theorem 3: If $p > 1$, and $\displaystyle \left[ p-1 \atop k \right] \equiv 1 \pmod p$ for all $1 \leq k < p$, then p is prime.

Proof:  We know from basic properties of Stirling numbers that $\displaystyle \sum_{k=1}^{p-1} \left[ p-1 \atop k \right] = (p-1)!$. Therefore, if $\displaystyle \left[ p-1 \atop k \right] \equiv 1 \pmod p$ for all $1 \leq k < p$, then we have

$\displaystyle (p-1)! \equiv \sum_{k=1}^{p-1} \left[ p-1 \atop k \right] \equiv \sum_{k=1}^{p-1} 1 \equiv p-1 \equiv -1 \pmod p.$

Again, by Wilson’s Theorem, $(p-1)! \equiv -1 \pmod{p}$ if and only if p is prime. Therefore, p must be prime.

(For those who wish to see solutions to Problems 51a and 51b as stated in Concrete Mathematics, the text contains outlines of the solutions in the back, as it does with all problems.)