The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001567 Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers.
(Formerly M5441 N2365)

%I M5441 N2365

%S 341,561,645,1105,1387,1729,1905,2047,2465,2701,2821,3277,4033,4369,

%T 4371,4681,5461,6601,7957,8321,8481,8911,10261,10585,11305,12801,

%U 13741,13747,13981,14491,15709,15841,16705,18705,18721,19951,23001,23377,25761,29341

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

%C 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.

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C 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

%C The only twin pseudoprimes up to 10^13 are 4369, 4371. - _Thomas Ordowski_, Feb 12 2016

%C 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

%C 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

%C If 2^n-1 is a pseudoprime, then n is a prime or a pseudoprime (odd or even). - _Thomas Ordowski_, Sep 05 2016

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

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

%D George P. Loweke, The Lore of Prime Numbers. New York: Vantage Press (1982): 22.

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

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

%H N. J. A. Sloane, <a href="/A001567/b001567.txt">Table of n, a(n) for n = 1..101629</a> [The pseudoprimes up to 10^12, from Richard Pinch's web site - see links below]

%H Jonathan Bayless and Paul Kinlaw, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL20/Bayless/bayless3.html">Explicit Bounds for the Sum of Reciprocals of Pseudoprimes and Carmichael Numbers</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.4.

%H Jens Bernheiden, <a href="https://web.archive.org/web/20160508153313/http://www.mathe-schule.de/download/pdf/Primzahl/PSP.pdf">Pseudoprimes</a> (Text in German).

%H John Brillhart, N. J. A. Sloane, J. D. Swift, <a href="/A001567/a001567_2.pdf">Correspondence, 1972</a>

%H Jan Feitsma, <a href="http://www.janfeitsma.nl/math/psp2/index">The pseudoprimes below 2^64</a>

%H William Galway, <a href="http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html">Tables of pseudoprimes and related data</a> [Includes a file with pseudoprimes up to 2^64.]

%H Richard K. Guy, <a href="/A005165/a005165.pdf">The strong law of small numbers</a>. Amer. Math. Monthly, Vol. 95, No. 8 (1988), pp. 697-712. [Annotated scanned copy]

%H D. H. Lehmer, <a href="http://www.jstor.org/stable/2004371">Errata for Poulet's table</a>, Math. Comp., Vol. 25, No. 116 (1971), pp. 944-945.

%H D. H. Lehmer, <a href="/A001567/a001567_1.pdf">Errata for Poulet's table</a> [annotated scanned copy]

%H Gérard P. Michon, <a href="http://www.numericana.com/answer/pseudo.htm">Pseudoprimes</a>

%H J. C. P. Miller, <a href="http://dx.doi.org/10.1090/S0025-5718-1975-0366796-6">On factorization, with a suggested new approach</a>, Math. Comp., Vol. 29, No. 129 (1975), pp. 155-172. - _Felix Fröhlich_, Aug 18 2014

%H Robert Morris, <a href="/A001567/a001567.pdf">Some observations on the converse of Fermat's theorem</a>, unpublished memorandum, Oct 03 1973

%H Richard Pinch, <a href="http://www.chalcedon.demon.co.uk/rgep/carpsp.html">Pseudoprimes</a>

%H Carl Pomerance & N. J. A. Sloane, <a href="/A001567/a001567_4.pdf">Correspondence, 1991</a>

%H Paul Poulet, <a href="/A001567/a001567_3.pdf">Tables des nombres composés vérifiant le théorème de Fermat pour le module 2 jusqu'à 100.000.000</a>, Sphinx (Brussels), Vol. 8 (1938), pp. 42-45. [annotated scanned copy]

%H Fred Richman, <a href="http://math.fau.edu/Richman/carm.htm">Primality testing with Fermat's little theorem</a>.

%H Andrzej Rotkiewicz, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002075660">Sur les nombres pseudopremiers de la forme MpMq</a>, Elemente der Mathematik, Vol. 20 (1965), pp. 108-109.

%H Waclaw Sierpiński, <a href="http://matwbn.icm.edu.pl/ksiazki/cm/cm1/cm113.pdf">Remarque sur une hypothèse des Chinois concernant les nombres (2^n-2)/n</a>, Colloquium Mathematicum, Vol. 1 (1947), p. 9.

%H Waclaw Sierpiński, <a href="http://matwbn.icm.edu.pl/kstresc.php?tom=42&amp;wyd=10">Elementary Theory of Numbers</a>, Państ. Wydaw. Nauk., p. 215, Warszawa 1964.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChineseHypothesis.html">Chinese Hypothesis</a>, <a href="http://mathworld.wolfram.com/FermatPseudoprime.html">Fermat Pseudoprime</a>, <a href="http://mathworld.wolfram.com/PouletNumber.html">Poulet Number</a>, and <a href="http://mathworld.wolfram.com/Pseudoprime.html">Pseudoprime</a>.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Chinese_hypothesis">Chinese hypothesis</a> and <a href="http://en.wikipedia.org/wiki/Pseudoprime">Pseudoprime</a>.

%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>

%F Sum_{n>=1} 1/a(n) is in the interval (0.015260, 33) (Bayless and Kinlaw, 2017). - _Amiram Eldar_, Oct 15 2020

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

%t Select[Range[3,30000,2], ! PrimeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &] (* _Farideh Firoozbakht_, Sep 15 2006 *)

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

%o (PARI) 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

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

%Y Cf. A002997, A005382, A020137, A052155, A083737, A084653, A153508.

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

%Y Cf. A005935, A005936, A005937, A005938, A005939, A020136-A020228 (pseudoprimes to bases 3 through 100).

%K nonn,nice

%O 1,1

%A _N. J. A. Sloane_

%E More terms from _David W. Wilson_, Aug 15 1996

%E Replacement of broken geocities link by _Jason G. Wurtzel_, Sep 05 2010

%E "Poulet numbers" added to name by _Joerg Arndt_, Aug 18 2014

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 12 22:36 EDT 2021. Contains 342933 sequences. (Running on oeis4.)