On 7/16/07, David Wilson <davidwwilson@comcast.net> wrote:
It looks as if B(p) == 2 (mod p) for prime p.
Besides the Touchard recurrence argument, it is well-known that B(n) = \sum_i S(n, i) where S(n, i) denotes second-kind Stirling numbers; and it can be shown (using a refinement of the Dobinski sum mentioned below) that for prime p, S(p, i) mod p = 0 unless i = 1,p, when S(p, i) = 1.
Is this true, and are there "Bell pseudoprimes" in this respect?
Yes indeed: in order of smallest factor, the first example is m = 21361 = 41*521 Verifying that B(m) mod m = 2 for this value of m is not entirely trivial. However, by the Chinese remainder theorem the result is equivalent to B(m) mod p = 2 for p | m; furthermore, it is a theorem that for prime p and natural q, in umbral notation B(p q) mod p = (B + 1)^q = B(q+1). [See for example Lunnon,~W.~F.~&~Pleasants,~P.~A.~B.~&~Stephens,~N.~M. Arithmetic Properties of Bell Numbers to Composite Modulus I, Acta Arith 35, pp~1-16 (1979).] Putting these together, we need only verify instead that B(522) mod 41 = B(42) mod 521 = 2 which would easily be evaluated directly under Maple 9, using bell(n) from the combinat package. But you can't stop progress: under Maple 10, bell(n) takes a stupendously long time to evaluate anything over n = 170 or so, despite its predecessor being easily good for n = 2500. Fortunately, a simple workaround via sums of Stirling numbers with(combinat); p := 522; q := 41; add(stirling2(p, i), i = 0..p) mod q; add(stirling2(q, i), i = 0..q) mod p; grinds to a conclusion in a minute (G4 Macintosh). A much faster alternative --- unfortunately requiring rather delicate estimation of precision and convergence --- would be the Dobinski infinite sum B(n) = (1/e) \sum_{i >= 0} n^i / i! --- but even this will not easily cope with B(m) above directly. Fred Lunnon