A366973 Smallest odd prime p such that n^((p+1)/2) == n (mod p).

3, 3, 7, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 11, 3, 3, 5, 3, 3, 5, 3, 3, 11, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 13, 3, 3, 5, 3, 3, 5, 3, 3, 7, 3, 3, 5, 3, 3, 17, 3, 3

Offset: 0

Author

Thomas Ordowski, Oct 30 2023

Keywords

• nonn

Comments

a(n) is the smallest odd prime p for which the Legendre symbol (n / p) >= 0.

For any set S of odd primes, by Chinese Remainder Theorem, there is n such that n is a primitive root mod each prime p in S, and then n^((p-1)/2) != 1 (mod p). Since n is invertible mod p, n^((p-1)/2) != 1 (mod p) implies n^((p+1)/2) != n (mod p). So this sequence is unbounded. - Robert Israel, Oct 31 2023

From Charles L. Hohn, Sep 27 2024: (Start)

Smallest odd prime p for which n is a square mod p.

Smallest odd prime p for which n mod p is a member of row A096008(p). (End)

Links

• Robin Visser, Table of n, a(n) for n = 0..10000

Crossrefs

Cf. A309316, A366930, A366982.

Cf. A096008.

Programs

Maple

f:= proc(n) local p;
  p:= 2;
  do
    p:= nextprime(p);
    if n &^ ((p+1)/2) - n mod p = 0 then return p fi
  od
end proc:
map(f, [$0..100]); # Robert Israel, Oct 30 2023

Mathematica

a[n_] := Module[{p = 3}, While[PowerMod[n, (p + 1)/2, p] != Mod[n, p], p = NextPrime[p]]; p]; Array[a, 100, 0] (* Amiram Eldar, Oct 30 2023 *)

PARI

a(n) = my(p=3); while(Mod(n, p)^((p+1)/2) != n, p=nextprime(p+1)); p; \\ Michel Marcus, Oct 30 2023

PARI

a(n) = for(i=2, oo, my(p=prime(i)); for(j=0, (p-1)/2, if(n%p==j^2%p, return(p)))) \\ Charles L. Hohn, Sep 27 2024

Extensions

More terms from Amiram Eldar, Oct 30 2023