login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation (tax deductible in USA) to keep the OEIS running. Over 5000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".

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

%I

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

%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 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 W. Johnson, On the nonvanishing of Fermat quotients (mod p), <a href="http://www-gdz.sub.uni-goettingen.de/cgi-bin/digbib.cgi?PPN243919689_0292">Journal f. die Reine und Angewandte Mathematik 292</a> (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,changed

%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 December 11 03:18 EST 2016. Contains 279034 sequences.