%I #31 Mar 05 2022 23:02:54
%S 7,7,11,2,3,3,2,5,2,5,2,3,2,11,2,7,3,3,17,2,2,2,3,2,2,5,2,3,3,2,2,3,2,
%T 5,5,2,3,41,2,13,3,3,2,2,7,2,5,2,3,3,2,2,2,3,2,2,5,2,3,2,7,17,7,2,2,7,
%U 5,2,3,3,2,2,2,3,5,2,5,3,2,2,3,3,2,2,2,3,2
%N a(n) is the smallest prime q such that Kronecker(q, prime(n)) = 1.
%C For n >= 2, a(n) is the smallest prime quadratic residue modulo the n-th prime.
%C Also for n >= 2, a(n) is the smallest prime that decomposes in the quadratic field Q[sqrt((-1)^((p-1)/2)*p)], p = prime(n). Using this definition, a(1) should have been 5 because for p = 2, Q[sqrt((-1)^((p-1)/2)*p)] = Q[sqrt(2*i)] = Q[1+i] = Q[i], in which 5 decomposes.
%C For most n, a(n) is relatively small. Among [1, 10000], there are only 669 n's that violate a(n) < prime(n)/n and 97 n's > 1 that violate a(n) < prime(n)*log(log(n))/n. In fact, if we ignore the first three terms, the only terms among the first 10000 ones that seem unusually large are a(14) = 11, a(19) = 17, a(38) = 41, a(62) = 17, a(1137) = 29, a(1334) = 29, a(3935) = 37, a(7309) = 43, a(8783) = 37 and a(8916) = 41, with the corresponding primes 43, 67, 163, 293, 9173, 10987, 37123, 74093, 90787, 92333.
%C For every prime p there are infinitely many n such that a(n)=p. Indeed, using quadratic reciprocity, for each prime p_j <= p we can choose k_j coprime to p_j, such that p_j is a quadratic nonresidue (if p_j < p) or residue (if p_j = p) mod q for every prime q == k_j (mod p_j). Dirichlet's theorem on primes in arithmetic progressions implies there are infinitely many primes q with q == k_j (mod p_j) for all j. Then a(n) = p where q = prime(n). - _Robert Israel_, Mar 26 2019
%C a(n) is the smallest prime q such that the congruence x^2 == q (mod p) has a solution x, where p = prime(n). For n > 1, a(n) is the smallest prime q such that q^((p-1)/2) == 1 (mod p), where odd p = prime(n). - _Thomas Ordowski_, Apr 29 2019
%H Robert Israel, <a href="/A306530/b306530.txt">Table of n, a(n) for n = 1..10000</a>
%e 2, 3, 5, 7, ..., 37 are all quadratic nonresidues modulo prime(38) = 163, while 41 is a quadratic residue modulo 163, so a(38) = 41.
%p f:= proc(n) local q,p;
%p q:= ithprime(n);
%p p:= 1:
%p do
%p p:= nextprime(p);
%p if numtheory:-jacobi(p,q)=1 then return p fi
%p od;
%p end proc:
%p map(f, [$1..100]); # _Robert Israel_, Mar 26 2019
%t a[n_] := Module[{i = 1}, While[KroneckerSymbol[Prime[i], Prime[n]] != 1, i++]; Prime[i]];
%t Array[a, 100] (* _Jean-François Alcover_, Jun 08 2020, after PARI *)
%o (PARI) a(n)=my(i=1);while(kronecker(prime(i),prime(n))!=1,i++);prime(i)
%Y Cf. A053760 (smallest (prime) quadratic nonresidue modulo prime(n)).
%Y Cf. A024704 (a(n)=2).
%K nonn
%O 1,1
%A _Jianing Song_, Feb 22 2019
|