Baltic Way Shortlist, 2023

Let $\mathrm{Epi}(n, i)$ be the number of surjective functions from a set with $n$ elements to a set with $i$ elements. It is not hard to see that $S(n, i) = \frac{\mathrm{Epi}(n, i)}{i!}$. Indeed, a surjective function from $\{1, \dots, n\}$ to $\{1, \dots, i\}$ is the same thing as a partition of $\{1, \dots, n\}$ into $i$ parts, together with a numbering of the blocks of the partition, from $1$ to $i$. For every partition there exists $i!$ numberings, and therefore $S(n, i) \cdot i! = \mathrm{Epi}(n, i)$.

When $1 \le i \le p-1$, $\gcd(p, i!) = 1$. It follows that for $1 \le i \le p-1$, $S(n, i) \equiv S(m, i) \pmod{p}$ if and only if $\mathrm{Epi}(n, i) \equiv \mathrm{Epi}(m, i) \pmod{p}$. So it is enough to prove that if $p-1 \mid m-n$ then $\mathrm{Epi}(n, i) \equiv \mathrm{Epi}(m, i) \pmod{p}$ for all $1 \le i \le p-1$.

There is a formula for $\mathrm{Epi}(n, i)$:
$$\mathrm{Epi}(n, i) = \sum_{j=0}^{i-1} (-1)^j (i-j)^n \binom{i}{j}.$$
This formula is based on nothing more than the inclusion-exclusion principle. The number of surjective functions is the number of all functions $-i$ times the number of functions that miss one particular element $+ \binom{i}{2}$ times the number of functions that miss two particular elements, etc. The number of functions that miss $j$ specified elements is $(i-j)^n$.

Now suppose $m$, $n$ are positive integers satisfying $p-1 \mid m-n$. Then $a^m \equiv a^n \pmod{p}$ for all integers $a$. When $a$ is not divisible by $p$ this follows from Fermat's little theorem. When $a$ is divisible by $p$, both sides are zero mod $p$. But we only need the cases when $a = 1, \dots, p-1$ anyway.

It follows that if $p-1 \mid m-n$ then $\mathrm{Epi}(n,i) \equiv \mathrm{Epi}(m,i) \pmod{p}$ for all $1 \le i \le p-1$, and we are done.

Lemma:
For every $i > 1$ and $n > i$:
$$S(n,i) = i \cdot S(n-1,i) + S(n-1,i-1)$$
Proof. Select an element $x$. There are $S(n-1,i)$ ways to partition the remaining elements into $i$ different sets. By adding $x$ to any of them, we get a partition of the original set. All the partitions obtained this way are different and the only partitions that cannot be obtained this way are the ones where $x$ ends up alone. But in that case the $n-1$ other elements must form $i-1$ sets, yielding another $S(n-1,i-1)$ partitions. $\square$

Lemma:
For every $p$ prime, $p > i \ge 1$ and $\lambda \ge 0$:
$$S(i + \lambda(p-1), i) = 1 \pmod{p}.$$
Proof. As $S(n,1) = 1$ and $S(i,i) = 1$, this is obvious for $i = 1$ or $\lambda = 0$. We proceed by induction over $i$ and $\lambda$. Using the induction hypothesis and the previous lemma:
$$\begin{aligned} S(i + \lambda(p-1), i) &= i \cdot S(i-1 + \lambda(p-1), i) + S(i-1 + \lambda(p-1), i-1) \\ &= i \cdot S(i-1 + \lambda(p-1), i) + 1 \quad \text{mod } p \end{aligned}$$
Otherwise applying this $p-1$ times gives
$$\begin{aligned} S(i + \lambda(p-1), i) &= i^{p-1} \cdot S(i + (\lambda - 1)(p-1), i) + \sum_{j=0}^{p-2} i^j \quad \text{mod } p \\ &= i^{p-1} \cdot 1 + \frac{i^{p-1} - 1}{i-1} \quad \text{mod } p \\ &= 1 \cdot 1 + 0 \quad \text{mod } p. \end{aligned}$$
Where the last equality holds by Fermat's little theorem as $p > i > 1$ implies $i \neq 0, 1 \pmod{p}$. $\square$

We can now proceed to proving the problem statement by induction: If $i=1$ the statement is obvious. If $m=i$ or $n=i$, we have the statement of the second lemma. So assume $i>1$ and $n>i$, $m>i$ and that the problem statement holds for all smaller values. Then
$$\begin{aligned} S(n,i) - S(m,i) &= i \cdot (S(n-1,i) - S(m-1,i)) + \\ &\quad + S(n-1,i-1) - S(m-1,i-1) \\ &= i \cdot 0 + 0 \quad \text{mod } p \\ &= 0 \quad \text{mod } p. \end{aligned}$$