login
This site is supported by donations to The OEIS Foundation.
Logo

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002997 Carmichael numbers: composite numbers n such that a^{n-1} = 1 ( mod n) if a is prime to n.
(Formerly M5462)
91
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; internal format)
OFFSET

1,1

COMMENTS

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

REFERENCES

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

Joerg Arndt, Fxtbook, p.786

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, Carmichael Number

Eric Weisstein's World of Mathematics, Knoedel Numbers

Eric Weisstein's World of Mathematics, Pseudoprime

Wikipedia, Carmichael number

Index entries for sequences related to Carmichael numbers.

FORMULA

n is composite and squarefree 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)

MATHEMATICA

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

PROG

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

\\ Charles R Greathouse IV, Jun 10 2011

CROSSREFS

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

Sequence in context: A047713 A006971 A104016 * A087788 A173703 A083733

Adjacent sequences:  A002994 A002995 A002996 * A002998 A002999 A003000

KEYWORD

nonn,nice

AUTHOR

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

EXTENSIONS

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

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

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

Content is available under The OEIS End-User License Agreement .

Last modified February 12 03:59 EST 2012. Contains 205360 sequences.