1,1

An odd composite number n is a Fermat pseudoprime to base b iff 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) iff q is of the form 12k+1. 2701,18721,49141,104653,226801,665281,721801,... is the related subsequence. This subsequence is also a subsequence of the sequences A005937 and A020137. - Farideh Firoozbakht (mymontain(AT)yahoo.com), Sep 15 2006

Also composite numbers n such that n divides 2^n - 2. 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 (alex(AT)kolmogorov.com), Nov 06 2006

An odd composite number 2n+1 is in the sequence iff multiplicative order of 2 (mod 2n+1) divides 2n. - Ray Chandler (rayjchandler(AT)sbcglobal.net), May 26 2008

Contribution from Artur Jasinski (grafix(AT)csl.pl), Dec 28 2008: (Start)

The Carmichael numbers A002997 are subset of this sequence.

For the Sarrus numbers which are not Carmichael numbers see A153508. (End)

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

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

R. K. Guy, Unsolved Problems Theory of Numbers, A12.

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

D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, p. 48.

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, Elementary Theory of Numbers. Pa\'{n}st. Wydaw. Nauk., Warsaw, 1964, p. 215.

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]

J. Bernheiden, Pseudoprimes (Text in German)

F. Di Noto and A. R. Tulumello, Nuovo test di primalita.

G. P. Michon, Pseudoprimes

Richard Pinch, Pseudoprimes

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

W. Sierpi\'{n}ski, Elementary Theory of Numbers, Warszawa 1964.

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, Fermat Pseudoprime

Wikipedia, Pseudoprime

Index entries for sequences related to pseudoprimes

Theorem: If both numbers q and 2q-1 are primes and n=q*(2q-1) then n is a pseudoprime in base 2 (n is in the sequence A001567 ) iff q == 1 (mod 4). - Farideh Firoozbakht (mymontain(AT)yahoo.com), Sep 11 2006

Equivalently: Theorem: If both numbers q and 2q-1 are primes and n=q*(2q-1) then n is a pseudoprime to base 2 (n is in the sequence A001567 ) iff q == 1 (mod 12). - Farideh Firoozbakht (mymontain(AT)yahoo.com), Sep 15 2006

Select[Range[4100], ! PrimeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &] - Farideh Firoozbakht (mymontain(AT)yahoo.com), Sep 15 2006

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

Cf. A002997, A052155, A083737, A084653, A005382, A005937, A020137.

Cf. A001220 = Wieferich primes p: p^2 divides 2^(p-1) - 1.

A153508 [From Artur Jasinski (grafix(AT)csl.pl), Dec 28 2008]

Sequence in context: A020188 A025353 A025345 this_sequence A006970 A007324 A007011

Adjacent sequences: A001564 A001565 A001566 this_sequence A001568 A001569 A001570

nonn,nice

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

More terms from David W. Wilson Aug 15 1996.