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.$
You correctly recalled the extension to the law of of quadratic reciprocity. So in a prime field $\Bbb{F}_p=\Bbb{Z}/p\Bbb{Z}$ $2$ is a square if and only if $p\equiv\pm1\pmod8$.
In an extension field $\Bbb{F}_q$, $q=p^n$, $p$ an odd prime, you can think of it as follows. If $p\equiv\pm1\pmod8$, then $2$ is a square already in the prime field $\Bbb{F}_p\subseteq\Bbb{F}_q$. But if $p\equiv\pm3\pmod8$, then the polynomial $x^2-2$ is irreducible over $\Bbb{F}_p$. Therefore $K=\Bbb{F}_p[x]/\langle x^2-2\rangle$ is a field, and the zeros of $x^2-2$ both (they are negatives of each other) exist in $K$. We see that $[K:\Bbb{F}_p]=2$, so $K$ has $p^2$ elements. Because to each prime power $q$ there is a unique field of cardinality $q$ we see that $2$ is a square in the field $\Bbb{F}_{p^2}$ when $p\equiv\pm3\pmod8$.
So in the case $p\equiv\pm3\pmod8$ we see that $2$ is a square in the field $\Bbb{F}_{p^n}$ if and only if $K\subseteq\Bbb{F}_{p^n}$. By one of the other basic results about finite fields we know that $\Bbb{F}_{p^2}\subseteq\Bbb{F}_{p^n}$ if and only if $2\mid n$.
Summary: $2$ is a square in the field $\Bbb{F}_{p^n}$, $p$ odd, if and only if either $p\equiv\pm1\pmod8$ or $n$ is even.
Best Answer
If $p$ is an odd prime, $-1$ is a quadratic residue iff $p\equiv 1\pmod{4}$, since $$\left(\frac{-1}{p}\right) \equiv (-1)^{\frac{p-1}{2}}\pmod{p}. $$
On the other hand the Legendre symbol is multiplicative, hence if $p$ is an odd prime and $a$ is a quadratic residue $\!\!\pmod{p}$ we have $$\left(\frac{p-a}{p}\right)=\left(\frac{-a}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{a}{p}\right)=\left(\frac{-1}{p}\right).$$