

A002997


Carmichael numbers: composite numbers n such that a^(n1) == 1 (mod n) for every a coprime to n.
(Formerly M5462)


130



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)



OFFSET

1,1


COMMENTS

n is composite and squarefree and for p prime, pn => p1n1.
An odd composite number n is a pseudoprime to base a iff a^(n1) == 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 p1 divides n1 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 such that gcd(1^(n1)+2^(n1)+...+(n1)^(n1),n)=1.  Thomas Ordowski, Oct 09 2013
Composite numbers n such that A063994(n) = A000010(n).  Thomas Ordowski, Dec 17 2013


REFERENCES

F. Arnault, Constructing Carmichael numbers which are strong pseudoprimes to several bases, Journal of Symbolic Computation, vol. 20, no 2, Aug. 1995, pp. 151161.
F. Arnault. RabinMiller primality test: Composite numbers which pass it, Mathematics of Computation, vol. 64, no 209, 1995, pp. 355361.
F. Arnault. The RabinMonier theorem for Lucas pseudoprimes, Mathematics of Computation, vol. 66, no 218, April 1997, pp. 869881.
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., McGrawHill, 2002.
CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 87.
James Emery, Number Theory, 2013; http://www.stem2.org/je/numbertheory.pdf
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.
R. K. Guy, Unsolved Problems in Number Theory, A13.
G. Jaeschke, The Carmichael numbers to 10^12, Math. Comp., 55 (1990), 383389.
D. H. Lehmer, Errata for Poulet's table, Math. Comp., 25 (1971), 944945.
O. Ore, Number Theory and Its History, McGrawHill, 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), 4245.
Vladimir Shevelev, The number of permutations with prescribed updown structure as a function of two variables, INTEGERS, 12 (2012), #A1.  From N. J. A. Sloane, Feb 07 2013
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).


LINKS

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 subsetproduct 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, 703722.
W. R. Alford, A. Granville, and C. Pomerance (1994). "On the difficulty of finding reliable witnesses". Lecture Notes in Computer Science 877, 1994, pp. 116.
F. Arnault, Thesis
Joerg Arndt, Matters Computational (The Fxtbook), p. 786
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).
Jan Feitsma and William Galway, Tables of pseudoprimes and related data
A. Granville, Papers on Carmichael numbers
A. Granville, Primality testing and Carmichael numbers, Notices Amer. Math. Soc., 39 (No. 7, 1992), 696700.
Andrew Granville and Carl Pomerance, Two contradictory conjectures concerning Carmichael numbers, Math. Comp. 71 (2002), no. 238, 883908.
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 4, 2013.
Yoshio Mimura, Carmichael Numbers up to 10^12 [broken link]
Math Reference Project, Carmichael Numbers
R. G. E. Pinch, Tables relating to Carmichael numbers
R. G. E. Pinch, Carmichael numbers up to 10^16
R. G. E. Pinch, The Carmichael numbers up to 10^17, arXiv:math/0504119 [math.NT], 2005.
R. G. E. Pinch, Carmichael numbers up to 10^18, April 2006.
R. G. E. Pinch, The Carmichael numbers up to 10^18, arXiv:math/0604376 [math.NT], 2006.
F. Richman, Primality testing with Fermat's little theorem
Eric Weisstein's World of Mathematics, Carmichael Number
Eric Weisstein's World of Mathematics, Knoedel Numbers
Eric Weisstein's World of Mathematics, 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].
Index entries for sequences related to Carmichael numbers.


MATHEMATICA

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


PROG

(PARI) Korselt(n)=my(f=factor(n)); for(i=1, #f[, 1], if(f[i, 2]>1(n1)%(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
(Haskell)
a002997 n = a002997_list !! (n1)
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


CROSSREFS

Cf. A001567, A064238A064262, A006931, A055553, A002322, A083737, A153581, A024556, A027748.
Sequence in context: A006971 A218483 A104016 * A087788 A173703 A135720
Adjacent sequences: A002994 A002995 A002996 * A002998 A002999 A003000


KEYWORD

nonn,nice,changed


AUTHOR

N. J. A. Sloane


EXTENSIONS

List of Carmichael numbers up to 10^9 replaced with list up to 10^12 by Jan Kristian Haugland (admin(AT)neutreeko.net), Mar 25 2009
Minor edit of Mathematica code from Zak Seidov, Feb 16 2011


STATUS

approved



