A174422 -id:A174422 - cp's OEIS frontend

A039951 a(n) is the smallest prime p such that p^2 divides n^(p-1) - 1.

2, 1093, 11, 1093, 2, 66161, 5, 3, 2, 3, 71, 2693, 2, 29, 29131, 1093, 2, 5, 3, 281, 2, 13, 13, 5, 2, 3, 11, 3, 2, 7, 7, 5, 2, 46145917691, 3, 66161, 2, 17, 8039, 11, 2, 23, 5, 3, 2, 3

Offset: 1

David W. Wilson

a(n^k) <= a(n) for any n,k > 1.
a(n) is currently unknown for n in {47, 72, 186, 187, 200, 203, 222, 231, 304, 311, 335, 355, 435, 454, 546, 554, 610, 639, 662, 760, 772, 798, 808, 812, 858, 860, 871, 983, 986, ...}. - Richard Fischer, Jul 15 2021
a(47) > 1.4*10^14, a(72) > 1.4*10^14 (see Fischer's tables).
For all nonnegative integers n and k, a(n^(n^k)) = a(n) (see Puzzle 762 in the links). Also a(n) = 3 if and only if mod(n, 36) is in the set {8, 10, 19, 26, 28, 35}. - Farideh Firoozbakht and Jahangeer Kholdi, Nov 01 2014

C. K. Caldwell, The Prime Glossary, Fermat quotient.
Richard Fischer, Fermat quotients B^(P-1) == 1 (mod P^2)
Richard Fischer, Update Table of n, July 15 2021.
W. Keller and J. Richstein, Fermat quotients q_p(a) that are divisible by p.
Carlos Rivera, Puzzle 762. Conjecture from Ribenboim's book, The Prime Puzzles and Problems Connection.
Robert G. Wilson v, Table of n, a(n) for n = 1..10000 (with missing terms)

Cf. A001220, A045616, A096082, A014127, A123692, A123693, A174422.

Table[p = 2; While[! Divisible[n^(p - 1) - 1, p^2], p = NextPrime@ p]; p, {n, 33}] (* Michael De Vlieger, Nov 24 2016 *)
f[n_] := Block[{p = 2}, While[ PowerMod[n, p - 1, p^2] != 1, p = NextPrime@ p]; p]; Array[f, 33] (* Robert G. Wilson v, Jul 18 2018 *)

a(n)={forprime(p=2, oo, if(Mod(n, p^2)^(p-1)==1, return(p))); oo} \\ Felix Fröhlich, Jul 24 2014

a(4k+1) = 2.

a(n) = A096082(n) for all n > 1 that are not of the form 4k+1. Note that A096082 begins with n = 2. [Corrected and clarified by Jonathan Sondow, Jun 17-18 2010]

a(34)-a(46) from Helmut Richter (richter(AT)lrz.de), May 17 2004
Entry revised by N. J. A. Sloane, Nov 30 2006
Edited by Max Alekseyev, Oct 06, Oct 09 2009
Edited and updated by Max Alekseyev, Jan 29 2012

A178871 2nd Wieferich prime base prime(n).

Original entry on oeis.org

3511, 1006003, 20771, 491531

Offset: 1

Jonathan Sondow, Jun 20 2010, Jun 24 2010

2nd prime p such that p^2 divides prime(n)^(p-1) - 1.
2nd prime p such that p divides the Fermat quotient q_p(p_n) = ((p_n)^(p-1) - 1)/p, where p_n = prime(n).
a(5) is unknown: 71 is the only known prime p that divides q_p(11).
If a(5) is found, the sequence continues a(6) = 863, a(7) = 3, a(8) = 7, a(9) = 2481757.
See additional comments, references, links, and cross-refs in A039951 and A174422.

			a(1) = 3511 is the 2nd Wieferich prime A001220(2).
a(2) = 1006003 is the 2nd Mirimanoff prime A014127(2).

Wikipedia, Generalized Wieferich primes

Cf. A039951 = smallest prime p such that p^2 divides n^(p-1) - 1, A174422 = first Wieferich prime base prime(n).

{default(primelimit, 10^7); for(n=1, 9, a=prime(n); c=0; forprime(p=2, 10^7, if(Mod(a, p^2)^(p-1)==1, c++; if(c==2, print1(p, ", "); next(2)))); print1(">10^7, "))} \\ Jens Kruse Andersen, Jun 18 2014

A244550 a(n) = first odd Wieferich prime to base a(n-1) for n > 1, with a(1) = 2.

Original entry on oeis.org

2, 1093, 5, 20771, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71, 3, 11, 71

Offset: 1

Felix Fröhlich, Jun 29 2014

a(2) = 1093 since 1093 is the smallest odd Wieferich prime to base 2.
a(3) = 5 since 5 is the smallest odd Wieferich prime to base 1093.
Subsequence starting at a(5) is periodic with period 3, repeating the terms {3, 11, 71}.
Do values for a(1) exist such that the resulting sequence does not eventually become periodic?
The following table lists the values for a(1) and the resulting cycles those values produce. An entry of the form x-y in first column means all terms from x up to and including y reach the corresponding cycle. An entry of the form {t_1, t_2, t_3, ..., t_n} in second column means the listed terms form a repeating cycle. Entries in second column without curly braces mean the listed terms are reached in order and the term following the last listed term is unknown. A question mark means no further terms have been found in the resulting trajectory of a(1).
a(1)             | resulting terms
----------------------------------
2-13, 15-20,     | {3, 11, 71}
22-28, 30-40,    |
42-46, 48-59,    |
62-71, 73-82,    |
84-87, 89-118,   |
120-132, 134-136,|
138, 140-155,    |
157-185, 188,    |
190-195, 197-199 |
                 |
14, 41, 60, 137, | 29
196              |
                 |
21, 29, 47, 61,  | ?
72, 139, 186-187 |
                 |
83               | {4871, 83}
                 |
88               | 2535619637, 139
                 |
119              | 1741
                 |
133              | 5277179
                 |
156              | 347
                 |
189              | 1847
                 |
Notes
------
The terms of the cycle reached from 83 correspond to A124121(4) and A124122(4), so those terms form a double Wieferich prime pair.

R. Fischer, Thema: Fermatquotient B^(P-1) == 1 (mod P^2)
Index entries for linear recurrences with constant coefficients, signature (0,0,1).

Cf. A001220, A124121, A124122, A174422, A244546.

[2, 1093, 5, 20771] cat &cat [[3, 11, 71]^^30]; // Wesley Ivan Hurt, Jun 30 2016

2,1093,5,20771,seq(op([3, 11, 71]), n=5..50); # Wesley Ivan Hurt, Jun 30 2016

Join[{2, 1093, 5, 20771},LinearRecurrence[{0, 0, 1},{3, 11, 71},66]] (* Ray Chandler, Aug 25 2015 *)

i=0; a=2; print1(a, ", "); while(i<100, forprime(p=2, 10^6, if(Mod(a, p^2)^(p-1)==1 && p%2!=0, print1(p, ", "); i++; a=p; break({n=1}))))

From Wesley Ivan Hurt, Jun 30 2016: (Start)
G.f.: x*(2+1093*x+5*x^2+20769*x^3-1090*x^4+6*x^5-20700*x^6) / (1-x^3).
a(n) = a(n-3) for n>7.
a(n) = (85 - 52*cos(2*n*Pi/3) + 68*sqrt(3)*sin(2*n*Pi/3))/3 for n>4. (End)

A179400 Primes which are the fourth element of a generalized Wieferich sequence.

Original entry on oeis.org

331, 359, 1549, 1777, 2011, 6211, 7481, 10369, 13477, 19069, 20431, 22567, 28289, 32933, 39041, 40597, 77713, 96979, 101489

Offset: 1

M. F. Hasler, Jan 10 2011

A generalized Wieferich sequence is an increasing sequence of primes p[1],p[2],... such that a=p[n+1] is a Wieferich prime to base b=p[n], i.e., a^(b-1)=1 (mod b^2).

			The smallest generalized Wieferich sequence of length 4 is (3,11,71,331): 3^10=1 (mod 11^2), 11^70=1 (mod 71^2), 71^330=1 (mod 331^2). Therefore, a(1)=331.
This can actually be extended with 359 to such a sequence of length 5, since 331^358=1 (mod 359^2). Therefore, the next such sequence is (11,71,331,359) and a(2)=359.
Then comes a(3)=1549 from the sequence (307, 487, 1069, 1549). Note that this sequence "starts later" than (197, 653, 1381, 1777) which yields a(4)=1777.

Kevin Acres, Mike Oakes, David Broadhurst, Makoto Kamada, 1993/2011 puzzle, digest of 15 messages in primenumbers Yahoo group, Jan 8 - Jan 9, 2011.
D. Broadhurst, Re: 1993/2011 puzzle [and Puzzle 7], in primenumbers@yahoogroups.com, Jan 2011.

Cf. A001220, A174422 and references therein.

fp(p)={ my(a=precprime(p)); while(Mod(a,p^2)^(p-1)-1 && a=precprime(a-1),);a }
forprime(p=1,default(primelimit),my(a=p); for(c=1,3,(a=fp(a))||next(2));print1(p, ", "))

A244546 Wieferich primes p to base p-th prime.

Original entry on oeis.org

997, 1879, 2617, 85091

Offset: 1

Felix Fröhlich, Jun 29 2014

No further terms up to 10^6.

No further terms up to 10^11. - Luke March, Jul 16 2014

			a(1) = 997, since prime(997) = 7883 and 7883^996 % 997^2 = 1.

Cf. A001220, A174422, A178900, A196202.

forprime(p=2, 10^6, q=prime(p); if(Mod(q, p^2)^(p-1)==1, print1(p, ", ")))

A247072 Smallest Wieferich prime (> sqrt(n)) in base n.

Original entry on oeis.org

2, 1093, 11, 1093, 20771, 66161, 5, 3, 11, 487, 71, 2693, 863, 29, 29131, 1093, 46021, 5, 7, 281

Offset: 1

Eric Chen, Nov 16 2014

a(n) = Smallest prime such that n appears in A143548. - Eric Chen, Nov 26 2014
The square of a(n) is the smallest squared prime that is a pseudoprime (> n) in base n; for example, a(2) = 1093, and 1093^2 = 1194649 is the smallest squared prime that is pseudoprime in base 2. - Eric Chen, Nov 26 2014
Is a(n) defined for all n? - Eric Chen, Nov 26 2014
Does every prime appear in this sequence? - Eric Chen, Nov 26 2014
a(22)..a(28) = {13, 13, 5, 20771, 71, 11, 19}, a(30)..a(46) = {7, 7, 1093, 233, 46145917691, 1613, 66161, 77867, 17, 8039, 11, 29, 23, 103, 229, 1283, 829}, a(48)..a(49) = {7, 491531}, a(51)..a(60) = {41, 461, 47, 19, 30109, 647, 47699, 131, 2777, 29}, a(62)..a(71) = {19, 23, 1093, 17, 89351671, 47, 19, 19, 13, 47}, a(74)..a(81) = {1251922253819, 17, 37, 32687, 43, 263, 13, 11}, a(83)..a(100) = {4871, 163, 11779, 68239, 1999, 2535619637, 13, 6590291053, 293, 727, 509, 11, 2137, 109, 2914393, 28627, 13, 487}; a(n) is currently unknown for n = {21, 29, 47, 50, 61, 72, 73, 82, 126, 132, 154, 186, 187, 188, 200, 203, 222, 231, 237, 301, 304, 309, 311, 327, 335, 347, 351, 355, 357, 435, 441, 454, 458, 496, 541, 542, 546, 554, 570, 593, 609, 610, 639, 640, 654, 662, 668, 674, 692, 697, 698, 701, 718, 724, 725, 727, 733, 743, 760, 772, 775, 777, 784, 798, 807, 808, 812, 829, 841, 858, 860, 871, 883, 912, 919, 944, 980, 983, 986, ...}. - Eric Chen, Nov 26 2014
a(21) > 3.4 * 10^13. - Eric Chen, Nov 26 2014

			a(12) = 2693 because the Wieferich primes to base 12 are 2693, 123653, ..., and 2693 is greater than sqrt(12), so a(12) = 2693.
a(17) = 46021 because the Wieferich primes to base 17 are 2, 3, 46021, 48947, 478225523351, ..., but neither 2 nor 3 is greater than sqrt(17), so a(17) = 46021.

Eric Chen, Table of known a(n) up to a(1000)
Richard Fischer, Fermat quotients B^(P-1) == 1 (mod P^2)
Wikipedia, Wieferich prime

Cf. A039951, A096082, A174422, A178871.

Cf. A001220, A014127, A123692, A212583, A123693, A045616, A111027, A128667, A234810, A242741, A128668, A244260, A090968, A242982, A128669.

a247072[n_] := Block[{p = Int[Sqrt[n]]+1}, While[!PrimeQ[p] || [p < 10^8 && PowerMod[n, p - 1, p^2] != 1], p++]; If[p == 10^8, 0, p]]; Table[ a247072[n], {n, 100}] (* Eric Chen, Nov 27 2014 *)

a(n)=forprime(p=sqrtint(n)+1,,if(Mod(n^(p-1),p^2)==1,return(p)))
n=1; while(n<101, print1(a(n), ", "); n++) \\ Charles R Greathouse IV, Nov 16 2014

A178813 a(n) = (prime(n)^(p-1) - 1)/p^2 mod p, where p is the first prime that divides (prime(n)^(p-1) - 1)/p.

Original entry on oeis.org

487, 4, 1, 1, 46, 1, 0, 1, 11, 1, 2, 1, 0, 2

Offset: 1

Jonathan Sondow, Jun 17 2010

a(n) = (prime(n)^(p-1) - 1)/p^2 mod p, where p = A174422(n) is the first Wieferich prime base prime(n).
a(n) = (prime(n)^(p-1) - 1)/p^2 mod p, where p is the first prime such that p^2 divides prime(n)^(p-1) - 1.
See references and additional comments, links, and cross-refs in A001220 and A039951.
a(15) > 2451011, a(16) = 1, a(17) = 4, a(18) = 1, a(19) = 5, a(20) = 2, a(21) = 0, a(22) = 6, a(23) = 1186, a(24) = 0, a(25) = 0, a(26) = 1, a(27) > 10^5, a(28) = 0, a(29) = 1, a(30) = 0, a(31) = 1, a(32) = 7, a(33) = 0, a(35) = 1, a(36) = 4, a(37) = 1, a(38) = 0, a(40) = 1, a(41) = 2, a(42) = 1, a(43) = 2, a(44) = 0, a(45) = 1, a(46) = 2, a(48) = 30, a(49) = 3, a(50) = 1. - J.W.L. (Jan) Eerland, Sep 27 2024

			Prime(2) = 3 and the first prime p that divides (3^(p-1) - 1)/p is 11, so a(2) = (3^10 - 1)/11^2 mod 11 = 488 mod 11 = 4.

Wikipedia, Generalized Wieferich primes

Cf. A001220, A039951, A174422, A178812, A178814.

Table[If[IntegerQ[s[[2]]],s,{s[[1]], "no solution in range 1 <= k <= 10^5"}], {s,Table[k = 1;Monitor[Parallelize[While[k <= 10^5,If[IntegerQ[((Prime[n]^(Prime[k] - 1) - 1)/Prime[k])/Prime[k]],Break[]]; k++];{n, Mod[(Prime[n]^(Prime[k] - 1) - 1)/Prime[k]^2, Prime[k]]}],k], {n, 1, 10}]}] (* J.W.L. (Jan) Eerland, Sep 27 2024 *)

a(n) = k mod 2, if prime(n) = 4k+1.
a(n) = A178814(prime(n)) .
a(1) = A178812(1).

A178814 (n^(p-1) - 1)/p^2 mod p, where p is the first prime that divides (n^(p-1) - 1)/p.

Original entry on oeis.org

0, 487, 4, 974, 1, 30384, 1, 1, 0, 2, 46, 1571, 1, 17, 24160, 855, 0, 4, 1, 189, 1, 5, 11, 1, 0, 0, 1, 0, 1, 3, 2, 3, 0, 19632919407, 1, 60768, 1, 11, 1435, 8, 0, 0, 2, 2, 1, 1

Offset: 1

Jonathan Sondow, Jun 17 2010

(n^(p-1) - 1)/p^2 mod p, where p is the first prime such that p^2 divides n^(p-1) - 1.

See references and additional comments, links, and cross-refs in A001220 and A039951.

			The first prime p that divides (3^(p-1) - 1)/p is 11, so a(3) = (3^10 - 1)/11^2 mod 11 = 488 mod 11 = 4.

Wikipedia, Generalized Wieferich primes

a(2) = A178812(1) = A178813(1). Cf. A001220, A039951, A174422.

a(n) = (n^(p-1) - 1)/p^2 mod p, where p = A039951(n).
a(n) = k mod 2, if n = 4k+1.
a(prime(n)) = A178813(n).

A253234 Smallest prime p such that p^2 divides n^(p-1)-(n-1)^(p-1).

Original entry on oeis.org

1093, 23, 5, 3, 3457, 72673, 13, 67, 67

Offset: 2

Eric Chen, May 17 2015

According to the generalized Fermat's little theorem, if a prime p does not divide n or n-1, then p must divide n^(p-1)-(n-1)^(p-1), so we can ask that whether there exists a Wieferich-type prime to the "base" (n, n-1), that is, a prime p such that p^2 divides n^(p-1)-(n-1)^(p-1).
a(n) is currently unknown for n = {11, 36, 49, 52, 66, 70, 84, 89, 102, 112, 133, 142, 148, ...}
a(11) > 6.5*10^10.

Eric Chen, Table of n, a(n) for n = 2..1000 status (test limit: 6.5*10^10)
Richard Fischer, Primes p such that (n+1)^(p-1)-n^(p-1) == 0 (mod p^2)

Cf. A039951, A174422.

f[n_] := Block[{k = 1}, While[k < 10^8 && PowerMod[n, Prime[k] - 1, Prime[k]^2] != PowerMod[n - 1, Prime[k] - 1, Prime[k]^2], k++ ]; If[k == 10^8, 0, Prime[k]]]; Table[ f[n], {n, 2, 75}]

for(n=2, 10, forprime(p=2, 1e8, if(Mod(n, p^2)^(p-1)==Mod(n-1, p^2)^(p-1), print1(p, ", "); next({2}))); print1("--, "))

a(9k+5) = 3.

A259909 n-th Wieferich prime to base prime(n), i.e., primes p such that p is the n-th solution of the congruence (prime(n))^(p-1) == 1 (mod p^2).

Original entry on oeis.org

1093, 1006003, 40487

Offset: 1

Felix Fröhlich, Jul 07 2015

Main diagonal of table T(b, p) of Wieferich primes p to prime bases b (that table is not yet in the OEIS as a sequence).
a(4), if it exists, corresponds to A123693(4) and is larger than 9.7*10^14 (cf. Dorais, Klyve, 2011).
a(5), if it exists, corresponds to the 5th base-11 Wieferich prime and is larger than approximately 5.9*10^13 (cf. Fischer).
a(6), if it exists, corresponds to A128667(6) and is larger than approximately 5.9*10^13 (cf. Fischer).

			a(1) = A001220(1) = 1093.
a(2) = A014127(2) = 1006003.
a(3) = A123692(3) = 40487.

W. Keller, Prime solutions p of a^p-1 = 1 (mod p2) for prime bases a, Abstracts Amer. Math. Soc., 19 (1998), 394.

M. Aaltonen and K. Inkeri, Catalan's equation x^p - y^q and related congruences, Mathematics of Computation, Vol. 56 No. 193 (1991), 359-370.
F. G. Dorais and D. Klyve, A Wieferich prime search up to p < 6.7*10^15, J. Integer Seq. 14 (2011), Art. 11.9.2, 1-14.
R. Fischer, Thema: Fermatquotient B^(P-1) == 1 (mod P^2)
W. Keller and J. Richstein, Fermat quotients q_p(a) that are divisible by p (Cached copy at the Wayback Machine).
K. E. Kloss, Some Number-Theoretic Calculations, J. Research of the National Bureau of Standards-B. Mathematics and Mathematical Physics, Vol. 69B, No. 4 (1965), 335-336.

Cf. A001220, A014127, A123692, A123693, A174422, A178871.

a(n) = my(i=0, p=2); while(i < n, if(Mod(prime(n), p^2)^(p-1)==1, i++; if(i==n, break({1}))); p=nextprime(p+1)); p

cp's OEIS Frontend

A039951 a(n) is the smallest prime p such that p^2 divides n^(p-1) - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A178871 2nd Wieferich prime base prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A244550 a(n) = first odd Wieferich prime to base a(n-1) for n > 1, with a(1) = 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A179400 Primes which are the fourth element of a generalized Wieferich sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A244546 Wieferich primes p to base p-th prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

A247072 Smallest Wieferich prime (> sqrt(n)) in base n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A178813 a(n) = (prime(n)^(p-1) - 1)/p^2 mod p, where p is the first prime that divides (prime(n)^(p-1) - 1)/p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A178814 (n^(p-1) - 1)/p^2 mod p, where p is the first prime that divides (n^(p-1) - 1)/p.

Views

Author