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

Author

David W. Wilson

Keywords

• nonn
• more
• hard

Comments

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

Links

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

Crossrefs

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

Programs

Mathematica

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

PARI

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

Formula

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]

Extensions

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