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.$
If $p=2$, both products are $1$, so we assume that $p$ is odd. By rules of exponents, the product of the quadratic residues is $$R=g^{(p-1)(p+1)/4}$$ and the product of the quadratic non-residues is $$N=g^{(p-1)(p-1)/4}.$$ Note that the product of all the residues is $-1$. (Each element $x$ cancels with its inverse unless $x$ is its own inverse, and $x^2=1$ has only the solutions $x=\pm 1$.)
If $n\equiv1\pmod4$, then $\frac{p-1}{4}$ is an integer $k$, so that $N=\left(g^{p-1}\right)^k=1$ and therefore, $R=-1$. Similarly, if $n\equiv3\pmod4$, then $\frac{p+1}{4}$ is an integer, so $R=1$ and $N=-1$.
Best Answer
Let $x^2=a+kp^n$ where $a$ is an integer
Case $\#1:$ If $a=0, x$ must be divisible by $\left\lceil\dfrac n2\right\rceil$
So if $n=2m,$ the highest power of $p$ that divides $x,$ can be $m$
In that case $p^{n+1}=p^{2m+1}$ can not divide $x$
Case $\#2:$
If $p\mid k,$ we are done.
Else $p\nmid k\iff(k,p)=1$
For some integer $m,p\nmid m\iff(m,p)=1$
$(x+mp^n)^2=x^2+2x\cdot mp^n+(mp^n)^2$
$=a+p^n(k+2x\cdot m)+(mp^n)^2\equiv a+p^n(k+2x\cdot m)\pmod{p^{n+1}}$
We need $k+2x\cdot m\equiv0\pmod p$
As $(kx,p)=1,$ we can always find $m$ by Bézout's Lemma