cp's OEIS Frontend

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

%I A366973 #46 Oct 22 2024 23:45:56
%S A366973 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,
%T A366973 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,
%U A366973 3,13,3,3,5,3,3,5,3,3,7,3,3,5,3,3,17,3,3
%N A366973 Smallest odd prime p such that n^((p+1)/2) == n (mod p).
%C A366973 a(n) is the smallest odd prime p for which the Legendre symbol (n / p) >= 0.
%C A366973 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
%C A366973 From _Charles L. Hohn_, Sep 27 2024: (Start)
%C A366973 Smallest odd prime p for which n is a square mod p.
%C A366973 Smallest odd prime p for which n mod p is a member of row A096008(p). (End)
%H A366973 Robin Visser, <a href="/A366973/b366973.txt">Table of n, a(n) for n = 0..10000</a>
%p A366973 f:= proc(n) local p;
%p A366973   p:= 2;
%p A366973   do
%p A366973     p:= nextprime(p);
%p A366973     if n &^ ((p+1)/2) - n mod p = 0 then return p fi
%p A366973   od
%p A366973 end proc:
%p A366973 map(f, [$0..100]); # _Robert Israel_, Oct 30 2023
%t A366973 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 *)
%o A366973 (PARI) a(n) = my(p=3); while(Mod(n, p)^((p+1)/2) != n, p=nextprime(p+1)); p; \\ _Michel Marcus_, Oct 30 2023
%o A366973 (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
%Y A366973 Cf. A309316, A366930, A366982.
%Y A366973 Cf. A096008.
%K A366973 nonn
%O A366973 0,1
%A A366973 _Thomas Ordowski_, Oct 30 2023
%E A366973 More terms from _Amiram Eldar_, Oct 30 2023