A185103 - OEIS

%I #70 May 18 2022 13:23:51

%S 5,8,17,7,37,18,65,80,101,3,145,19,197,26,257,38,325,28,401,197,485,

%T 28,577,182,677,728,177,14,901,115,1025,485,1157,99,1297,18,1445,170,

%U 1601,51,1765,19,1937,82,2117,53,2305,1047,2501,577,529,338,2917,1451

%N Smallest k > 1 such that k^(n-1) == 1 (mod n^2).

%C a(n) <= n^2 + (-1)^n. - _Thomas Ordowski_, Dec 28 2016

%C If n = p^k for a prime p > 3 and k > 0, then gcd(n, a(n)^2 - 1) = 1. - _Thomas Ordowski_, Nov 27 2018

%C A039678 interleaved with A256517. - _Felix Fröhlich_, Apr 29 2022

%H Michel Lagneau and Charles R Greathouse IV, <a href="/A185103/b185103.txt">Table of n, a(n) for n = 2..10000</a> (terms to 500 from Michel Lagneau)

%H K. Broughan, <a href="http://nzjm.math.auckland.ac.nz/images/d/d6/Relaxations_of_the_ABC_Conjecture_using_integer_k%27th_roots.pdf">Relaxations of the ABC Conjecture using integer k'th roots</a>, New Zealand J. Math. 35(2) (2006), 121-136. - _Felix Fröhlich_, Jun 24 2014

%e a(2) = 5 because 2^(2-1) == 2 (mod 2^2), 3^(2-1) == 3 (mod 2^2), 4^(2-1) == 0 (mod 2^2), but 5^(2-1) == 1 (mod 2^2). - _Petros Hadjicostas_, Sep 15 2019

%p with(numtheory):for n from 2 to 100 do:ii:=0:for k from 1 to 10000 while(ii=0) do:x:=k^(n-1)-1:if irem(x,n^2)=0 and k>1 then ii:=1:printf(`%d, `,k):else fi:od:od:

%t Table[k = 2; While[PowerMod[k, n - 1, n^2] != 1, k++]; k, {n, 2, 100}]

%o (PARI) a(n)=my(v=List([1]));for(k=2,n-1,if(Mod(k,n)^(n-1)==1, if(Mod(k,n^2)^(n-1)==1, return(k)); listput(v,k))); v=vector(#v,i, v[i%#v+1]-v[i]); v[#v]+=n;forstep(k=n+1,n^2+1,v,if(Mod(k,n^2)^(n-1)==1, return(k))) \\ _Charles R Greathouse IV_, Dec 26 2012

%o (PARI) a(n) = for(k=2, 200, if(Mod(k, n^2)^(n-1)==1, return(k))) \\ _Felix Fröhlich_, Apr 29 2022

%o (Python)

%o def a(n):

%o     k, n2 = 2, n*n

%o     while pow(k, n-1, n2) != 1: k += 1

%o     return k

%o print([a(n) for n in range(2, 56)]) # _Michael S. Branicky_, Apr 29 2022

%o (Python)

%o from sympy.ntheory.residue_ntheory import nthroot_mod

%o def A185103(n):

%o     z = nthroot_mod(1,n-1,n**2,True)

%o     return int(z[0]+n**2 if len(z) == 1 else z[1]) # _Chai Wah Wu_, May 18 2022

%Y Cf. A039678, A105222, A220105, A256517.

%K nonn

%O 2,1

%A _Michel Lagneau_, Dec 26 2012

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