A001567 -id:A001567 - cp's OEIS frontend

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

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

A001220 Wieferich primes: primes p such that p^2 divides 2^(p-1) - 1.

Original entry on oeis.org

1093, 3511

Offset: 1

N. J. A. Sloane

Sequence is believed to be infinite.
Joseph Silverman showed that the abc-conjecture implies that there are infinitely many primes which are not in the sequence. - Benoit Cloitre, Jan 09 2003
Graves and Murty (2013) improved Silverman's result by showing that for any fixed k > 1, the abc-conjecture implies that there are infinitely many primes == 1 (mod k) which are not in the sequence. - Jonathan Sondow, Jan 21 2013
The squares of these numbers are Fermat pseudoprimes to base 2 (A001567) and Catalan pseudoprimes (A163209). - T. D. Noe, May 22 2003
Primes p that divide the numerator of the harmonic number H((p-1)/2); that is, p divides A001008((p-1)/2). - T. D. Noe, Mar 31 2004
In a 1977 paper, Wells Johnson, citing a suggestion from Lawrence Washington, pointed out the repetitions in the binary representations of the numbers which are one less than the two known Wieferich primes; i.e., 1092 = 10001000100 (base 2); 3510 = 110110110110 (base 2). It is perhaps worth remarking that 1092 = 444 (base 16) and 3510 = 6666 (base 8), so that these numbers are small multiples of repunits in the respective bases. Whether this is mathematically significant does not appear to be known. - John Blythe Dobson, Sep 29 2007
A002326((a(n)^2 - 1)/2) = A002326((a(n)-1)/2). - Vladimir Shevelev, Jul 09 2008, Aug 24 2008
It is believed that p^2 does not divide 3^(p-1) - 1 if p = a(n). This is true for n = 1 and 2. See A178815, A178844, A178900, and Ostafe-Shparlinski (2010) Section 1.1. - Jonathan Sondow, Jun 29 2010
These primes also divide the numerator of the harmonic number H(floor((p-1)/4)). - H. Eskandari (hamid.r.eskandari(AT)gmail.com), Sep 28 2010
1093 and 3511 are prime numbers p satisfying congruence 429327^(p-1) == 1 (mod p^2). Why? - Arkadiusz Wesolowski, Apr 07 2011. Such bases are listed in A247208. - Max Alekseyev, Nov 25 2014. See A269798 for all such bases, prime and composite, that are not powers of 2. - Felix Fröhlich, Apr 07 2018
A196202(A049084(a(1))) = A196202(A049084(a(2))) = 1. - Reinhard Zumkeller, Sep 29 2011
If q is prime and q^2 divides a prime-exponent Mersenne number, then q must be a Wieferich prime. Neither of the two known Wieferich primes divide Mersenne numbers. See Will Edgington's Mersenne page in the links below. - Daran Gill, Apr 04 2013
There are no other terms below 4.97*10^17 as established by PrimeGrid (see link below). - Max Alekseyev, Nov 20 2015. The search was done via PrimeGrid's PRPNet and the results were not double-checked. Because of the unreliability of the testing, the search was suspended in May 2017 (cf. Goetz, 2017). - Felix Fröhlich, Apr 01 2018. On Nov 28 2020, PrimeGrid has resumed the search (cf. Reggie, 2020). - Felix Fröhlich, Nov 29 2020. As of Dec 29 2022, PrimeGrid has completed the search to 2^64 (about 1.8 * 10^19) and has no plans to continue further. - Charles R Greathouse IV, Sep 24 2024
Are there other primes q >= p such that q^2 divides 2^(p-1)-1, where p is a prime? - Thomas Ordowski, Nov 22 2014. Any such q must be a Wieferich prime. - Max Alekseyev, Nov 25 2014
Primes p such that p^2 divides 2^r - 1 for some r, 0 < r < p. - Thomas Ordowski, Nov 28 2014, corrected by Max Alekseyev, Nov 28 2014
For some reason, both p=a(1) and p=a(2) also have more bases b with 1 < b < p that make b^(p-1) == 1 (mod p^2) than any smaller prime p; in other words, a(1) and a(2) belong to A248865. - Jeppe Stig Nielsen, Jul 28 2015
Let r_1, r_2, r_3, ..., r_i be the set of roots of the polynomial X^((p-1)/2) - (p-3)! * X^((p-3)/2) - (p-5)! * X^((p-5)/2) - ... - 1. Then p is a Wieferich prime iff p divides sum{k=1, p}(r_k^((p-1)/2)) (see Example 2 in Jakubec, 1994). - Felix Fröhlich, May 27 2016
Arthur Wieferich showed that if p is not a term of this sequence, then the First Case of Fermat's Last Theorem has no solution in x, y and z for prime exponent p (cf. Wieferich, 1909). - Felix Fröhlich, May 27 2016
Let U_n(P, Q) be a Lucas sequence of the first kind, let e be the Legendre symbol (D/p) and let p be a prime not dividing 2QD, where D = P^2 - 4*Q. Then a prime p such that U_(p-e) == 0 (mod p^2) is called a "Lucas-Wieferich prime associated to the pair (P, Q)". Wieferich primes are those Lucas-Wieferich primes that are associated to the pair (3, 2) (cf. McIntosh, Roettger, 2007, p. 2088). - Felix Fröhlich, May 27 2016
Any repeated prime factor of a term of A000215 is a term of this sequence. Thus, if there exist infinitely many Fermat numbers that are not squarefree, then this sequence is infinite, since no two Fermat numbers share a common factor. - Felix Fröhlich, May 27 2016
If the Diophantine equation p^x - 2^y = d has more than one solution in positive integers (x, y), with (p, d) not being one of the pairs (3, 1), (3, -5), (3, -13) or (5, -3), then p is a term of this sequence (cf. Scott, Styer, 2004, Corollary to Theorem 2). - Felix Fröhlich, Jun 18 2016
Odd primes p such that Chi_(D_0)(p) != 1 and Lambda_p(Q(sqrt(D_0))) != 1, where D_0 < 0 is the fundamental discriminant of the imaginary quadratic field Q(sqrt(1-p^2)) and Chi and Lambda are Iwasawa invariants (cf. Byeon, 2006, Proposition 1 (i)). - Felix Fröhlich, Jun 25 2016
If q is an odd prime, k, p are primes with p = 2*k+1, k == 3 (mod 4), p == -1 (mod q) and p =/= -1 (mod q^3) (Jakubec, 1998, Corollary 2 gives p == -5 (mod q) and p =/= -5 (mod q^3)) with the multiplicative order of q modulo k = (k-1)/2 and q dividing the class number of the real cyclotomic field Q(Zeta_p + (Zeta_p)^(-1)), then q is a term of this sequence (cf. Jakubec, 1995, Theorem 1). - Felix Fröhlich, Jun 25 2016
From Felix Fröhlich, Aug 06 2016: (Start)
Primes p such that p-1 is in A240719.
Prime terms of A077816 (cf. Agoh, Dilcher, Skula, 1997, Corollary 5.9).
p = prime(n) is in the sequence iff T(2, n) > 1, where T = A258045.
p = prime(n) is in the sequence iff an integer k exists such that T(n, k) = 2, where T = A258787. (End)
Conjecture: an integer n > 1 such that n^2 divides 2^(n-1)-1 must be a Wieferich prime. - Thomas Ordowski, Dec 21 2016
The above conjecture is equivalent to the statement that no "Wieferich pseudoprimes" (WPSPs) exist. While base-b WPSPs are known to exist for several bases b > 1 other than 2 (see for example A244752), no base-2 WPSPs are known. Since two necessary conditions for a composite to be a base-2 WPSP are that, both, it is a base-2 Fermat pseudoprime (A001567) and all its prime factors are Wieferich primes (cf. A270833), as shown in the comments in A240719, it seems that the first base-2 WPSP, if it exists, is probably very large. This appears to be supported by the guess that the properties of a composite to be a term of A001567 and of A270833 are "independent" of each other and by the observation that the scatterplot of A256517 seems to become "less dense" at the x-axis parallel line y = 2 for increasing n. It has been suggested in the literature that there could be asymptotically about log(log(x)) Wieferich primes below some number x, which is a function that grows to infinity, but does so very slowly. Considering the above constraints, the number of WPSPs may grow even more slowly, suggesting any such number, should it exist, probably lies far beyond any bound a brute-force search could reach in the forseeable future. Therefore I guess that the conjecture may be false, but a disproof or the discovery of a counterexample are probably extraordinarily difficult problems. - Felix Fröhlich, Jan 18 2019
Named after the German mathematician Arthur Josef Alwin Wieferich (1884-1954). a(1) = 1093 was found by Waldemar Meissner in 1913. a(2) = 3511 was found by N. G. W. H. Beeger in 1922. - Amiram Eldar, Jun 05 2021
From Jianing Song, Jun 21 2025: (Start)
The ring of integers of Q(2^(1/k)) is Z[2^(1/k)] if and only if k does not have a prime factor in this sequence (k is in A342390). See Theorem 5.3 of the paper of Keith Conrad. For example, we have:
  (1 + 2^(364/1093) + 2^(2*364/1093) + ... + 2^(1092*364/1093))/1093 is an algebraic integer, but it is not in Z[2^(1/1093)];
  (1 + 2^(1755/3511) + 2^(2*1755/3511) + ... + 2^(3510*1755/3511))/3511 is an algebraic integer, but it is not in Z[2^(1/3511)]. (End)

Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 28.
Richard K. Guy, Unsolved Problems in Number Theory, A3.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 91.
Yves Hellegouarch, "Invitation aux mathématiques de Fermat Wiles", Dunod, 2eme Edition, pp. 340-341.
Pace Nielsen, Wieferich primes, heuristics, computations, Abstracts Amer. Math. Soc., 33 (#1, 20912), #1077-11-48.
Paulo Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 263.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 230-234.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, NY, 1986, p. 163.

Takashi Agoh, Karl Dilcher and Ladislav Skula, Fermat Quotients for Composite Moduli, Journal of Number Theory 66(1), 1997, 29-50.
Joerg Arndt, Matters Computational (The Fxtbook), p. 780.
Alex Samuel Bamunoba, A note on Carlitz Wieferich primes, Journal of Number Theory, Vol. 174 (2017), pp. 343-357;
N. G. W. H. Beeger, On a New Case of the Congruence 2^(p-1) == 1 (mod p^2), Messenger of Mathematics, Vol 51 (1922), pp. 149-150.
Dongho Byeon, Class numbers, Iwasawa invariants and modular forms, Trends in Mathematics, Vol. 9, No. 1, (2006), pp. 25-29.
Chris K. Caldwell, The Prime Glossary, Wieferich prime.
Chris K. Caldwell, Prime-square Mersenne divisors are Wieferich.
Denis Xavier Charles, On Wieferich Primes.
Keith Conrad, The ring of integers in a radical extension.
Richard Crandall, Karl Dilcher and Carl Pomerance, A search for Wieferich and Wilson primes, Mathematics of Computation, Vol. 66, No. 217 (1997), pp. 433-449; alternative link.
Joe K. Crump, Joe's Number Theory Web, Weiferich Primes. (sic)
John Blythe Dobson, A note on the two known Wieferich Primes, 2007-2015.
John Blythe Dobson A Characterization of Wilson-Lerch Primes, Integers, Vol. 16 (2016), A51.
John Blythe Dobson, On the special harmonic numbers H_floor(p/9) and H_floor(p/18) modulo p, arXiv:2302.02027 [math.NT], 2023.
F. G. Dorais, WPSE - A Wieferich Prime Search Engine (A program to search Wieferich primes written by F. G. Dorais.) - _Felix Fröhlich_, Jul 13 2014
François G. Dorais and Dominic W. Klyve, A Wieferich Prime Search up to 6.7*10^15, Journal of Integer Sequences, Vol. 14 (2011), Article 11.9.2.
Bruno Dular, Cycles of Sums of Integers, arXiv:1905.01765 [math.NT], 2019.
Will Edgington, Mersenne Page [from Internet Archive Wayback Machine].
M. Goetz, WSS and WFS are suspended, PrimeGrid forum, Message 107809, May 11, 2017.
Andrew Granville and K. Soundararajan, A binary additive problem of Erdős and the order of 2 mod p^2, Raman. J., Vol. 2 (1998) pp. 283-298
Hester Graves and M. Ram Murty, The abc conjecture and non-Wieferich primes in arithmetic progressions, Journal of Number Theory, Vol. 133 (2013), pp. 1809-1813.
René Gy, Extended Congruences for Harmonic Numbers, arXiv:1902.05258 [math.NT], 2019.
Lorenz Halbeisen and Norbert Hungerbuehler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5 (1999) 138-150. (ps, pdf)
Stanislav Jakubec, Connection between the Wieferich congruence and divisibility of h+, Acta Arithmetica, Vol. 71, No. 1 (1995), pp. 55-64.
Stanislav Jakubec, On divisibility of the class number h+ of the real cyclotomic fields of prime degree l, Mathematics of Computation, Vol. 67, No. 221 (1998), pp. 369-398.
Stanislav Jakubec, The Congruence for Gauss Period, Journal of Number Theory, Vol. 48, No. 1 (1994), pp. 36-45.
Wells Johnson, On the nonvanishing of Fermat quotients (mod p), Journal f. die reine und angewandte Mathematik, Vol. 292, (1977), pp. 196-200.
Jiří Klaška, A Simple Proof of Skula's Theorem on Prime Power Divisors of Mersenne Numbers, J. Int. Seq., Vol. 25 (2022), Article 22.4.3.
Jiří Klaška, Jakóbczyk's Hypothesis on Mersenne Numbers and Generalizations of Skula's Theorem, J. Int. Seq., Vol. 26 (2023), Article 23.3.8.
Joshua Knauer and Jörg Richstein, The continuing search for Wieferich primes, Math. Comp., Vol. 74, No. 251 (2005), pp. 1559-1563.
D. H. Lehmer, On Fermat's quotient, base two, Math. Comp., Vol. 36, No. 153 (1981), pp. 289-290.
Richard J. McIntosh and Eric L. Roettger, A search for Fibonacci-Wieferich and Wolstenholme primes, Math. Comp., Vol 76, No. 260 (2007), pp. 2087-2094.
C. McLeman, PlanetMath.org, Wieferich prime.
Waldemar Meissner, Über die Teilbarkeit von 2^p-2 durch das Quadrat der Primzahl p = 1093, Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften Berlin, Vol. 35 (1913), pp. 663-667. [Annotated scanned copy]
Sihem Mesnager and Jean-Pierre Flori, A note on hyper-bent functions via Dillon-like exponents, IACR, Report 2012/033, 2012.
Mishima Miwako and Koji Momihara, A new series of optimal tight conflict-avoiding codes of weight 3, Discrete Mathematics, Vol. 340, No. 4 (2017), pp. 617-629. See page 618.
Alina Ostafe and Igor E. Shparlinski, Pseudorandomness and Dynamics of Fermat Quotients, arXiv:1001.1504 [math.NT], 2010.
Christian Perfect, Integer sequence reviews on Numberphile (or vice versa), 2013.
Reggie, Welcome to the Wieferich and Wall-Sun-Sun Prime Search, PrimeGrid forum, 2020.
Reese Scott and Robert Styer, On p^x - q^y = c and related three term exponential Diophantine equations with prime bases, Journal of Number Theory, Vol. 105, No. 2 (2004), pp. 212-234.
Vladimir Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich Primes, arXiv:0806.3412 [math.NT], 2008.
Joseph Silverman, Wieferich's Criterion and the abc Conjecture, J. Number Th. 30 (1988) 226-237.
Jonathan Sondow, Lerch quotients, Lerch primes, Fermat-Wilson quotients, and the Wieferich-non-Wilson primes 2, 3, 14771, arXiv:1110.3113 [math.NT], 2012.
Jonathan Sondow, Lerch Quotients, Lerch Primes, Fermat-Wilson Quotients, and the Wieferich-non-Wilson Primes 2, 3, 14771, Combinatorial and Additive Number Theory, CANT 2011 and 2012, Springer Proc. in Math. & Stat., Vol. 101 (2014), pp. 243-255.
Michel Waldschmidt, Lecture on the abc conjecture and some of its consequences, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.
Michel Waldschmidt, Lecture on the abc conjecture and some of its consequences, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.
Eric Weisstein's World of Mathematics, Wieferich Prime.
Eric Weisstein's World of Mathematics, abc Conjecture.
Eric Weisstein's World of Mathematics, Integer Sequence Primes.
A. Wieferich, Zum letzten Fermat'schen Theorem, Journal für die reine und angewandte Mathematik, Vol. 136 (1909), pp. 293-302.
Wikipedia, Wieferich prime.
Paul Zimmermann, Records for Prime Numbers.

Cf. similar primes related to the first case of Fermat's last theorem: A007540, A088164.
Sequences "primes p such that p^2 divides X^(p-1)-1": A014127 (X=3), A123692 (X=5), A212583 (X=6), A123693 (X=7), A045616 (X=10), A111027 (X=12), A128667 (X=13), A234810 (X=14), A242741 (X=15), A128668 (X=17), A244260 (X=18), A090968 (X=19), A242982 (X=20), A298951 (X=22), A128669 (X=23), A306255 (X=26), A306256 (X=30).
Cf. A001567, A002323, A077816, A001008, A039951, A049094, A126196, A126197, A178815, A178844, A178871, A178900, A246503, A247208, A269798.

Filtered([1..50000],p->IsPrime(p) and (2^(p-1)-1) mod p^2 =0); # Muniru A Asiru, Apr 03 2018

import Data.List (elemIndices)
a001220 n = a001220_list !! (n-1)
a001220_list = map (a000040 . (+ 1)) $ elemIndices 1 a196202_list
-- Reinhard Zumkeller, Sep 29 2011

[p : p in PrimesUpTo(310000) | IsZero((2^(p-1) - 1) mod (p^2))]; // Vincenzo Librandi, Jan 19 2019

wieferich := proc (n) local nsq, remain, bin, char: if (not isprime(n)) then RETURN("not prime") fi: nsq := n^2: remain := 2: bin := convert(convert(n-1, binary),string): remain := (remain * 2) mod nsq: bin := substring(bin,2..length(bin)): while (length(bin) > 1) do: char := substring(bin,1..1): if char = "1" then remain := (remain * 2) mod nsq fi: remain := (remain^2) mod nsq: bin := substring(bin,2..length(bin)): od: if (bin = "1") then remain := (remain * 2) mod nsq fi: if remain = 1 then RETURN ("Wieferich prime") fi: RETURN ("non-Wieferich prime"): end: # Ulrich Schimke (ulrschimke(AT)aol.com), Nov 01 2001

Select[Prime[Range[50000]],Divisible[2^(#-1)-1,#^2]&]  (* Harvey P. Dale, Apr 23 2011 *)
Select[Prime[Range[50000]],PowerMod[2,#-1,#^2]==1&] (* Harvey P. Dale, May 25 2016 *)

N=10^4; default(primelimit,N);
forprime(n=2,N,if(Mod(2,n^2)^(n-1)==1,print1(n,", ")));
\\ Joerg Arndt, May 01 2013

from sympy import prime
from gmpy2 import powmod
A001220_list = [p for p in (prime(n) for n in range(1,10**7)) if powmod(2,p-1,p*p) == 1]
# Chai Wah Wu, Dec 03 2014

(A178815(A000720(p))^(p-1) - 1) mod p^2 = A178900(n), where p = a(n). - Jonathan Sondow, Jun 29 2010

Odd primes p such that A002326((p^2-1)/2) = A002326((p-1)/2). See A182297. - Thomas Ordowski, Feb 04 2014

A001262 Strong pseudoprimes to base 2.

Original entry on oeis.org

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, 104653, 130561, 196093, 220729, 233017, 252601, 253241, 256999, 271951, 280601, 314821, 357761, 390937, 458989, 476971, 486737

Offset: 1

N. J. A. Sloane

The number 2^k-1 is in the sequence iff k is in A054723 or in A001567. - Thomas Ordowski, Sep 02 2016

The number (2^k+1)/3 is in the sequence iff k is in A127956. - Davide Rotondo, Aug 13 2021

			From _Michael B. Porter_, Sep 04 2016: (Start)
For k = 577, k-1 = 576 = 9*2^6. Since 2^(9*2^3) = 2^72 == -1 (mod 577), 577 passes the primality test, but since it is actually prime, it is not in the sequence.
For k = 3277, k-1 = 3276 = 819*2^2, and 2^(819*2) == -1 (mod 3277), so k passes the primality test, and k = 3277 = 29*113 is composite, so 3277 is in the sequence. (End)

R. K. Guy, Unsolved Problems Theory Numbers, A12.
P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 95.

T. D. Noe, Table of n, a(n) for n = 1..10000 (using data from A001567)
Joerg Arndt, Matters Computational (The Fxtbook), section 39.10, pp. 786-792.
Chris Caldwell, Strong probable prime.
Eric Weisstein's World of Mathematics, Strong Pseudoprime.
OEIS Wiki, Strong Pseudoprime.
Wikipedia, Strong pseudoprime.
Index entries for sequences related to pseudoprimes

Cf. A001567 (pseudoprimes to base 2), A020229 (strong pseudoprimes to base 3), A020231 (base 5), A020233 (base 7).

Cf. A072276 (SPP to base 2 and 3), A215568 (SPP to base 2 and 5), A056915 (SPP to base 2,3 and 5), A074773 (SPP to base 2,3,5 and 7).

A007814 := proc(n) padic[ordp](n,2) ; end proc:
isStrongPsp := proc(n,b) local d,s,r; if type(n,'even') or n<=1 then return false; elif isprime(n) then return false; else s := A007814(n-1) ; d := (n-1)/2^s ; if modp(b &^ d,n) = 1 then return true; else for r from 0 to s-1 do if modp(b &^ d,n) = n-1 then return true; end if; d := 2*d ; end do: return false; end if; end if; end proc:
isA001262 := proc(n) isStrongPsp(n,2) ; end proc:
for n from 1 by 2 do if isA001262(n) then print(n); end if; end do:
# R. J. Mathar, Apr 05 2011

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, n] == n-1, Return[True]]; d = 2*d, {s}]]); lst = {}; k = 3; While[k < 500000, If[sppQ[k, 2], Print[k]; AppendTo[lst, k]]; k += 2]; lst (* Jean-François Alcover, Oct 20 2011, after R. J. Mathar *)

isStrongPsp(n,b)={
        my(s,d,r,bm) ;
        if( (n% 2) ==0 || n <=1, return(0) ;) ;
        if(isprime(n), return(0) ;) ;
        s = valuation(n-1,2) ;
        d = (n-1)/2^s ;
        bm = Mod(b,n)^d ;
        if ( bm == Mod(1,n), return(1) ;) ;
        for(r=0,s-1,
                bm = Mod(b,n)^d ;
                if ( bm == Mod(-1,n),
                        return(1) ;
                ) ;
                d *= 2;
        ) ;
        return(0);
}
isA001262(n)={
        isStrongPsp(n,2)
}
{
for(n=1,10000000000,
    if(isA001262(n),
        print(n)
    ) ;
) ;
} \\ R. J. Mathar, Mar 07 2012

is_A001262(n,a=2)={ (bittest(n,0) && !isprime(n) && n>8) || return; my(s=valuation(n-1,2)); if(1==a=Mod(a,n)^(n>>s),return(1)); while(a!=-1 && s--, a=a^2); a==-1} \\ M. F. Hasler, Aug 16 2012

More terms from David W. Wilson, Aug 15 1996

This sequence contains the distances from pseudoprime numbers (A001567) to the next smaller number of the form 2^n. Conjecture: It seems that these distances do not take all possible values. So, if we know that a certain distance does not appear with pseudoprime numbers, we are able to calculate these numbers using Fermat's little theorem and we know for sure that they are primes.

a(n) <= A177415(n).
Each a(n) is an odd prime.
If k = A001567(n) is a Carmichael number, then a(n) = lpf(k).
Conjecture: if k = A001567(n) is semiprime, then a(n) < lpf(k).
The smallest numbers k = A001567(n) such that a(n) = prime(m) for m > 1 are 341, 1105, 1729, 75361, 29341, 162401, 334153, ... See A135720 > 561.
The smallest such semiprimes are 341, 2701, ?, 721801, ... Cf. A285549.

It is notable how many primes, semiprimes, pseudoprimes, squares and multiples of 3 are in this sequence.
Primes obtained and the corresponding Fermat pseudoprime in the brackets: 769 (341), 2113 (645), 4481 (1729), 6481 (2465), 6841 (3277), 12289 (4371), 26641 (10585), 28081 (13747), 32257 (13981), 32833 (15709), 37889 (15841), 63361 (18705), 40609 (19951), 72577 (23001).
Semiprimes obtained and the corresponding Fermat pseudoprime in the brackets: 6145 (1905), 4321 (2047), 7169 (2821), 9289 (4369), 17065 (8321), 21761 (8911), 36289 (12801), 34049 (13741), 43345 (16705).
Pseudoprimes obtained and the corresponding Fermat pseudoprime in the brackets: 1729 (561).
Squares obtained and the corresponding Fermat pseudoprime in the brackets: 3025 = 5^2*11^2 (1105), 5625 = 3^2*5^4 (2701), 16129 = 127^2 (6601), 38025 = 3^2*5^2*13^2 (18721).
Multiples of 3 obtained and the corresponding Fermat pseudoprime in the brackets: 2961 = 3^2*329 (1387), 5625 = 3^2*625 (2701), 8361 = 3^2*929 (4033), 9729 = 3^2*1081 (4681), 3*3755 (5461), 16281 = 3^5*67 (7957), 21249 = 3^3*787 (10261), 29745 = 3^2*3305 (14491), 38025 = 3^2*4225 (18721), 47433 = 3*15811 (23377), 71169 = 3*23723 (25761).
The only numbers from the sequence above that are not into at least one of these categories (and the corresponding Fermat pseudoprime in the brackets) are 24769 = 17*31*47 (8481) and 34561 = 17*19*107 (11305).
An interesting correspondence with the function from the sequence A216404: with that one we obtain the pseudoprime 561 from the pseudoprime 1729 (2*a(n) + 1); with this one we obtain 1729 from 561 (a(n)). Another type of correspondence with that function: 2*a(n) + 1 = 769 for a(n) = 384 for that function (corresponding to pseudoprime 1905) while a(n) = 769 for this function (corresponding to pseudoprime 341).

Is this sequence infinite? Is there a prime followed by three pseudoprimes before the next prime? I believe heuristics suggest "no" to both.
From Amiram Eldar, Mar 12 2023: (Start)
The primes preceding the terms of A335326.
There are no more terms below 2^64. (End)

2^n == 2 mod n if and only if n is a prime or a member of A001567 or of A006935. [Guy]. - N. J. A. Sloane, Mar 22 2012; corrected by Thomas Ordowski, Mar 26 2016
Known solutions to 2^n == 3 (mod n) are given in A050259.
This sequence is conjectured to include every integer k >= 0 except k = 1. A036236 includes a proof that k = 1 is not in this sequence, and n = A036236(k) solves a(n) = k for all other 0 <= k <= 1000. - David W. Wilson, Oct 11 2011
It could be argued that a(0) := 1 would make sense, e.g., thinking of "mod n" as "in Z/nZ", and/or because (anything)^0 = 1. See also A112987. - M. F. Hasler, Nov 09 2018

cp's OEIS Frontend

A295607 a(n) = A001567(n) - 2^floor(log_2(A001567(n))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A321790 a(n) is the smallest base a > 2 such that a^(k-1) != 1 (mod k), where k = A001567(n), the n-th Fermat pseudoprime to base 2.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A329240 Numbers that are both Fermat pseudoprimes to base 2 (A001567) and Bruckman-Lucas pseudoprimes (A005845).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

A379056 A378696 without A000961 and A001567.

Views

Author

Keywords

Crossrefs

A216646 a(n) = 1+2*(d1 + 1)*(d2 + 1)* … *(dk + 1), where d1, d2, ..., dk are the prime factors of the n-th Fermat pseudoprime to base 2 A001567(n).

Views

Author

Keywords

Comments

Links

Crossrefs

A359490 Primes p followed by two or more 2-pseudoprimes (A001567) before the next prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

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

A001220 Wieferich primes: primes p such that p^2 divides 2^(p-1) - 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A216646 a(n) = 1+2(d1 + 1)(d2 + 1)* … *(dk + 1), where d1, d2, ..., dk are the prime factors of the n-th Fermat pseudoprime to base 2 A001567(n).