This site is supported by donations to The OEIS Foundation.



The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002997 Carmichael numbers: composite numbers n such that a^(n-1) == 1 (mod n) for every a coprime to n.
(Formerly M5462)
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461 (list; graph; refs; listen; history; text; internal format)



n is composite and squarefree and for p prime, p|n => p-1|n-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.

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)

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, Aug 31 2005

Alford et al. have constructed a Carmichael number with 10333229505 prime factors, and have also constructed Carmichael numbers with k prime factors for every k between 3 and 19565220. - Jonathan Vos Post, Apr 01 2012

Thomas Wright proved that for any numbers b and M in N with gcd(b,M) = 1, there are infinitely many Carmichael numbers m such that m = b mod M. - Jonathan Vos Post, Dec 27 2012

Composite numbers n relatively prime to 1^(n-1)+2^(n-1)+...+(n-1)^(n-1). - Thomas Ordowski, Oct 09 2013

Composite numbers n such that A063994(n) = A000010(n). - Thomas Ordowski, Dec 17 2013

Odd composite numbers n such that n divides A002445((n-1)/2). - Robert Israel, Oct 02 2015

If n is a Carmichael number and gcd(b,n)=gcd(b-1,n)=1, then (b^n-1)/(b-1) is a pseudoprime to base b; by Steuerwald's theorem, see the reference in A005935. - Thomas Ordowski, Apr 17 2016

Composite numbers n such that p^n == p (mod n) for every prime p <= A285512(n). - Max Alekseyev and Thomas Ordowski, Apr 20 2017

If a composite m < A285549(n) and p^m == p (mod m) for every prime p <= prime(n), then m is a Carmichael number. - Thomas Ordowski, Apr 23 2017

The sequence of all Carmichael numbers can be defined as follows: a(1) = 561, a(n+1) = smallest composite k > a(n) such that p^k == p (mod k) for every prime p <= n+2. - Thomas Ordowski, Apr 24 2017


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.

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

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ński, A Selection of Problems in the Theory of Numbers. Macmillan, NY, 1964, p. 51.

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


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

W. R. Alford, Jon Grantham, Steven Hayman, Andrew Shallue, Constructing Carmichael numbers through improved subset-product algorithms, arXiv:1203.6664v1 [math.NT], Mar 29 2012.

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

W. R. Alford, A. Granville, and C. Pomerance (1994). "On the difficulty of finding reliable witnesses". Lecture Notes in Computer Science 877, 1994, pp. 1-16.

F. Arnault, Thesis

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.

Joerg Arndt, Matters Computational (The Fxtbook), p. 786

Eric Bach, Rex Fernando, Infinitely Many Carmichael Numbers for a Modified Miller-Rabin Prime Test, arXiv preprint arXiv:1512.00444 [math.NT], 2015.

J. Bernheiden, Carmichael numbers (Text in German)

J. Brillhart, N. J. A. Sloane, J. D. Swift, Correspondence, 1972

Ronald Joseph Burthe, Jr. Upper bounds for least witnesses and generating sets, Acta Arith. 80 (1997), no. 4, 311-326.

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).

James Emery, Number Theory, 2013.

Jan Feitsma and William Galway, Tables of pseudoprimes and related data

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

A. Granville, Papers on Carmichael numbers

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

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

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. 25 944 1971.

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

Romeo Meštrović, Generalizations of Carmichael numbers I, arXiv:1305.1867v1 [math.NT], May 04 2013.

R. Mestrovic, On a Congruence Modulo n^3 Involving Two Consecutive Sums of Powers, Journal of Integer Sequences, Vol. 17 (2014), 14.8.4.

Yoshio Mimura, Carmichael Numbers up to 10^12 [broken link, WayBackMachine]

Math Reference Project, Carmichael Numbers

R. G. E. Pinch, Tables relating to Carmichael numbers

R. G. E. Pinch, Carmichael numbers up to 10^15, 10^16, 10^17, 10^18, 10^19, and 10^21

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

Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1. - From N. J. A. Sloane, Feb 07 2013

Eric Weisstein's World of Mathematics, Carmichael Number, Knoedel Numbers, and Pseudoprime

Wikipedia, Carmichael number

Thomas Wright, Infinitely many Carmichael numbers in arithmetic progressions, To appear in the Bulletin of the London Mathematical Society, arXiv:1212.5850v1 [math.NT], 2012.

Index entries for sequences related to Carmichael numbers.


filter:= proc(n)

  local q;

  if isprime(n) then return false fi;

  if 2 &^ (n-1) mod n <> 1 then return false fi;

  if not numtheory:-issqrfree(n) then return false fi;

  for q in numtheory:-factorset(n) do

    if (n-1) mod (q-1) <> 0 then return false fi



end proc:

select(filter, [seq(2*k+1, k=1..10^6)]); # Robert Israel, Dec 29 2014


Cases[Range[1, 100000, 2], n_ /; Mod[n, CarmichaelLambda[n]] == 1 && ! PrimeQ[n]] (* Artur Jasinski, Apr 05 2008 *)


(PARI) Korselt(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]>1||(n-1)%(f[i, 1]-1), return(0))); 1

isA002997(n)=n%2 && !isprime(n) && Korselt(n) && n>1 \\ Charles R Greathouse IV, Jun 10 2011

(PARI) is_A002997(n)=my(f); bittest(n, 0) && !for(i=1, #f=factor(n)~, (f[2, i]==1 && n%(f[1, i]-1)==1)||return) && #f>1 \\ M. F. Hasler, Aug 24 2012


a002997 n = a002997_list !! (n-1)

a002997_list = [x | x <- a024556_list,

all (== 0) $ map ((mod (x - 1)) . (subtract 1)) $ a027748_row x]

-- Reinhard Zumkeller, Apr 12 2012

(MAGMA) [n: n in [3..53*10^4 by 2] | not IsPrime(n) and n mod CarmichaelLambda(n) eq 1]; // Bruno Berselli, Apr 23 2012


Cf. A001567, A002445, A002322, A006931, A024556, A027748, A055553, A064238-A064262, A083737, A135717, A141711, A153581, A285512, A285549.

Sequence in context: A270698 A218483 A104016 * A087788 A173703 A135720

Adjacent sequences:  A002994 A002995 A002996 * A002998 A002999 A003000




N. J. A. Sloane


Links for lists of Carmichael numbers updated. - Jan Kristian Haugland (admin(AT)neutreeko.net), Mar 25 2009 and Danny Rorabaugh, May 05 2017

Minor edit of Mathematica code from Zak Seidov, Feb 16 2011



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 28 21:38 EDT 2017. Contains 287241 sequences.