A039678 Smallest number m > 1 such that m^(p-1)-1 is divisible by p^2, where p = n-th prime.

5, 8, 7, 18, 3, 19, 38, 28, 28, 14, 115, 18, 51, 19, 53, 338, 53, 264, 143, 11, 306, 31, 99, 184, 53, 181, 43, 164, 96, 68, 38, 58, 19, 328, 313, 78, 226, 65, 253, 259, 532, 78, 176, 276, 143, 174, 165, 69, 330, 44, 33, 332, 94, 263, 48, 79, 171, 747, 731, 20, 147, 91, 40

Offset: 1

Author

Felice Russo

Keywords

• nonn
• nice

Comments

Using Fermat's little theorem twice, it is easy to see that m=p^2-1 solves this problem for all odd primes p. In fact, there appear to be exactly p-1 values of m with 1 <= m <= p^2 for which m^(p-1) == 1 (mod p^2). See A096082 for the related open problem. - T. D. Noe, Aug 24 2008

That there are exactly p-1 values of 1 <= m <= p^2 for which m^(p-1) == 1 (mod p^2) follows immediately from Hensel's lifting lemma and Fermat's little theorem - every solution mod p corresponds to a unique solution mod p^2. - Phil Carmody, Jan 10 2011

For n > 2, prime(n) does not divide a(n)^2 - 1, so a(n) is the smallest m > 1 such that (m^(prime(n)-1) - 1)/(m^2 - 1) == 0 (mod prime(n)^2). - Thomas Ordowski, Nov 24 2018

Examples

			For n=3, p=5 is the third prime and 5^2 = 25 divides 7^4 - 1 = 2400.
		

References

• P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, 345-349.

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A185103.

Programs

Mathematica

dpa[n_]:=Module[{p=Prime[n],a=2},While[PowerMod[a,p-1,p^2]!=1,a++];a]; Array[dpa,70] (* Harvey P. Dale, Sep 05 2012 *)

PARI

a(n) = my(p=prime(n)); for(a=2, oo, if(Mod(a, p^2)^(p-1)==1, return(a))) \\ Felix Fröhlich, Nov 24 2018

Python

from sympy import prime
from sympy.ntheory.residue_ntheory import nthroot_mod
def A039678(n): return 2**2+1 if n == 1 else int(nthroot_mod(1,(p:= prime(n))-1,p**2,True)[1]) # Chai Wah Wu, May 18 2022

Formula

a(n) = A185103(A000040(n)).

Extensions

More terms from David W. Wilson

Definition adjusted by Felix Fröhlich, Jun 24 2014

Edited by Felix Fröhlich, Nov 24 2018