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

5, 8, 17, 7, 37, 18, 65, 80, 101, 3, 145, 19, 197, 26, 257, 38, 325, 28, 401, 197, 485, 28, 577, 182, 677, 728, 177, 14, 901, 115, 1025, 485, 1157, 99, 1297, 18, 1445, 170, 1601, 51, 1765, 19, 1937, 82, 2117, 53, 2305, 1047, 2501, 577, 529, 338, 2917, 1451

Offset: 2

Author

Michel Lagneau, Dec 26 2012

Keywords

• nonn

Comments

a(n) <= n^2 + (-1)^n. - Thomas Ordowski, Dec 28 2016

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

A039678 interleaved with A256517. - Felix Fröhlich, Apr 29 2022

Examples

			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
		

Links

• Michel Lagneau and Charles R Greathouse IV, Table of n, a(n) for n = 2..10000 (terms to 500 from Michel Lagneau)
• K. Broughan, Relaxations of the ABC Conjecture using integer k'th roots, New Zealand J. Math. 35(2) (2006), 121-136. - _Felix Fröhlich_, Jun 24 2014

Crossrefs

Cf. A039678, A105222, A220105, A256517.

Programs

Maple

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:

Mathematica

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

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

PARI

a(n) = for(k=2, 200, if(Mod(k, n^2)^(n-1)==1, return(k))) \\ Felix Fröhlich, Apr 29 2022

Python

def a(n):
    k, n2 = 2, n*n
    while pow(k, n-1, n2) != 1: k += 1
    return k
print([a(n) for n in range(2, 56)]) # Michael S. Branicky, Apr 29 2022

Python

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

Extensions

Definition adjusted by Felix Fröhlich, Jun 24 2014