A306530 a(n) is the smallest prime q such that Kronecker(q, prime(n)) = 1.

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, 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, 5, 2, 3, 3, 2, 2, 2, 3, 5, 2, 5, 3, 2, 2, 3, 3, 2, 2, 2, 3, 2

Offset: 1

Author

Jianing Song, Feb 22 2019

Keywords

• nonn

Comments

For n >= 2, a(n) is the smallest prime quadratic residue modulo the n-th prime.

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.

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.

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

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

Examples

			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.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A053760 (smallest (prime) quadratic nonresidue modulo prime(n)).

Cf. A024704 (a(n)=2).

Programs

Maple

f:= proc(n) local q,p;
  q:= ithprime(n);
  p:= 1:
  do
    p:= nextprime(p);
    if numtheory:-jacobi(p,q)=1 then return p fi
  od;
end proc:
map(f, [$1..100]); # Robert Israel, Mar 26 2019

Mathematica

a[n_] := Module[{i = 1}, While[KroneckerSymbol[Prime[i], Prime[n]] != 1, i++]; Prime[i]];
Array[a, 100] (* Jean-François Alcover, Jun 08 2020, after PARI *)

PARI

a(n)=my(i=1);while(kronecker(prime(i),prime(n))!=1,i++);prime(i)