A039678 - OEIS

%I #46 May 18 2022 13:13:03

%S 5,8,7,18,3,19,38,28,28,14,115,18,51,19,53,338,53,264,143,11,306,31,

%T 99,184,53,181,43,164,96,68,38,58,19,328,313,78,226,65,253,259,532,78,

%U 176,276,143,174,165,69,330,44,33,332,94,263,48,79,171,747,731,20,147,91,40

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

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

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

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

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

%H T. D. Noe, <a href="/A039678/b039678.txt">Table of n, a(n) for n = 1..10000</a>

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

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

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

%o (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

%o (Python)

%o from sympy import prime

%o from sympy.ntheory.residue_ntheory import nthroot_mod

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

%Y Cf. A185103.

%K nonn,nice

%O 1,1

%A _Felice Russo_

%E More terms from _David W. Wilson_

%E Definition adjusted by _Felix Fröhlich_, Jun 24 2014

%E Edited by _Felix Fröhlich_, Nov 24 2018