Extending Babbage's (Non-)Primality Tests
Preprint
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.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- The on-line encyclopedia of integer sequencesNotices of the American Mathematical Society, 2018
- Divisors of the Middle Binomial CoefficientThe American Mathematical Monthly, 2015
- An extension of Babbage’s criterion for primalityMathematica Slovaca, 2013
- The Mathematical Work of Charles BabbageThe American Mathematical Monthly, 1979
- Irascible Genius: A Life of Charles Babbage, InventorTechnology and Culture, 1968
- Binomial Coefficients Modulo a PrimeThe American Mathematical Monthly, 1947