Cunningham Number

A Binomial Number of the form $C^\pm (b,n)\equiv b^n\pm 1$. Bases $b^k$ which are themselves powers need not be considered since they correspond to $(b^k)^n\pm 1=b^{kn}\pm 1$. Prime Numbers of the form $C^\pm (b,n)$ are very rare.

A Necessary (but not Sufficient) condition for $C^+(2,n)=2^n+1$ to be Prime is that $n$ be of the form $n=2^m$. Numbers of the form $F_m=C^+(2,2^m)=2^{2^m}+1$ are called Fermat Numbers, and the only known Primes occur for $C^+(2,1)=3$, $C^+(2,2)=5$, $C^+(2,4)=17$, $C^+(2,8)=257$, and $C^+(2,16)=65537$ (i.e., $n=0$, 1, 2, 3, 4). The only other Primes $C^+(b,n)$ for nontrivial $b\leq 11$ and $2\leq n\leq 1000$ are $C^+(6,2)=37$, $C^+(6,4)=1297$, and $C^+(10,2)=101$.

Primes of the form $C^-(b,n)$ are also very rare. The Mersenne Numbers $M_n=C^-(2,n)=2^n-1$ are known to be prime only for 37 values, the first few of which are $n=2$, 3, 5, 7, 13, 17, 19, ... (Sloane's A000043). There are no other Primes $C^-(b,n)$ for nontrivial $b\leq 20$ and $2\leq n\leq 1000$.

In 1925, Cunningham and Woodall (1925) gathered together all that was known about the Primality and factorization of the numbers $C^\pm (b,n)$ and published a small book of tables. These tables collected from scattered sources the known prime factors for the bases 2 and 10 and also presented the authors' results of 30 years' work with these and other bases.

Since 1925, many people have worked on filling in these tables. D. H. Lehmer, a well-known mathematician who died in 1991, was for many years a leader of these efforts. Lehmer was a mathematician who was at the forefront of computing as modern electronic computers became a reality. He was also known as the inventor of some ingenious pre-electronic computing devices specifically designed for factoring numbers.

Updated factorizations were published in Brillhart et al. (1988). The current archive of Cunningham number factorizations for $b=1$, ..., $\pm 12$ is kept on ftp://sable.ox.ac.uk/pub/math/cunningham. The tables have been extended by Brent and te Riele (1992) to $b=13$, ..., 100 with $m<255$ for $b<30$ and $m<100$ for $b\geq 30$. All numbers with exponent 58 and smaller, and all composites with $\leq 90$ digits have now been factored.

See also Binomial Number, Cullen Number, Fermat Number, Mersenne Number, Repunit, Riesel Number, Sierpinski Number of the First Kind, Woodall Number

References

Brent, R. P. and te Riele, H. J. J. ``Factorizations of $a^n\pm 1$, $13\leq a<100.$'' Report NM-R9212, Centrum voor Wiskunde en Informatica. Amsterdam, June 1992. ftp://sable.ox.ac.uk/pub/math/factors/.

Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; and Tuckerman, B. Factorizations of $b^n\pm 1$, $b=2$, $3, 5, 6, 7, 10, 11, 12$ Up to High Powers, rev. ed. Providence, RI: Amer. Math. Soc., 1988. Updates are available electronically from ftp://sable.ox.ac.uk/pub/math/cunningham/.

Cunningham, A. J. C. and Woodall, H. J. Factorisation of $y^n\mp 1$, $y=2$, 3, 5, 6, 7, 10, 11, 12 Up to High Powers ($n$). London: Hodgson, 1925.

Mudge, M. ``Not Numerology but Numeralogy!'' Personal Computer World, 279-280, 1997.

Ribenboim, P. ``Numbers $k\times 2^n\pm 1$.'' §5.7 in The New Book of Prime Number Records. New York: Springer-Verlag, pp. 355-360, 1996.

Sloane, N. J. A. Sequence A000043/M0672 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.