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

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

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

Example

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

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}]

Prog

(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

Crossrefs

Cf. A039678, A105222, A220105, A256517.

Sequence in context: A154119 A196387 A258787 * A314566 A096545 A314567

Adjacent sequences: A185100 A185101 A185102 * A185104 A185105 A185106

Keyword

nonn

Author

Michel Lagneau, Dec 26 2012

Extensions

Definition adjusted by Felix Fröhlich, Jun 24 2014

Status

approved