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.)

Advertisements
This entry was posted in combinatorics, elementary number theory. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s