|
|
A185103
|
|
Smallest k > 1 such that k^(n-1) == 1 (mod n^2).
|
|
12
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
COMMENTS
|
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
|
|
LINKS
|
|
|
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
(Python)
from sympy.ntheory.residue_ntheory import nthroot_mod
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|