Touchard's congruence for Bell numbers

For a prime p and every n, the Bell numbers satisfy B(n + p) ≡ B(n) + B(n + 1) (mod p); in particular B(p) ≡ 2 (mod p). The proof uses the umbral functional L on (ZMod p)[X] with L(Xⁿ) = B(n): the recurrence Nat.bell_succ gives L(X f) = L(f(X + 1)), hence L((X)ₖ h) = L(h(X + k)) for the falling factorial; in ZMod p the falling factorial of order p is X^p - X (both monic of degree p with the same p roots), which yields the congruence.

Main results

• Touchard.bell_add_prime: B(n + p) = B(n) + B(n + 1) in ZMod p for a prime p

References

• J. Touchard, Propriétés arithmétiques de certains nombres récurrents, Ann. Soc. Sci. Bruxelles A 53 (1933), 21–31.

theorem Touchard.bell_add_prime (p : ℕ) [Fact (Nat.Prime p)] (n : ℕ) : ↑(n + p).bell = ↑n.bell + ↑(n + 1).bell

Touchard's congruence (1933). For a prime p and every n, the Bell numbers satisfy B(n + p) ≡ B(n) + B(n + 1) (mod p); in particular B(p) ≡ 2 (mod p).