$p \gt 2$ is a prime, then there are infinite primes $q$ such that $q$ is a quadratic residue modulo $p$.
With Dirichlet's theorem on arithmetic progressions, the problem is easy! How about Without the use of the theorem? Can one find an elementary proof?
p.s. there are several elementary ways(without Dirichlet) to show that there are infinite primes $q$ such that $q$ is a quadratic non-residue modulo $p$
Proof 1 The least $q>0$ quadratic non-residue modulo $p$ is a prime . Consider
$$a_0=q, a_1=q+p,a_2=q+pa_1,a_3=q+pa_1a_2,\dotsc, a_n=q+pa_1a_2\dotsb a_{n-1},\dotsc $$
then $(a_i,a_j)=1$
Proof 2 Only $\dfrac{p-1}2$ quadratic non-residues modulo $p$, so there is a integer $a$ such that $(\dfrac{a^2+1}p)=-1$.
In not, only finite $q_1,q_2,\dotsc, q_n$. then there exists $k\in\Bbb Z$ such that $kq_1q_2\dotsb q_n \equiv a \pmod p$. Consider
$$ (kq_1q_2\dotsb q_n)^2 +1$$
Best Answer
Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 3 \pmod 4} $$
Lemma: $$ (-p|q) = (q|p). $$
Lemma: If $$ a^2 + p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$
Let $$ F_1 = 4 + p, $$ $$ F_2 = 4 F_1^2 + p, $$ $$ F_3 = 4 F_1^2 F_2^2 + p, $$ $$ F_4 = 4 F_1^2 F_2^2 F_3^2 + p, $$ $$ F_5 = 4 F_1^2 F_2^2 F_3^2 F_4^2 + p, $$ and so on.
These are all of the form $a^2 + p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Given ODD primes $p \neq q:$ and $$ \color{magenta}{p \equiv 1 \pmod 4} $$
Lemma: $$ (p|q) = (q|p). $$
Lemma: If $$ a^2 - p \equiv 0 \pmod q, $$ THEN $$ (q|p) = 1. $$
FIND an even square $$ W = 4^k = \left( 2^k \right)^2 $$ such that $$ \color{magenta}{ W > p.} $$
Let $$ F_1 = W - p, $$ $$ F_2 = W F_1^2 - p, $$ $$ F_3 = W F_1^2 F_2^2 - p, $$ $$ F_4 = W F_1^2 F_2^2 F_3^2 - p, $$ $$ F_5 = W F_1^2 F_2^2 F_3^2 F_4^2 - p, $$ and so on. As $p \equiv 1 \pmod 4$ and $W \equiv 0 \pmod 4,$ we know $W - p \equiv 3 \pmod 4 $ and so $W-p \geq 3. $ So the $F_j$ are larger than $1$ and strictly increasing.
These are all of the form $a^2 - p$ and are odd, so the only primes than can be factors are quadratic residues for $p.$ Next, all the $F_j$ are prime to $p$ itself. Finally, these are all coprime. So, however they factor, we get an infinite list of primes that are quadratic residues of $p.$