A005939 -id:A005939 - cp's OEIS frontend

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

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

A005935 Pseudoprimes to base 3.

Original entry on oeis.org

91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, 10585, 11011, 12403, 14383, 15203, 15457, 15841, 16471, 16531, 18721, 19345, 23521, 24046, 24661, 24727, 28009, 29161

Offset: 1

N. J. A. Sloane

nonn

Theorem: If q>3 and both numbers q and (2q-1) are primes then n=q*(2q-1) is a pseudoprime to base 3 (i.e. n is in the sequence). So for n>2, A005382(n)*(2*A005382(n)-1) is in the sequence (see Comments lines for the sequence A122780). 91,703,1891,2701,12403,18721,38503,49141... are such terms. This sequence is a subsequence of A122780. - Farideh Firoozbakht, Sep 13 2006
Composite numbers n such that 3^(n-1) == 1 (mod n).
Theorem (R. Steuerwald, 1948): if n is a pseudoprime to base b and gcd(n,b-1)=1, then (b^n-1)/(b-1) is a pseudoprime to base b. In particular, if n is an odd pseudoprime to base 3, then (3^n-1)/2 is a pseudoprime to base 3. - Thomas Ordowski, Apr 06 2016
Steuerwald's theorem can be strengthened by weakening his assumption as follows: if n is a weak pseudoprime to base b and gcd(n,b-1)=1, then ... - Thomas Ordowski, Feb 23 2021

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 91, p. 33, 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..102839 (terms a(1)-a(798) from R. J. Mathar, a(799)-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
Carlos Rivera, Conjecture 105: conjecture about twin primes and pseudo twin primes to base 3, The Prime Puzzles & Problems Connection.
Rudolf Steuerwald, Über die Kongruenz a^(n-1) == 1 (mod n), Sitzungsber. math.-naturw. Kl. Bayer. Akad. Wiss. München, 1948, pp. 69-70.
Eric Weisstein's World of Mathematics, Fermat Pseudoprime
Index entries for sequences related to pseudoprimes

Pseudoprimes to other bases: A001567 (2), A005936 (5), A005937 (6), A005938 (7), A005939 (10).
Subsequence of A122780.
Cf. A005382.

base = 3; 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 *)

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

More terms from David W. Wilson, Aug 15 1996

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}.

A121014 Nonprime terms in A121912.

Original entry on oeis.org

1, 6, 9, 10, 15, 18, 30, 33, 45, 55, 90, 91, 99, 165, 246, 259, 370, 385, 451, 481, 495, 505, 561, 657, 703, 715, 909, 1035, 1045, 1105, 1233, 1626, 1729, 2035, 2409, 2465, 2821, 2981, 3333, 3367, 3585, 4005, 4141, 4187, 4521, 4545, 5005, 5461, 6533, 6541

Offset: 1

N. J. A. Sloane, Sep 06 2006

Theorem: If both numbers q and 2q-1 are primes (q is in the sequence A005382) and n=q*(2q-1) then 10^n == 10 (mod n) (n is in the sequence A121014) iff q<5 or mod(q, 20) is in the set {1, 7, 19}. 6,15,91,703,12403,38503,79003,188191,269011,... are such terms. A005939 is a subsequence of this sequence. - Farideh Firoozbakht, Sep 15 2006

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

Cf. A005382, A005939, A121014, A121912.

Select[Range[10^4], ! PrimeQ[ # ] && PowerMod[10, #, # ] == Mod[10, # ] &] (* Ray Chandler, Sep 06 2006 *)

for(n=1,7000,if(!isprime(n),k=10^n;if((k-10)%n==0,print1(n,",")))) \\ Klaus Brockhaus, Sep 06 2006

Theorem: If both numbers q and 2q-1 are primes and n=q*(2q-1) then 10^n == 10 (mod n) (n is in the sequence) iff q<5 or mod(q, 20) is in the set {1, 7, 19}. - Farideh Firoozbakht, Sep 11 2006

Extended by Ray Chandler and Klaus Brockhaus, Sep 06 2006

A020236 Strong pseudoprimes to base 10.

Original entry on oeis.org

9, 91, 1729, 4187, 6533, 8149, 8401, 10001, 11111, 19201, 21931, 50851, 79003, 83119, 94139, 100001, 102173, 118301, 118957, 134863, 139231, 148417, 158497, 166499, 188191, 196651, 201917, 216001, 226273, 231337, 237169, 251251, 287809, 302177

Offset: 1

David W. Wilson

nonn

			From _Alonso del Arte_, Aug 10 2018: (Start)
9 is a strong pseudoprime to base 10. It's not enough to check that 10^8 = 1 mod 9. Since 8 = 1 * 2^3, we also need to verify that 10 = 1 mod 9 and 10^2 = 1 mod 9 as well. Since these are both equal to 1, we see that 9 is indeed a strong pseudoprime to base 10.
91 is also a strong pseudoprime to base 10. Besides checking that 10^90 = 1 mod 91, since 90 = 45 * 2, we also check that 10^45 = -1 mod 91; the -1 is enough to satisfy the definition of a strong pseudoprime.
99 is a Fermat pseudoprime to base 10 (see A005939) but it is not a strong pseudoprime to base 10. Although 10^98 = 1 mod 99, since 98 = 49 * 2, we have to check 10^49 mod 99, and there we find not -1 nor 1 but 10. Therefore 99 is not in this sequence. (End)

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..203 from R. J. Mathar)
Index entries for sequences related to pseudoprimes

Cf. A005939, A001262, A020229, A020230, A020231, A020232, A020233, A020234, A020235.

strongPseudoprimeQ[b_, n_] := Module[{rems = Table[PowerMod[b, (n - 1)/2^expo, n], {expo, 0, IntegerExponent[n - 1,2]}]}, (rems[[-1]] == 1 || MemberQ[rems, n - 1]) && PowerMod[b, n - 1, n] == 1]; max = 5000; Select[Complement[Range[2, max], Prime[Range[PrimePi[max]]]], strongPseudoprimeQ[10, #] &] (* Alonso del Arte, Aug 10 2018 *)

A000864 Deceptive nonprimes: composite numbers k that divide the repunit R_{k-1}.

Original entry on oeis.org

91, 259, 451, 481, 703, 1729, 2821, 2981, 3367, 4141, 4187, 5461, 6533, 6541, 6601, 7471, 7777, 8149, 8401, 8911, 10001, 11111, 12403, 13981, 14701, 14911, 15211, 15841, 19201, 21931, 22321, 24013, 24661, 27613, 29341, 34133

Offset: 1

Tim Ray (c268scm(AT)semovm.semo.edu)

nonn

Francis and Ray call these numbers "deceptive primes".
Pseudoprimes to base 10, A005939, not divisible by 3. If k is in the sequence, then (10^k-1)/9 is in the sequence, by Steuerwald's theorem; see A005935. - Thomas Ordowski, Apr 10 2016
41041 is the first term that has four prime divisors. - Altug Alkan, Apr 10 2016

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
R. Francis and T. Ray, The deceptive primes to 2.10^7, Missouri J. Math. Sci. 12 (2000), no. 3, 145-158.

Cf. A002275, A005939.

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

p=5;forprime(q=7,1e5,forstep(n=p+2,q-2,2,if(n%5 && Mod(10,9*n)^(n-1)==1,print1(n", ")));p=q) \\ Charles R Greathouse IV, Jul 31 2011

A067934 Let rep(k) = (10^k - 1)/9 be the k-th repunit number = 11111..1111 with k 1 digits, then sequence gives values of k such that rep(k) == 1 (mod k).

Original entry on oeis.org

1, 2, 5, 7, 10, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 55, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 259

Offset: 1

Benoit Cloitre, Mar 05 2002

nonn

Due to Fermat's little theorem, all prime numbers except 3 are in the sequence. E.g., rep(17) = 1 + 17*653594771241830.
Numbers n such that 10^n == 10 (mod 9n). The number (10^n - 1)/9 is a term if and only if n is a term. - Thomas Ordowski, Apr 28 2018
Generally, the repunit theorem: Let integer b <> 1 and n be a positive integer. Define R_b(n) = (b^n-1)/(b-1) = N. Then R_b(N) == 1 (mod N) if and only if N == 1 (mod n). - Thomas Ordowski, Apr 28 2018
Proof: (b^N-1)/(b-1)-1 = (b^N-b)/(b-1) is divisible by N if and only if b^N-b is divisible by b^n-1. Since b^N-b == b^(N mod n)-b (mod b^n-1), we have that b^N-b is divisible by b^n-1 if and only if N == 1 (mod n). QED. - Max Alekseyev, Apr 28 2018
Terms which are not prime are 1 U A303608. - Robert G. Wilson v, Jun 13 2018
No multiples of 3 are in this sequence. - Eric Chen, Jun 13 2018
A005939 is subsequence. - Eric Chen, Jun 13 2018

			(10^11 - 1)/9 = 11111111111 == 1 (mod 11), so 11 is a term.
We also have the congruence 10^11 == 10 (mod 9*11).

Michael De Vlieger, Table of n, a(n) for n = 1..10000

Cf. A000864, A015919, A303608, A005939.

{1}~Join~Select[Range[260], Mod[#2, #1] == 1 & @@ {#, (10^# - 1)/9} &] (* Michael De Vlieger, May 06 2018 *)
fQ[n_] := PowerMod[10, n, 9 n] == 10; fQ[1] = True; Select[Range@260, fQ] (* Robert G. Wilson v, Jun 13 2018 *)

is(n)=n==1 || ((10^n-1)/9)%n==1 \\ Eric Chen, Jun 13 2018

cp's OEIS Frontend

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

A005935 Pseudoprimes to base 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A121014 Nonprime terms in A121912.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A020236 Strong pseudoprimes to base 10.

Views

Author

Keywords