Extending Babbage's (Non-)Primality Tests

Abstract

We recall Charles Babbage's 1819 criterion for primality, based on simultaneous congruences for binomial coefficients, and extend it to a least-prime-factor test. We also prove a partial converse of his non-primality test, based on a single congruence. Two problems are posed. Along the way we encounter Bachet, Bernoulli, Bezout, Euler, Fermat, Kummer, Lagrange, Lucas, Vandermonde, Waring, Wilson, Wolstenholme, and several contemporary mathematicians.

10 pages, 1 figure