A358016 a(n) is the largest k <= n-2 such that k^2 == 1 (mod n).

1, 1, 1, 1, 1, 5, 1, 1, 1, 7, 1, 1, 11, 9, 1, 1, 1, 11, 13, 1, 1, 19, 1, 1, 1, 15, 1, 19, 1, 17, 23, 1, 29, 19, 1, 1, 25, 31, 1, 29, 1, 23, 26, 1, 1, 41, 1, 1, 35, 27, 1, 1, 34, 43, 37, 1, 1, 49, 1, 1, 55, 33, 51, 43, 1, 35, 47, 41, 1, 55, 1, 1, 49, 39, 43, 53

Offset: 3

Author

Darío Clavijo, Oct 24 2022

Keywords

• nonn

Comments

It appears that the terms > 1 comprise the sequence A277777.

What is the asymptotic behavior of this sequence? Numerically, it seems like sum_{3 <= n <= x} a(n) is of the order x log x or so. - Charles R Greathouse IV, Oct 27 2022

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 3..10000
• Project Euler, Problem 451. Modular inverses, where a(n) = I(n).

Crossrefs

Cf. A228179, A277777, A033948, A060594.

Programs

Mathematica

lkn[n_]:=Module[{k=n-2},While[PowerMod[k,2,n]!=1,k--];k]; Array[lkn,80,3] (* Harvey P. Dale, Sep 01 2023 *)

PARI

a(n) = forstep(k=n-2, 1, -1, if ((gcd(k, n) == 1) && (lift(Mod(1,n)/k) == k), return(k));); \\ Michel Marcus, Oct 25 2022

PARI

rootsOfUnity(p,e,pe=p^e)=if(p>2, return(Mod([1,-1],pe))); if(e==1, return(Mod([1],2))); if(e==2, return(Mod([1,3],4))); Mod([1,pe/2-1,pe/2+1,-1],pe)
a(n,f=factor(n))=my(v=apply(x->rootsOfUnity(x[1],x[2]),Col(f)),r,t); forvec(u=vector(#v,i,[1,#v[i]]), t=lift(chinese(vector(#u,i,v[i][u[i]]))); if(t>r && tCharles R Greathouse IV, Oct 26 2022

Python

def a(n):
  for k in range(n - 2, 0, -1):
    if pow(k,2,n) == 1: return k

Python

from sympy.ntheory import sqrt_mod_iter
def A358016(n): return max(filter(lambda k: k<=n-2,sqrt_mod_iter(1,n))) # Chai Wah Wu, Oct 26 2022