Mfcttrf

It is not difficult to check that the least quadratic nonresidue modulo prime $p$ cannot be a composite number, see, for example: Quadratic nonresidues mod p.

It is quite natural to ask the opposite question: Is every prime the least quadratic non-residue modulo some $p$? In the other words, if we are given a prime $q$, is there $p$ such that $q$ is a quadratic nonresidue modulo $p$ and, at the same time, all numbers $1,2,dots,q-1$ are quadratic residues modulo $p$?

I think I have a proof which I outlined in my answer below. However, the proof uses Dirichlet's theorem on arithmetic progressions, which is rather non-elementary result. I was wondering whether there is a more straightforward solution.

I will also include link to the sequence A000229 in OEIS, which is described as: "a(n) is the least number m such that the n-th prime is the least quadratic nonresidue modulo m."

The approach taken in this proof is similar to the proof of Theorem 3 in Section 5.2 of Ireland, Rosen: A Classical Introduction to Modern Number Theory. This theorem states that for every non-square integer $a$ there are infinitely many primes $p$ such that $a$ is a quadratic non-residue modulo $p$.

$newcommandjaco[2]left(frac#1#2right)$Let $q=p_k$ be the $k$-th prime, we also consider all smaller primes $p_1=2<p_2<dots<p_k-1<p_k$. We want to find $p$ such that
$$jaco 2p=jacop_2p = dots = jacop_k-1p = 1 qquadtextaqquad jacop_kp=-1. tag*$$
If there is such $p$, then

• 
  $p_k$ is a quadratic non-residue modulo $p$;


• all smaller primes are quadratic residues modulo $p$.

Since the smallest quadratic non-residue must be prime, we get that $p_k$ the smallest quadratic non-residue modulo $p$.

To get a prime which fulfills $(*)$, we consider the system of congruences
beginalign*
p &equiv 1pmod8\
p &equiv 1pmodp_2\
&vdots\
p &equiv 1pmodp_k-1\
p &equiv spmodp_k
endalign*
where $s$ a is some quadratic non-residue modulo $p_k$.

First, this system of congruences is equivalent to $pequiv a pmod8p_2cdots p_k$ for some $a$, i.e., the solutions form an arithmetic progression. Moreover, it is easy to see that $gcd(a,8p_2cdots p_k)$, since $a$ fulfills all congruences listed above. So we get from Dirichlet's theorem that there is a prime number $p$ which fulfills this system of congruences.

For any such prime we have $$jaco2p=1,$$ since $pequiv 1pmod 8$. At the same time, using
law of quadratic reciprocity together with $pequiv1pmod4$ we get
$$jacop_ip=jacopp_i=jaco1p_i=1.$$

Similarly, we have
$$jacop_kp=jacopp_k=jaco sp_k=-1.$$