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

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

Links

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

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

Prog

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

Crossrefs

Cf. A309316, A366930, A366982.

Sequence in context: A089488 A367034 A366982 * A076560 A359048 A096915

Adjacent sequences: A366970 A366971 A366972 * A366974 A366975 A366976

Keyword

nonn

Author

Thomas Ordowski, Oct 30 2023

Extensions

More terms from Amiram Eldar, Oct 30 2023

Status

approved