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

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).

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 *)

Prog

(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
(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 && t<n-1, r=t)); r \\ Charles R Greathouse IV, Oct 26 2022

Crossrefs

Cf. A228179, A277777, A033948, A060594.

Sequence in context: A284252 A284254 A309206 * A250097 A340678 A028235

Adjacent sequences: A358013 A358014 A358015 * A358017 A358018 A358019

Keyword

nonn

Author

Darío Clavijo, Oct 24 2022

Status

approved