Divisibility of Stirling numbers It is well known that if $p$ is prime, Stirling numbers of the first and second kind, $s_1(p,k)$ and $s_2(p,k)$, are divisible by $p$ if $1<k\le p-1$ (Lagrange ; easiest is working in $\mathbb F_p$ with the factorization of $X^p-X$). But is the converse true, i.e. is $n$ prime if all the $s_1(n,k)$ (or $s_2(n,k)$) are divisible by $n$ for $1<k\le n-1$? I checked it for $n<1000$ (hard to do much more with simple programs)  ; the similar well-known result for binomial coefficients is not hard to prove using the explicit formula, but I have no idea for Stirling numbers.
 A: The Stirling numbers of the first kind satisfy $x^{\underline{n}} = \sum_{k=0}^n s_1(n,k)x^k$. For $n > 0$ we have $s_1(n, 0) = 0$, $s_1(n, 1) = (-1)^{n-1}(n-1)!$, $s_1(n, n) = 1$.
If $n > 1$ then $1^{\underline{n}} = 0$, so $\sum_{k=1}^n s_1(n,k) = 0$, or $$ \sum_{k=2}^{n-1} s_1(n,k) = -s_1(n,n) - s_1(1,1) = (-1)^n (n-1)! - 1$$
We need to deal with three cases of composite $n$:

*

*$n=4$ can be handled as a special case: $s_1(4, 2) = 11 \not\equiv 0 \pmod 4$.

*$n$ has a non-trivial factorisation into distinct factors (i.e. $n=uv$ where $2 \le u < v$): $(n-1)! \equiv 0 \pmod n$ because both $u$ and $v$ are terms of the factorial.

*$n = p^2$ is a prime square where $p > 2$: both $p$ and $2p$ are terms of the factorial, so again $(n-1)! \equiv 0 \pmod n$.

So if $n > 4$ is composite then $(n-1)! \equiv 0 \pmod n$, so the sum is non-zero $\bmod n$ and in particular cannot contain only terms which are zero $\bmod n$.
A: Following the lines of Peter Taylor answer, a proof for Stirling numbers of the second kind follows : we have$$X^{n-1}-1=\sum_{k=2}^ns(n,k)\prod_{j=2}^k(X-j+1),$$ so for $X=0$, $\sum_{k=2}^ns(n,k)(-1)^k(k-1)!=1$, and $\sum_{k=2}^{n-1}s(n,k)(-1)^k(k-1)!=(-1)^n(n-1)!+1$, which can be a multiple of $n$ only if $n$ is prime (Wilson theorem), so if $n$ is not prime, not every $s(n,k)$ can be a multiple of $n$.
