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,1

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

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

Formula

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

Example

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

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

Prog

(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

Crossrefs

Cf. A185103.

Sequence in context: A053787 A314569 A314570 * A259234 A131040 A231786

Adjacent sequences: A039675 A039676 A039677 * A039679 A039680 A039681

Keyword

nonn,nice

Author

Felice Russo

Extensions

More terms from David W. Wilson

Definition adjusted by Felix Fröhlich, Jun 24 2014

Edited by Felix Fröhlich, Nov 24 2018

Status

approved