1,1

An odd composite number n is a pseudoprime to base a iff a^(n-1) == 1 mod n. A Carmichael number is an odd composite number n which is a pseudoprime to base a for every number a prime to n.

Ghatage and Scott prove using Fermat's little theorem that (a+b)^n == a^n + b^n (mod n) (the freshman's dream) exactly when n is a prime (A000040) or a Carmichael number. - Jonathan Vos Post (jvospost3(AT)gmail.com), Aug 31 2005

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Alford, W. R., Granville, Andrew and Pomerance, Carl, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703-722.

F. Arnault, Constructing Carmichael numbers which are strong pseudoprimes to several bases, Journal of Symbolic Computation, vol. 20, no 2, Aug. 1995, pp. 151-161.

F. Arnault. Rabin-Miller primality test: Composite numbers which pass it, Mathematics of Computation, vol. 64, no 209, 1995, pp. 355-361.

F. Arnault. The Rabin-Monier theorem for Lucas pseudoprimes, Mathematics of Computation, vol. 66, no 218, April 1997, pp. 869-881.

A. H. Beiler, Recreations in the Theory of Numbers, Dover Publications, Inc. New York, 1966, Table 18, Page 44.

D. M. Burton, Elementary Number Theory, 5th ed., McGraw-Hill, 2002.

CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 87.

Pratibha Ghatage (p.ghatage(AT)csuohio.edu) and Brian Scott (b.scott(AT)csuohio.edu), When is (a+b)^n == a^n + b^n (mod n)?, College Mathematics Journal, Vol. 36, No. 4 (Sep 2005), p. 322.

Granville, Andrew and Pomerance, Carl, Two contradictory conjectures concerning Carmichael numbers. Math. Comp. 71 (2002), no. 238, 883-908.

R. K. Guy, Unsolved Problems in Number Theory, A13.

G. Jaeschke, The Carmichael numbers to 10^12, Math. Comp., 55 (1990), 383-389.

D. H. Lehmer, Errata for Poulet's table, Math. Comp., 25 (1971), 944-945.

O. Ore, Number Theory and Its History, McGraw-Hill, 1948, Reprinted by Dover Publications, 1988, Chapter 14.

P. Poulet, Tables des nombres composes verifiant le theoreme du Fermat pour le module 2 jusqu'a 100.000.000, Sphinx (Brussels), 8 (1938), 42-45.

W. Sierpi\'{n}ski, A Selection of Problems in the Theory of Numbers. Macmillan, NY, 1964, p. 51.

N. J. A. Sloane, Table of n, a(n) for n = 1..10000 (from the Pinch web site mentioned below)

Joerg Arndt, Fxtbook

W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703-722.

F. Arnault, Thesis

J. Bernheiden, Carmichael numbers (Text in German)

C. K. Caldwell, The Prime Glossary, Carmichael number

Harvey Dubner, Journal of Integer Sequences, Vol. 5 (2002) Article 02.2.1, Carmichael Numbers of the form (6m+1)(12m+1)(18m+1).

A. Granville, Papers on Carmichael numbers

A. Granville, Primality testing and Carmichael numbers, Notices Amer. Math. Soc., 39 (No. 7, 1992), 696-700.

Renaud Lifchitz, A generalization of the Korselt's criterion - Nested Carmichael numbers

Yoshio Mimura, Carmichael Numbers up to 10^12

Math Reference Project, Carmichael Numbers

R. G. E. Pinch, Carmichael numbers up to 10^16 (FTP)

R. G. E. Pinch, The Carmichael numbers up to 10^17

Richard Pinch, Carmichael numbers up to 10^18, April 2006.

R. G. E. Pinch, The Carmichael numbers up to 10^18

F. Richman, Primality testing with Fermat's little theorem

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.

Wikipedia, Carmichael number

Index entries for sequences related to Carmichael numbers.

n is composite and square-free and for p prime, p|n => p-1|n-1.

A composite odd number n is a Carmichael number if and only if n is squarefree and p-1 divides n-1 for every prime p dividing n (Korselt, 1899)

Cases[Range[100000], n_ /; Mod[n, CarmichaelLambda[n]] == 1 && ! PrimeQ[n]] - Artur Jasinski (grafix(AT)csl.pl), Apr 05 2008

Cf. A001567, A064238-A064262, A006931, A055553, A002322, A083737, A153581.

Sequence in context: A047713 A006971 A104016 this_sequence A087788 A083733 A048123

Adjacent sequences: A002994 A002995 A002996 this_sequence A002998 A002999 A003000

nonn,nice,easy

N. J. A. Sloane (njas(AT)research.att.com).

Replaced list of Carmichael numbers up to 10^9 by list up to 10^12. - Jan Kristian Haugland (admin(AT)neutreeko.net), Mar 25 2009