A005935 -id:A005935 - cp's OEIS frontend

A052155 Pseudoprimes to both base 2 and base 3, i.e., intersection of A001567 and A005935.

1105, 1729, 2465, 2701, 2821, 6601, 8911, 10585, 15841, 18721, 29341, 31621, 41041, 46657, 49141, 52633, 63973, 75361, 83333, 83665, 88561, 90751, 93961, 101101, 104653, 107185, 115921, 126217, 162401, 172081, 176149, 188461

Offset: 1

Harvey P. Dale, Jan 24 2000

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 (first 201 terms from R. J. Mathar)
J. Bernheiden, Pseudoprimes (Text in German)
Index entries for sequences related to pseudoprimes

Cf. A001567, A005935, A083737.

Select[ Range[228240], !PrimeQ[ # ] && PowerMod[2, # - 1, # ] == 1 && PowerMod[3, # - 1, # ] == 1 &]

is(n)=!isprime(n)&&Mod(2,n)^(n-1)==1&&Mod(3,n)^(n-1)==1 \\ Charles R Greathouse IV, Apr 12 2012

A001567 Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers.

Original entry on oeis.org

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341

Offset: 1

N. J. A. Sloane

A composite number n is a Fermat pseudoprime to base b if and only if b^(n-1) == 1 (mod n). Fermat pseudoprimes to base 2 are often simply called pseudoprimes.
Theorem: If both numbers q and 2q - 1 are primes (q is in the sequence A005382) and n = q*(2q-1) then 2^(n-1) == 1 (mod n) (n is in the sequence) if and only if q is of the form 12k + 1. The sequence 2701, 18721, 49141, 104653, 226801, 665281, 721801, ... is related. This subsequence is also a subsequence of the sequences A005937 and A020137. - Farideh Firoozbakht, Sep 15 2006
Also, composite odd numbers n such that n divides 2^n - 2 (cf. A006935). It is known that all primes p divide 2^(p-1) - 1. There are only two known numbers n such that n^2 divides 2^(n-1) - 1, A001220(n) = {1093, 3511} Wieferich primes p: p^2 divides 2^(p-1) - 1. 1093^2 and 3511^2 are the terms of a(n). - Alexander Adamchuk, Nov 06 2006
An odd composite number 2n + 1 is in the sequence if and only if multiplicative order of 2 (mod 2n+1) divides 2n. - Ray Chandler, May 26 2008
The Carmichael numbers A002997 are a subset of this sequence. For the Sarrus numbers which are not Carmichael numbers, see A153508. - Artur Jasinski, Dec 28 2008
An odd number n greater than 1 is a Fermat pseudoprime to base b if and only if ((n-1)! - 1)*b^(n-1) == -1 (mod n). - Arkadiusz Wesolowski, Aug 20 2012
The name "Sarrus numbers" is after Frédéric Sarrus, who, in 1819, discovered that 341 is a counterexample to the "Chinese hypothesis" that n is prime if and only if 2^n is congruent to 2 (mod n). - Alonso del Arte, Apr 28 2013
The name "Poulet numbers" appears in Monografie Matematyczne 42 from 1932, apparently because Poulet in 1928 produced a list of these numbers (cf. Miller, 1975). - Felix Fröhlich, Aug 18 2014
Numbers n > 2 such that (n-1)! + 2^(n-1) == 1 (mod n). Composite numbers n such that (n-2)^(n-1) == 1 (mod n). - Thomas Ordowski, Feb 20 2016
The only twin pseudoprimes up to 10^13 are 4369, 4371. - Thomas Ordowski, Feb 12 2016
Theorem (A. Rotkiewicz, 1965): (2^p-1)*(2^q-1) is a pseudoprime if and only if p*q is a pseudoprime, where p,q are different primes. - Thomas Ordowski, Mar 31 2016
Theorem (W. Sierpiński, 1947): if n is a pseudoprime (odd or even), then 2^n-1 is a pseudoprime. - Thomas Ordowski, Apr 01 2016
If 2^n-1 is a pseudoprime, then n is a prime or a pseudoprime (odd or even). - Thomas Ordowski, Sep 05 2016
From Amiram Eldar, Jun 19 2021, Apr 21 2024: (Start)
Erdős (1950) called these numbers "almost primes".
According to Erdős (1949) and Piza (1954), the term "pseudoprime" was coined by D. H. Lehmer.
Named after the French mathematician Pierre de Fermat (1607-1665), or, alternatively, after the Belgian mathematician Paul Poulet (1887-1946), or, the French mathematician Pierre Frédéric Sarrus (1798-1861). (End)
If m is a term of this sequence, then (m-1)/ord(2,m) >= 5, where ord(a,m) is the multiplicative order of a modulo m; see my link below. Actually, it seems that we always have (m-1)/ord(2,m) >= 9. - Jianing Song, Nov 04 2024

Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, p. 80.
Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section A12, pp. 44-50.
George P. Loweke, The Lore of Prime Numbers. New York: Vantage Press (1982), p. 22.
Øystein Ore, Number Theory and Its History, McGraw-Hill, 1948.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 88-92.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 145.

N. J. A. Sloane, Table of n, a(n) for n = 1..101629 [The pseudoprimes up to 10^12, from Richard Pinch's web site - see links below]
Jonathan Bayless and Paul Kinlaw, Explicit Bounds for the Sum of Reciprocals of Pseudoprimes and Carmichael Numbers, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.4.
Jens Bernheiden, Pseudoprimes (Text in German).
John Brillhart, N. J. A. Sloane, J. D. Swift, Correspondence, 1972.
Carlos M. da Fonseca and Anthony G. Shannon, A formal operator involving Fermatian numbers, Notes Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 491-498.
Paul Erdős, On the converse of Fermat's theorem, The American Mathematical Monthly, Vol. 56, No. 9 (1949), pp. 623-624; alternative link.
Paul Erdős, On almost primes, Amer. Math. Monthly, Vol. 57, No. 6 (1950), pp. 404-407; alternative link.
Jan Feitsma, The pseudoprimes below 2^64.
William Galway, Tables of pseudoprimes and related data [Includes a file with pseudoprimes up to 2^64.]
Richard K. Guy, The strong law of small numbers. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712. [Annotated scanned copy]
Paul Kinlaw, The reciprocal sums of pseudoprimes and Carmichael numbers, Mathematics of Computation (2023).
D. H. Lehmer, Guide to Tables in the Theory of Numbers, Bulletin No. 105, National Research Council, Washington, DC, 1941, p. 48.
D. H. Lehmer, Errata for Poulet's table, Math. Comp., Vol. 25, No. 116 (1971), pp. 944-945.
D. H. Lehmer, Errata for Poulet's table. [annotated scanned copy]
Gérard P. Michon, Pseudoprimes.
J. C. P. Miller, On factorization, with a suggested new approach, Math. Comp., Vol. 29, No. 129 (1975), pp. 155-172. - _Felix Fröhlich_, Aug 18 2014
Robert Morris, Some observations on the converse of Fermat's theorem, unpublished memorandum, Oct 03 1973.
Richard Pinch, Pseudoprimes.
P. A. Piza, Fermat Coefficients, Mathematics Magazine, Vol. 27, No. 3 (1954), pp. 141-146.
Carl Pomerance & N. J. A. Sloane, Correspondence, 1991.
Paul Poulet, Tables des nombres composés vérifiant le théorème de Fermat pour le module 2 jusqu'à 100.000.000, Sphinx (Brussels), Vol. 8 (1938), pp. 42-45. [annotated scanned copy]
Fred Richman, Primality testing with Fermat's little theorem.
Andrzej Rotkiewicz, Sur les nombres pseudopremiers de la forme MpMq, Elemente der Mathematik, Vol. 20 (1965), pp. 108-109.
Waclaw Sierpiński, Remarque sur une hypothèse des Chinois concernant les nombres (2^n-2)/n, Colloquium Mathematicum, Vol. 1 (1947), p. 9.
Waclaw Sierpiński, Elementary Theory of Numbers, Państ. Wydaw. Nauk., Warszawa, 1964, p. 215.
Jianing Song, Notes on Fermat Pseudoprimes.
Eric Weisstein's World of Mathematics, Chinese Hypothesis, Fermat Pseudoprime, Poulet Number, and Pseudoprime.
Wikipedia, Chinese hypothesis and Pseudoprime.
Index entries for sequences related to pseudoprimes

Cf. A002997, A005382, A020137, A052155, A083737, A084653, A153508.
Cf. A001220 = Wieferich primes p: p^2 divides 2^(p-1) - 1.
Cf. A005935, A005936, A005937, A005938, A005939, A020136-A020228 (pseudoprimes to bases 3 through 100).

[n: n in [3..3*10^4 by 2] | IsOne(Modexp(2,n-1,n)) and not IsPrime(n)]; // Bruno Berselli, Jan 17 2013

select(t -> not isprime(t) and 2 &^(t-1) mod t = 1, [seq(i,i=3..10^5,2)]); # Robert Israel, Feb 18 2016

Select[Range[3,30000,2], ! PrimeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &] (* Farideh Firoozbakht, Sep 15 2006 *)

q=1;vector(50,i,until( !isprime(q) & (1<<(q-1)-1)%q == 0, q+=2);q) \\ M. F. Hasler, May 04 2007

is_A001567(n)={Mod(2,n)^(n-1)==1 && !isprime(n) && n>1}  \\ M. F. Hasler, Oct 07 2012, updated to current PARI syntax and to exclude even pseudoprimes on Mar 01 2019

Sum_{n>=1} 1/a(n) is in the interval (0.015260, 33) (Bayless and Kinlaw, 2017). The upper bound was reduced to 0.0911 by Kinlaw (2023). - Amiram Eldar, Oct 15 2020, Feb 24 2024

More terms from David W. Wilson, Aug 15 1996
Replacement of broken geocities link by Jason G. Wurtzel, Sep 05 2010
"Poulet numbers" added to name by Joerg Arndt, Aug 18 2014

A002997 Carmichael numbers: composite numbers k such that a^(k-1) == 1 (mod k) for every a coprime to k.

Original entry on oeis.org

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, 530881, 552721

Offset: 1

N. J. A. Sloane

V. Šimerka found the first 7 terms of this sequence 25 years before Carmichael (see the link and also the remark of K. Conrad). - Peter Luschny, Apr 01 2019
k is composite and squarefree and for p prime, p|k => p-1|k-1.
An odd composite number k is a pseudoprime to base a iff a^(k-1) == 1 (mod k). A Carmichael number is an odd composite number k which is a pseudoprime to base a for every number a prime to k.
A composite odd number k is a Carmichael number if and only if k is squarefree and p-1 divides k-1 for every prime p dividing k. (Korselt, 1899)
Ghatage and Scott prove using Fermat's little theorem that (a+b)^k == a^k + b^k (mod k) (the freshman's dream) exactly when k 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 m prime factors for every m 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 k such that k == b (mod M). - Jonathan Vos Post, Dec 27 2012
Composite numbers k relatively prime to 1^(k-1) + 2^(k-1) + ... + (k-1)^(k-1). - Thomas Ordowski, Oct 09 2013
Composite numbers k such that A063994(k) = A000010(k). - Thomas Ordowski, Dec 17 2013
Odd composite numbers k such that k divides A002445((k-1)/2). - Robert Israel, Oct 02 2015
If k is a Carmichael number and gcd(b-1,k)=1, then (b^k-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 k such that p^k == p (mod k) for every prime p <= A285512(k). - 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
An integer m > 1 is a Carmichael number if and only if m is squarefree and each of its prime divisors p satisfies both s_p(m) >= p and s_p(m) == 1 (mod p-1), where s_p(m) is the sum of the base-p digits of m. Then m is odd and has at least three prime factors. For each prime factor p, the sharp bound p <= a*sqrt(m) holds with a = sqrt(17/33) = 0.7177.... See Kellner and Sondow 2019. - Bernd C. Kellner and Jonathan Sondow, Mar 03 2019
Carmichael numbers are special polygonal numbers A324973. The rank of the n-th Carmichael number is A324975(n). See Kellner and Sondow 2019. - Jonathan Sondow, Mar 26 2019
An odd composite number m is a Carmichael number iff m divides denominator(Bernoulli(m-1)). The quotient is A324977. See Pomerance, Selfridge, & Wagstaff, p. 1006, and Kellner & Sondow, section on Bernoulli numbers. - Jonathan Sondow, Mar 28 2019
This is setwise difference A324050 \ A008578. Many of the same identities apply also to A324050. - Antti Karttunen, Apr 22 2019
If k is a Carmichael number, then A309132(k) = A326690(k). The proof generalizes that of Theorem in A309132. - Jonathan Sondow, Jul 19 2019
Composite numbers k such that A111076(k)^(k-1) == 1 (mod k). Proof: the multiplicative order of A111076(k) mod k is equal to lambda(k), where lambda(k) = A002322(k), so lambda(k) divides k-1, qed. - Thomas Ordowski, Nov 14 2019
For all positive integers m, m^k - m is divisible by k, for all k > 1, iff k is either a Carmichael number or a prime, as is used in the proof by induction for Fermat's Little Theorem. Also related are A182816 and A121707. - Richard R. Forberg, Jul 18 2020
From Amiram Eldar, Dec 04 2020, Apr 21 2024: (Start)
Ore (1948) called these numbers "Numbers with the Fermat property", or, for short, "F numbers".
Also called "absolute pseudoprimes". According to Erdős (1949) this term was coined by D. H. Lehmer.
Named by Beeger (1950) after the American mathematician Robert Daniel Carmichael (1879 - 1967). (End)
For ending digit 1,3,5,7,9 through the first 10000 terms, we see 80.3, 4.1, 7.4, 3.8 and 4.3% apportionment respectively. Why the bias towards ending digit "1"? - Bill McEachen, Jul 16 2021
It seems that for any m > 1, the remainders of Carmichael numbers modulo m are biased towards 1. The number of terms congruent to 1 modulo 4, 6, 8, ..., 24 among the first 10000 terms: 9827, 9854, 8652, 8034, 9682, 5685, 6798, 7820, 7880, 3378 and 8518. - Jianing Song, Nov 08 2021
Alford, Granville and Pomerance conjectured in their 1994 paper that a statement analogous to Bertrand's Postulate could be applied to Carmichael numbers. This has now been proved by Daniel Larsen, see link below. - David James Sycamore, Jan 17 2023

N. G. W. H. Beeger, On composite numbers n for which a^n == 1 (mod n) for every a prime to n, Scripta Mathematica, Vol. 16 (1950), pp. 133-135.
Albert H. Beiler, Recreations in the Theory of Numbers, Dover Publications, Inc. New York, 1966, Table 18, Page 44.
David M. Burton, Elementary Number Theory, 5th ed., McGraw-Hill, 2002.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 142.
CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 87.
Richard K. Guy, Unsolved Problems in Number Theory, A13.
Øystein Ore, Number Theory and Its History, McGraw-Hill, 1948, Reprinted by Dover Publications, 1988, Chapter 14.
Paul Poulet, Tables des nombres composés vérifiant le théorème du Fermat pour le module 2 jusqu'à 100.000.000, Sphinx (Brussels), 8 (1938), 42-45.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 22, 100-103.
Wacław 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).
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 145-146.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See entry 561 at p. 157.

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, and Andrew Shallue, Constructing Carmichael numbers through improved subset-product algorithms, Mathematics of Computation, Vol. 83, No. 286 (2014), pp. 899-915, arXiv preprint, 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.
François Arnault, Thesis.
François Arnault, Constructing Carmichael numbers which are strong pseudoprimes to several bases, Journal of Symbolic Computation, vol. 20, no 2, Aug. 1995, pp. 151-161.
François Arnault, Rabin-Miller primality test: Composite numbers which pass it, Mathematics of Computation, vol. 64, no 209, 1995, pp. 355-361.
François 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 and Rex Fernando, Infinitely Many Carmichael Numbers for a Modified Miller-Rabin Prime Test, ISSAC '16: Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, July 2016, pp. 47-54, arXiv preprint, arXiv:1512.00444 [math.NT], 2015.
Sunghan Bae, Su Hu, and Min Sha, On the Carmichael rings, Carmichael ideals and Carmichael polynomials, arXiv:1809.05432 [math.NT], 2018.
Jonathan Bayless and Paul Kinlaw, Explicit Bounds for the Sum of Reciprocals of Pseudoprimes and Carmichael Numbers, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.4.
Jens Bernheiden, Carmichael numbers (Text in German).
John D. Brillhart, N. J. A. Sloane, and 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.
R. D. Carmichael, Note on a new number theory function, Bull. Amer. Math. Soc. 16 (1910), 232-238.
Keith Conrad, Carmichael numbers and Korselt's criterion, expository paper (2016), 1-3.
K. A. Draziotis, V. Martidis, and S. Tiganourias, Product Subset Problem: Applications to number theory and cryptography, arXiv:2002.07095 [math.NT], 2020. See also Chapter 5, Analysis, Cryptography and Information Science, World Scientific (2023), p. 108.
Harvey Dubner, Carmichael Numbers of the form (6m+1)(12m+1)(18m+1), Journal of Integer Sequences, Vol. 5 (2002) Article 02.2.1.
James Emery, Number Theory, 2013. [Broken link]
Paul Erdős, On the converse of Fermat's theorem, The American Mathematical Monthly, Vol. 56, No. 9 (1949), pp. 623-624; alternative link.
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.
Claude Goutier, Compressed text file carm10e22.7z containing all the Carmichael numbers up to 10^22. [Local copy, with permission. This is a very large file.]
Andrew Granville, Papers on Carmichael numbers.
Andrew 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.
Gerhard Jaeschke, The Carmichael numbers to 10^12, Math. Comp., Vol. 55, No. 191 (1990), pp. 383-389.
Eugene Karolinsky and Dmytro Seliutin, Carmichael numbers for GL(m), arXiv:2001.10315 [math.NT], 2020.
Bernd C. Kellner, On primary Carmichael numbers, Integers 22 (2022), #A38, 39 pp.; arXiv:1902.11283 [math.NT], 2019.
Bernd C. Kellner and Jonathan Sondow, On Carmichael and polygonal numbers, Bernoulli polynomials, and sums of base-p digits, Integers 21 (2021), #A52, 21 pp.; arXiv:1902.10672 [math.NT], 2019.
Paul Kinlaw, The reciprocal sums of pseudoprimes and Carmichael numbers, Mathematics of Computation (2023).
A. Korselt, G. Tarry, I. Franel, and G. Vacca, Problème chinois, L'intermédiaire des mathématiciens 6 (1899), 142-144.
Daniel Larsen, Bertrand's Postulate for Carmichael Numbers, arXiv:2111.06963 [math.NT], 2021.
D. H. Lehmer, Errata for Poulet's table, Math. Comp., 25 (1971), 944-945. 25 944 1971.
Max Lewis and Victor Scharaschkin, k-Lehmer and k-Carmichael Numbers, Integers, 16 (2016), #A80.
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.
Romeo Meštrović, 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, The Carmichael numbers up to 10^18, 2008.
R. G. E. Pinch, Carmichael numbers up to 10^15, 10^16, 10^16 to 10^17, 10^17 to 10^18, 10^19, and 10^21.
Carl Pomerance, J. L. Selfridge, and Samuel S. Wagstaff, Jr., The pseudoprimes to 25*10^9, Math. Comp., Vol. 35, No. 151 (1980), pp. 1003-1026.
Carl Pomerance and N. J. A. Sloane, Correspondence, 1991.
Fred 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
Václav Šimerka, Zbytky z arithmetické posloupnosti, (On the remainders of an arithmetic progression), Časopis pro pěstování matematiky a fysiky. 14 (1885), 221-225.
Eric Weisstein's World of Mathematics, Carmichael Number, Knoedel Numbers, and Pseudoprime.
Wikipedia, Carmichael number.
Thomas Wright, Infinitely many Carmichael numbers in arithmetic progressions, Bulletin of the London Mathematical Society, 45 (2013) 943-952, arXiv preprint, arXiv:1212.5850 [math.NT], Dec 2012.
Index entries for sequences related to Carmichael numbers.

Cf. A001567, A002445, A002322, A006931, A024556, A027748, A055553, A064238-A064262, A083737, A087441, A087442, A135717, A141711, A153581, A225498, A285512, A285549, A309132, A324290, A324315, A324316, A324973, A324975, A324977, A326690.

Subsequence of A324050.

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

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

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
  od:
  true;
end proc:
select(filter, [seq(2*k+1,k=1..10^6)]); # Robert Israel, Dec 29 2014
isA002997 := n -> 0 = modp(n-1, numtheory:-lambda(n)) and not isprime(n) and n <> 1:
select(isA002997, [$1..10000]); # Peter Luschny, Jul 21 2019

Cases[Range[1,100000,2], n_ /; Mod[n, CarmichaelLambda[n]] == 1 && ! PrimeQ[n]] (* Artur Jasinski, Apr 05 2008; minor edit from Zak Seidov, Feb 16 2011 *)
Select[Range[1,600001,2],CompositeQ[#]&&Mod[#,CarmichaelLambda[#]]==1&] (* Harvey P. Dale, Jul 08 2023 *)

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

is_A002997(n, F=factor(n)~)={ #F>2 && !foreach(F,f,(n%(f[1]-1)==1 && f[2]==1) || return)} \\ No need to check parity: if efficiency is needed, scan only odd numbers. - M. F. Hasler, Aug 24 2012, edited Mar 24 2022

from itertools import islice
from sympy import nextprime, factorint
def A002997_gen(): # generator of terms
    p, q = 3, 5
    while True:
        for n in range(p+2,q,2):
            f = factorint(n)
            if max(f.values()) == 1 and not any((n-1) % (p-1) for p in f):
                yield n
        p, q = q, nextprime(q)
A002997_list = list(islice(A002997_gen(),20)) # Chai Wah Wu, May 11 2022

def isCarmichael(n):
    if n == 1 or is_even(n) or is_prime(n):
        return False
    factors = factor(n)
    for f in factors:
        if f[1] > 1: return False
        if (n - 1) % (f[0] - 1) != 0:
            return False
    return True
print([n for n in (1..20000) if isCarmichael(n)]) # Peter Luschny, Apr 02 2019

Sum_{n>=1} 1/a(n) is in the interval (0.004706, 27.8724) (Bayless and Kinlaw, 2017). The upper bound was reduced to 0.0058 by Kinlaw (2023). - Amiram Eldar, Oct 26 2020, Feb 24 2024

Links for lists of Carmichael numbers updated by Jan Kristian Haugland, Mar 25 2009 and Danny Rorabaugh, May 05 2017

A020229 Strong pseudoprimes to base 3.

Original entry on oeis.org

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, 105163, 111361, 112141, 148417, 152551, 182527, 188191, 211411, 218791, 221761, 226801

Offset: 1

David W. Wilson

nonn

Charles R Greathouse IV, Table of n, a(n) for n = 1..24767 (first 752 terms from R. J. Mathar)
Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792
Eric Weisstein's World of Mathematics, Strong Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A001262, A072276, A056915, A074773, A005935.

sppQ[n_?EvenQ, ] := False; sppQ[n?PrimeQ, ] := False; sppQ[n, b_] := (s = IntegerExponent[n-1, 2]; d = (n-1)/2^s; If[PowerMod[b, d, n] == 1, Return[True], Do[If[PowerMod[b, d*2^r, n] == n-1, Return[True]], {r, 0, s-1}]]); A020229 = {}; lst = {}; k = 3; While[k < 500000, If[sppQ[k, 3], Print[k]; AppendTo[lst, k]]; k += 2]; lst (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)

is_A020229(n,b=3)={ bittest(n,0) || return;ispseudoprime(n) && return;my(d=(n-1)>>valuation(n-1,2));Mod(b,n)^d==1 || until(n-1<=d*=2,Mod(b,n)^d+1 || return(1))} \\ M. F. Hasler, Jul 19 2012

A005936 Pseudoprimes to base 5.

Original entry on oeis.org

4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, 11041, 11476, 12801, 13021, 13333, 13981, 14981, 15751, 15841, 16297, 17767, 21361, 22791, 23653, 24211, 25327, 25351, 29341, 29539

Offset: 1

N. J. A. Sloane

nonn

According to Karsten Meyer, 4 should be excluded, following the strict definition in Crandall and Pomerance. - May 16 2006
Theorem: If both numbers q and (2q - 1) are primes (q is in the sequence A005382) then n = q*(2q - 1) is a pseudoprime to base 5 (n is in the sequence) if and only if q is of the form 10k + 1. 1891, 88831, 146611, 218791, 721801, ... are such terms. This sequence is a subsequence of A122782. - Farideh Firoozbakht, Sep 14 2006
Composite numbers n such that 5^(n-1) == 1 (mod n).

R. Crandall and C. Pomerance, "Prime Numbers - A Computational Perspective", Second Edition, Springer Verlag 2005, ISBN 0-387-25282-7 Page 132 (Theorem 3.4.2. and Algorithm 3.4.3)
J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 124, p. 43, Ellipses, Paris 2008.
R. K. Guy, Unsolved Problems in Number Theory, A12.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. J. Mathar, T. D. Noe and Hiroaki Yamanouchi, Table of n, a(n) for n = 1..92893 (terms a(1)-a(776) from R. J. Mathar, a(777)-a(1000) from T. D. Noe)
J. Bernheiden, Pseudoprimes (Text in German)
C. Pomerance & N. J. A. Sloane, Correspondence, 1991
F. Richman, Primality testing with Fermat's little theorem
Eric Weisstein's World of Mathematics, Fermat Pseudoprime
Index entries for sequences related to pseudoprimes

Pseudoprimes to other bases: A001567 (2), A005935 (3), A005937 (6), A005938 (7), A005939 (10).

Cf. A005382, A122782.

base = 5; t = {}; n = 1; While[Length[t] < 100, n++; If[! PrimeQ[n] && PowerMod[base, n-1, n] == 1, AppendTo[t, n]]]; t (* T. D. Noe, Feb 21 2012 *)
Select[Range[30000],CompositeQ[#]&&PowerMod[5,#-1,#]==1&] (* Harvey P. Dale, Jul 21 2023 *)

More terms from David W. Wilson, Aug 15 1996

A005938 Pseudoprimes to base 7.

Original entry on oeis.org

6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, 10225, 10585, 10621, 11041, 11521, 12025, 13665, 14089, 16725, 16806, 18721, 19345, 20197, 20417, 20425, 22945, 25829, 26419, 29234, 29341, 29857, 29891, 30025, 30811, 33227

Offset: 1

N. J. A. Sloane

nonn

According to Karsten Meyer, May 16 2006, 6 should be excluded, following the strict definition in Crandall and Pomerance.
Theorem: If both numbers q & 2q-1 are primes(q is in the sequence A005382) and n=q*(2q-1) then 7^(n-1)==1 (mod 7)(n is in the sequence) iff q=2 or mod(q,14) is in the set {1, 5, 13}. 6,703,18721,38503,88831,104653,146611,188191,... are such terms. This sequence is a subsequence of A122784. - Farideh Firoozbakht, Sep 14 2006
Composite numbers n such that 7^(n-1) == 1 (mod n).

R. Crandall and C. Pomerance, "Prime Numbers - A Computational Perspective", Second Edition, Springer Verlag 2005, ISBN 0-387-25282-7 Page 132 (Theorem 3.4.2. and Algorithm 3.4.3)
R. K. Guy, Unsolved Problems in Number Theory, A12.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. J. Mathar, T. D. Noe and Hiroaki Yamanouchi, Table of n, a(n) for n = 1..87448 (terms a(1)-a(697) from R. J. Mathar, a(698)-a(1000) from T. D. Noe)
J. Bernheiden, Pseudoprimes (Text in German)
C. Pomerance & N. J. A. Sloane, Correspondence, 1991
F. Richman, Primality testing with Fermat's little theorem
Index entries for sequences related to pseudoprimes

Pseudoprimes to other bases: A001567 (2), A005935 (3), A005936 (5), A005937 (6), A005939 (10).

Cf. A005382, A122784.

Select[Range[31000], ! PrimeQ[ # ] && PowerMod[7, (# - 1), # ] == 1 &] (* Farideh Firoozbakht, Sep 14 2006 *)

from sympy import isprime
def ok(n): return pow(7, n-1, n) == 1 and not isprime(n)
print(list(filter(ok, range(1, 34000)))) # Michael S. Branicky, Jun 25 2021

A090086 Smallest pseudoprime to base n, not necessarily exceeding n (cf. A007535).

Original entry on oeis.org

4, 341, 91, 15, 4, 35, 6, 9, 4, 9, 10, 65, 4, 15, 14, 15, 4, 25, 6, 21, 4, 21, 22, 25, 4, 9, 26, 9, 4, 49, 6, 25, 4, 15, 9, 35, 4, 39, 38, 39, 4, 205, 6, 9, 4, 9, 46, 49, 4, 21, 10, 51, 4, 55, 6, 15, 4, 57, 15, 341, 4, 9, 62, 9, 4, 65, 6, 25, 4, 69, 9, 85, 4, 15, 74, 15, 4, 77, 6, 9, 4, 9, 21, 85, 4, 15, 86, 87, 4, 91, 6

Offset: 1

Labos Elemer, Nov 25 2003

nonn

If n-1 is composite, then a(n) < n. - Thomas Ordowski, Aug 08 2018
Conjecture: a(n) = A007535(n) for finitely many n. For n > 2; if a(n) > n, then n-1 is prime (find all these primes). - Thomas Ordowski, Aug 09 2018
It seems that if a(2^p) = p^2, then 2^p-1 is prime. - Thomas Ordowski, Aug 10 2018
a(n) is the smallest composite k such that n^(k-1) == (1-k)^n (mod k). - Thomas Ordowski, Mar 19 2025

			From _Robert G. Wilson v_, Feb 26 2015: (Start)
a(n) = 4 for n = 1 + 4*k, k >= 0.
a(n) = 6 for n = 7 + 12*k, k >= 0.
a(n) = 9 for n = 8 + 18*k, 10 + 18*k, 35 + 36*k, k >= 0.
(End)
a(n) = 10 for n = 51 + 60*k, 11 + 180*k, 131 + 180*k, k >= 0.

Robert G. Wilson v, Table of n, a(n) for n = 1..10000 (first 1024 terms from Eric Chen)
Wikipedia, Pseudoprime
Index entries for sequences related to pseudoprimes

Cf. A007535, A250200, A090085, A090087, A000790, A239293, A293203.

Cf. A001567, A005935, A005936, A005937, A005938, A005939, A020136 - A020228.

f[n_] := Block[{k = 1}, While[ GCD[n, k] > 1 || PrimeQ[k] || PowerMod[n, k - 1, k] != 1, j = k++]; k]; Array[f, 91] (* Robert G. Wilson v, Feb 26 2015 *)

/* a(n) <= 2000 is sufficient up to n = 10000 */
a(n) = for(k=2,2000,if((n^(k-1))%k==1 && !isprime(k), return(k))) \\ Eric Chen, Feb 22 2015

a(n) = {forcomposite(k=2, , if (Mod(n,k)^(k-1) == 1, return (k)););} \\ Michel Marcus, Mar 02 2015

a(n) = LeastComposite{x; n^(x-1) mod x = 1}.

A130433 Even pseudoprimes to base 3.

Original entry on oeis.org

286, 24046, 232726, 1304446, 1707266, 2232026, 3197806, 3922126, 4446982, 5603326, 5886166, 10123366, 10169926, 12304774, 13658086, 45133726, 47766286, 52249654, 62656126, 75421126, 76254046, 91459126, 91612246, 96956926, 108571606, 139868326, 151513846

Offset: 1

Alexander Adamchuk, May 26 2007, Jun 17 2007

nonn

The first 27 terms (halved) are given in Table 1 by Paszkiewicz and Rotkiewicz. - R. J. Mathar, Aug 22 2012

Amiram Eldar, Table of n, a(n) for n = 1..215 (terms below 10^12, calculated from the b-file at A005935; terms 1..68 from Jeppe Stig Nielsen)
Adam Paszkiewicz and Andrzej Rotkiewicz, On a Problem of H. J. A. Duprac, Tatra Mt. Math. Publ. 32 (2005) 15-32, MR2206908.
Eric Weisstein's World of Mathematics, Fermat Pseudoprime.
Index entries for sequences related to pseudoprimes.

Even terms of A005935.
Terms of A122780 that are congruent to 2 or 4 modulo 6.
Cf. A006935, A090082, A090083, A090084, A090085.
Cf. A130434, A130435, A130436, A130437, A130438, A130439, A130440, A130441, A130442, A130443.

Do[ f=PowerMod[ 3, 2n-1, 2n ]; If[ f==1, Print[ 2n ] ], {n,2,7000000} ]

forstep(n=4,10^10,2,Mod(3,n)^(n-1)==1 && print1(n,", ")) \\ Jeppe Stig Nielsen, Apr 25 2018

More terms from Alexander Adamchuk, Jun 17 2007

a(25)-a(27) from Jeppe Stig Nielsen, Apr 25 2018

A122780 Nonprimes k such that 3^k == 3 (mod k).

Original entry on oeis.org

1, 6, 66, 91, 121, 286, 561, 671, 703, 726, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7107, 7381, 8205, 8401, 8646, 8911, 10585, 11011, 12403, 14383, 15203, 15457, 15841, 16471, 16531, 18721, 19345

Offset: 1

Farideh Firoozbakht, Sep 11 2006

Theorem: If q!=3 and both numbers q and (2q-1) are primes then k=q*(2q-1) is in the sequence. 6, 91, 703, 1891, 2701, 12403, 18721, 38503, 49141, ... is the related subsequence.

The terms > 1 and coprime to 3 of this sequence are the base-3 pseudoprimes, A005935. - M. F. Hasler, Jul 19 2012 [Corrected by Jianing Song, Feb 06 2019]

			66 is composite and 3^66 = 66*468229611858069884271524875811 + 3 so 66 is in the sequence.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A001567, A005935, A122014.

Cf. A122781, A122782, A122783, A122784, A122785, A122786.

isA122780 := proc(n)
    if isprime(n) then
        false;
    else
        modp( 3 &^ n,n) = modp(3,n) ;
    end if;
end proc:
for n from 1 do
    if isA122780(n) then
        print(n) ;
    end if;
end do: # R. J. Mathar, Jul 15 2012

Select[Range[30000], ! PrimeQ[ # ] && Mod[3^#, # ] == Mod[3, # ] &]
Join[{1},Select[Range[20000],!PrimeQ[#]&&PowerMod[3,#,#]==3&]] (* Harvey P. Dale, Apr 30 2023 *)

is_A122780(n)={n>0 & Mod(3, n)^n==3 & !ispseudoprime(n)} \\ M. F. Hasler, Jul 19 2012

A048950 Base-3 Euler-Jacobi pseudoprimes.

Original entry on oeis.org

121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, 16531, 18721, 19345, 23521, 24661, 28009, 29341, 31621, 41041, 44287, 46657, 47197, 49141, 50881, 52633, 55969, 63139, 63973, 74593, 75361, 79003, 82513

Offset: 1

Eric W. Weisstein

nonn

Odd composite k with gcd(k,3) = 1 and 3^((k-1)/2) == (3,k) (mod k) where (.,.) is the Jacobi symbol. - R. J. Mathar, Jul 15 2012

The base 5 Euler-Jacobi pseudoprimes are 781, 1541, 1729, 5461, 5611, 6601, 7449, ... - R. J. Mathar, Jul 15 2012 [Typo fixed; this is A375914. - Jianing Song, Sep 02 2024]

Amiram Eldar, Table of n, a(n) for n = 1..10000
A. Rotkiewicz, On Euler Lehmer pseudoprimes and strong Lehmer pseudoprimes with Parameters L, Q in arithmetic progressions, Math. Comp 39 (159) (1982) 239-247.
Eric Weisstein's World of Mathematics, Euler-Jacobi Pseudoprime.
Index entries for sequences related to pseudoprimes

Cf. A005935.
                                   |        b=2        |   b=3    |   b=5   |
-----------------------------------+-------------------+----------+---------+
  (b/k)=1, b^((k-1)/2)==1 (mod k)  |      A006971      | A375917  | A375915 |
-----------------------------------+-------------------+----------+---------+
 (b/k)=-1, b^((k-1)/2)==-1 (mod k) | A244628 U A244626 | A375918  | A375916 |
-----------------------------------+-------------------+----------+---------+
 b^((k-1)/2)==-(b/k) (mod k), also |      A306310      | A375490  | A375816 |
 (b/k)=-1, b^((k-1)/2)==1 (mod k)  |                   |          |         |
-----------------------------------+-------------------+----------+---------+
     Euler-Jacobi pseudoprimes     |      A047713      | this seq | A375914 |
       (union of first two)        |                   |          |         |
-----------------------------------+-------------------+----------+---------+
        Euler pseudoprimes         |      A006970      | A262051  | A262052 |
       (union of all three)        |                   |          |         |

Select[Range[1, 10^5, 2], GCD[#, 3] == 1 && CompositeQ[#] && PowerMod[3, (# - 1)/2, #] == Mod[JacobiSymbol[3, #], #] &] (* Amiram Eldar, Jun 28 2019 *)

is(n) = n%2==1 && gcd(n,3)==1 && Mod(3, n)^((n-1)/2)==kronecker(3,n)
forcomposite(c=1, 83000, if(is(c), print1(c, ", "))) \\ Felix Fröhlich, Jul 15 2019

cp's OEIS Frontend

A052155 Pseudoprimes to both base 2 and base 3, i.e., intersection of A001567 and A005935.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A001567 Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A002997 Carmichael numbers: composite numbers k such that a^(k-1) == 1 (mod k) for every a coprime to k.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A020229 Strong pseudoprimes to base 3.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A005936 Pseudoprimes to base 5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A005938 Pseudoprimes to base 7.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

A090086 Smallest pseudoprime to base n, not necessarily exceeding n (cf. A007535).

Views

Author

Keywords