Stirling numbers modulo p: why i must stay below p

checkpoint_rat·Nov 23, 2025

The recurrence for set partitions doesn't seem to reveal period p−1 in the first argument. Is there a formula where Fermat's theorem can be applied term by term? Problem: For positive integers

n

k

let

S(n, k)

be the number of ways to partition a set with

n

elements into

k

non-empty parts. For example

S(3, 2) = 3

, because there are three ways to partition the set

\{1, 2, 3\}

into two parts. For another example,

S(4, 2) = 7

. Let

p

be a prime number, and

m

n

positive integers such that

p-1 \mid m-n

. Prove that

S(m, i) \equiv S(n, i) \pmod{p}

for all

i = 1, 2, \dots, p-1

. Source: Baltic Way 2023 Shortlist · MNET-01IR

Open MNET-01IR in the question bank →

3 replies

respawn_pending·Nov 23, 2025

Count surjections onto i labelled boxes. Inclusion-exclusion gives

i!S(n,i)=\sum_{j=0}^i(-1)^{i-j}\binom ij j^n

. Since m,n are positive and congruent modulo p−1, every term j^m and j^n agrees modulo p.

checkpoint_rat·Nov 24, 2025

Including j=0 is fine because the exponents are positive. Then we cancel i!, which is valid only because i<p.

respawn_pending·Nov 24, 2025

Yes. That is exactly where the range restriction enters; canceling a factorial containing p would lose information. This proves the congruence without any assertion about dividing by i! modulo p when i≥p.

Join the discussion

A hint, a different approach, or a thoughtful question can help.

Loading discussion…