This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001220 Wieferich primes: primes p such that p^2 divides 2^(p-1) - 1. 125


%S 1093,3511

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

%C Sequence is believed to be infinite.

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

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

%C The squares of these numbers are Fermat pseudoprimes to base 2 (A001567) and Catalan pseudoprimes (A163209). - _T. D. Noe_, May 22 2003

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

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

%C A002326((a(n)^2 - 1)/2) = A002326((a(n)-1)/2). - _Vladimir Shevelev_, Jul 09 2008, Aug 24 2008

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

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

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

%C A196202(A049084(a(1)) = A196202(A049084(a(2)) = 1. - _Reinhard Zumkeller_, Sep 29 2011

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

%C There are no other terms below 4.97*10^17 as established by PrimeGrid (see link below). - _Max Alekseyev_, Nov 20 2015

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

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

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

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

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

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

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

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

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

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

%C From _Felix Fröhlich_, Aug 06 2016: (Start)

%C Primes p such that p-1 is in A240719.

%C Prime terms of A077816 (cf. Agoh, Dilcher, Skula, 1997, Corollary 5.9).

%C p = prime(n) is in the sequence iff T(2, n) > 1, where T = A258045.

%C p = prime(n) is in the sequence iff an integer k exists such that T(n, k) = 2, where T = A258787. (End)

%C Conjecture: an integer n > 1 such that n^2 divides 2^(n-1)-1 must be a Wieferich prime. - _Thomas Ordowski_, Dec 21 2016

%D R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001; see p. 28.

%D R. K. Guy, Unsolved Problems in Number Theory, A3.

%D G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 91.

%D Y. Hellegouarch, "Invitation aux mathématiques de Fermat Wiles", Dunod, 2eme Edition, pp. 340-341.

%D Mishima, Miwako, and Koji Momihara. "A new series of optimal tight conflict-avoiding codes of weight 3." Discrete Mathematics 340.4 (2017): 617-629. See page 618.

%D Pace Nielsen, Wieferich primes, heuristics, computations, Abstracts Amer. Math. Soc., 33 (#1, 20912), #1077-11-48.

%D P. Ribenboim, The Book of Prime Number Records. Springer-Verlag, NY, 2nd ed., 1989, p. 263.

%D D. Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, 163.

%H T. Agoh, K. Dilcher, L. Skula, <a href="http://dx.doi.org/10.1006/jnth.1997.2162">Fermat Quotients for Composite Moduli</a>, Journal of Number Theory 66(1), 1997, 29-50.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p.780

%H D. Byeon, <a href="http://trends.mathnet.or.kr/content-2.php?no=369927">Class numbers, Iwasawa invariants and modular forms</a>, Trends in Mathematics, Vol. 9, No. 1, (2006), 25-29.

%H C. K. Caldwell, The Prime Glossary, <a href="http://www.utm.edu/research/primes/glossary/WieferichPrime.html">Wieferich prime</a>

%H C. K. Caldwell, <a href="http://primes.utm.edu/notes/proofs/SquareMerDiv.html">Prime-square Mersenne divisors are Wieferich</a>

%H D. X. Charles, <a href="http://www.cs.wisc.edu/~cdx/Criterion.pdf">On Wieferich Primes</a>

%H R. Crandall, K. Dilcher and C. Pomerance, <a href="http://www.math.dartmouth.edu/~carlp/PDF/paper111.pdf">A search for Wieferich and Wilson primes</a>, Mathematics of Computation, Volume 66, 1997.

%H J. K. Crump, Joe's Number Theory Web, <a href="http://web.archive.org/web/20110728092734/http://www.immortaltheory.com/NumberTheory/Wieferich.htm">Weiferich Primes</a> (sic)

%H John Blythe Dobson, <a href="http://library.uwinnipeg.ca/people/Dobson/mathematics/Wieferich_primes.html">A note on the two known Wieferich Primes</a>

%H J. B. Dobson <a href="http://www.integers-ejcnt.org/vol16.html">A Characterization of Wilson-Lerch Primes</a>, Integers, 16 (2016), A51.

%H F. G. Dorais, <a href="http://www.math.cornell.edu/~dorais/index.php?page=software">WPSE - A Wieferich Prime Search Engine</a> (A program to search Wieferich primes written by F. G. Dorais.) - _Felix Fröhlich_, Jul 13 2014

%H F. G. Dorais and D. W. Klyve, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Klyve/klyve3.html">A Wieferich Prime Search up to 6.7*10^15</a>, Journal of Integer Sequences, Vol. 14, 2011.

%H Will Edgington, <a href="http://www.garlic.com/~wedgingt/mersenne.html">Mersenne Page</a>.

%H A. Granville, K. Soundararajan, <a href="http://dx.doi.org/10.1023/A:1009786614584">A binary additive problem of Erdos and the order of 2 mod p^2</a>, Raman. J. 2 (1998) 283-298

%H Hester Graves and M. Ram Murty, <a href="http://www.mast.queensu.ca/~murty/Wieferich.pdf">The abc conjecture and non-Wieferich primes in arithmetic progressions</a>, Journal of Number Theory, 133 (2013), 1809-1813.

%H Lorenz Halbeisen and Norbert Hungerbuehler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5 (1999) 138-150. (<a href="http://math.berkeley.edu/~halbeis/publications/psf/seq.ps">ps</a>, <a href="http://math.berkeley.edu/~halbeis/publications/pdf/seq.pdf">pdf</a>)

%H S. Jakubec, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa71/aa7114.pdf">Connection between the Wieferich congruence and divisibility of h+</a>, Acta Arithmetica, Vol. 71, No. 1 (1995), 55-64.

%H S. Jakubec, <a href="http://dx.doi.org/10.1090/S0025-5718-98-00916-8">On divisibility of the class number h+ of the real cyclotomic fields of prime degree l</a>, Mathematics of Computation, Vol. 67, No. 221 (1998), 369-398.

%H S. Jakubec, <a href="http://dx.doi.org/10.1006/jnth.1994.1050">The Congruence for Gauss Period</a>, Journal of Number Theory, Vol. 48, No. 1 (1994), 36-45.

%H Wells Johnson, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002193698">On the nonvanishing of Fermat quotients (mod p)</a>, Journal f. die reine und angewandte Mathematik 292, (1977): 196-200.

%H J. Knauer and J. Richstein, <a href="http://dx.doi.org/10.1090/S0025-5718-05-01723-0">The continuing search for Wieferich primes</a>, Math. Comp., 75 (2005), 1559-1563.

%H D. H. Lehmer, <a href="http://dx.doi.org/10.1090/S0025-5718-1981-0595064-5">On Fermat's quotient, base two</a>, Math. Comp. 36 (1981), 289-290.

%H P. Lezak, <a href="http://sourceforge.net/projects/wieferich/">Software for searching Wieferich primes</a> - _Felix Fröhlich_, Jul 13 2014

%H R. J. McIntosh and E. L. Roettger, <a href="http://dx.doi.org/10.1090/S0025-5718-07-01955-2">A search for Fibonacci-Wieferich and Wolstenholme primes</a>, Math. Comp. vol 76, no 260 (2007) pp 2087-2094.

%H C. McLeman, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/WieferichPrime.html">Wieferich prime</a>

%H Sihem Mesnager and Jean-Pierre Flori, <a href="http://eprint.iacr.org/2012/033.pdf">A note on hyper-bent functions via Dillon-like exponents</a>

%H A. Ostafe and I. Shparlinski, <a href="http://arxiv.org/abs/1001.1504"> Pseudorandomness and Dynamics of Fermat Quotients</a>, arXiv:1001.1504 [math.NT], 2010.

%H Christian Perfect, <a href="http://aperiodical.com/2013/07/integer-sequence-reviews-on-numberphile-or-vice-versa/">Integer sequence reviews on Numberphile (or vice versa)</a>, 2013.

%H PrimeGrid, <a href="http://prpnet.primegrid.com:13000/">Wieferich Prime Search statistics</a>

%H M. Rodenkirch, <a href="http://home.roadrunner.com/~mrodenkirch/home/PRPNet.html">PRPNet</a> (The PRPNet package includes wwww, a program that can search for Wieferich and Wall-Sun-Sun primes.) - _Felix Fröhlich_, Jul 13 2014

%H R. Scott and R. Styer, <a href="http://dx.doi.org/10.1016/j.jnt.2003.11.008">On p^x - q^y = c and related three term exponential Diophantine equations with prime bases</a>, Journal of Number Theory, Vol. 105, No. 2 (2004), 212-234.

%H V. Shevelev, <a href="http://arxiv.org/abs/0806.3412">Overpseudoprimes, Mersenne Numbers and Wieferich Primes</a>, arXiv:0806.3412 [math.NT], 2008.

%H J. Silverman, <a href="http://dx.doi.org/10.1016/0022-314X(88)90019-4">Wieferich's Criterion and the abc Conjecture</a>, J. Number Th. 30 (1988) 226-237.

%H J. Sondow, <a href="http://arxiv.org/abs/1110.3113">Lerch quotients, Lerch primes, Fermat-Wilson quotients, and the Wieferich-non-Wilson primes 2, 3, 14771</a>, arXiv 2011.

%H J. Sondow, <a href="http://link.springer.com/chapter/10.1007%2F978-1-4939-1601-6_17">Lerch Quotients, Lerch Primes, Fermat-Wilson Quotients, and the Wieferich-non-Wilson Primes 2, 3, 14771</a>, Combinatorial and Additive Number Theory, CANT 2011 and 2012, Springer Proc. in Math. & Stat., vol. 101 (2014), pp. 243-255.

%H Michel Waldschmidt, <a href="http://www.math.jussieu.fr/~miw/articles/pdf/abcLahore032013.pdf">Lecture on the abc conjecture and some of its consequences</a>, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.

%H Michel Waldschmidt, <a href="http://www.math.jussieu.fr/~miw/articles/pdf/abcLahore2013VI.pdf">Lecture on the abc conjecture and some of its consequences</a>, Abdus Salam School of Mathematical Sciences (ASSMS), Lahore, 6th World Conference on 21st Century Mathematics 2013.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WieferichPrime.html">Wieferich Prime</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/abcConjecture.html">abc Conjecture</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IntegerSequencePrimes.html">Integer Sequence Primes</a>

%H Wieferich Home Page, <a href="http://www.elmath.org/">Search for Wieferich primes</a>

%H A. Wieferich, <a href="http://resolver.sub.uni-goettingen.de/purl?GDZPPN002166968">Zum letzten Fermat'schen Theorem</a>, Journal für die reine und angewandte Mathematik, 136 (1909), 293-302.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Wieferich_prime">Wieferich prime</a>

%H P. Zimmermann, <a href="http://www.loria.fr/~zimmerma/records/primes.html">Records for Prime Numbers</a>

%F A178815(A000720(p))^(p-1) - 1 mod p^2 = A178900(n), where p = a(n). - _Jonathan Sondow_, Jun 29 2010

%F Odd primes p such that A002326((p^2-1)/2) = A002326((p-1)/2). See A182297. - _Thomas Ordowski_, Feb 04 2014

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

%t Select[Prime[Range[50000]],Divisible[2^(#-1)-1,#^2]&] (* _Harvey P. Dale_, Apr 23 2011 *)

%t Select[Prime[Range[50000]],PowerMod[2,#-1,#^2]==1&] (* _Harvey P. Dale_, May 25 2016 *)

%o (Haskell)

%o import Data.List (elemIndices)

%o a001220 n = a001220_list !! (n-1)

%o a001220_list = map (a000040 . (+ 1)) $ elemIndices 1 a196202_list

%o -- _Reinhard Zumkeller_, Sep 29 2011

%o (PARI)

%o N=10^9; default(primelimit,N);

%o forprime(n=2,N,if(Mod(2,n^2)^(n-1)==1,print1(n,", ")));

%o \\ _Joerg Arndt_, May 01 2013

%o (Python)

%o from sympy import prime

%o from gmpy2 import powmod

%o A001220_list = [p for p in (prime(n) for n in range(1,10**7)) if powmod(2,p-1,p*p) == 1]

%o # _Chai Wah Wu_, Dec 03 2014

%Y See A007540 for a similar problem.

%Y 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).

%Y Cf. A001567, A002323, A077816, A001008, A039951, A049094, A126196, A126197, A178815, A178844, A178871, A178900, A246503.

%K nonn,hard,bref,nice,more

%O 1,1

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy .

Last modified September 21 01:31 EDT 2017. Contains 292293 sequences.