Let $s = \frac{p-1}{2}$, and consider the $s$ equations
$$\begin{align}
1&= (-1)(-1) \\
2&=2(-1)^2 \\
3&= (-3)(-1)^3 \\
4&= 4 (-1)^4 \\
& \quad\quad \ldots\\
s&= (\pm s)(-1)^s
\end{align}$$
Where the sign is always chosen to have the correct resulting sign.
Now multiply the $s$ equations together. Clearly on the left we have $s!$. On the right, we have a $2,4,6,\dots$ and some negative odd numbers. But note that $2(s) \equiv -1 \mod p$, $2(s-1) \equiv - 3 \mod p$, and so on, so that the negative numbers are the rest of the even numbers mod $p$, but disguised. So the right side contains $s! (2^s)$ (where we intuit this to mean that one two goes to each of the terms of the factorial, to represent the even numbers $\mod p$).
We only have consideration of $(-1)^{1 + 2 + \ldots + s} = (-1)^{s(s+1)/2}$ left.
Putting this all together, we get that $2^s s! \equiv s! (-1)^{s(s+1)/2} \mod p$, or upon cancelling factorials that $2^s \equiv (-1)^{s(s+1)/2}$. And $s(s+1)/2 = (p^2 - 1)/8$, so we really have $2^{(p-1)/2} \equiv (-1)^{(p^2 - 1)/8}$.
So it depends on $p \pmod 8$. [This is probably the involved manipulation of factorial proof that André alludes to].
You indicated that the problem
Let $k$ be a positive integer and let $p$ be a prime other than $2$ or $5$.
Show that the only solutions, up to congruence, of $x^2 \equiv 25\;(\text{mod}\;p^k)$ are $x \equiv \pm 5\;(\text{mod}\;p^k)$.
is the underlying problem which you are trying to solve.
For the above problem, there is no need to consider quadratic residues.
Instead, we can argue as follows . . .
Suppose $x$ is an integer such that $x^2 \equiv 25\;(\text{mod}\;p^k)$.
Note that $x+5$ and $x-5$ can't both be divisible by $p$, else their difference
$$
(x+5)-(x-5)=10
$$
would be divisible by $p$, contrary to $p\ne 2,5$.
\begin{align*}
\text{Then}\;\;&
x^2 \equiv 25\;(\text{mod}\;p^k)
\\[4pt]
\implies\;&
p^k{\,\mid\,}x^2-25
\\[4pt]
\implies\;&
p^k{\,\mid\,}(x+5)(x-5)
\\[4pt]
\implies\;&
p{\,\mid\,}(x+5)(x-5)
\\[4pt]
\implies\;&
p{\,\mid\,}(x+5)\;\text{or}\;p{\,\mid\,}(x-5)\;\text{but not both}
\\[4pt]
\end{align*}
Then since $p^k{\,\mid\,}(x+5)(x-5)$ and exactly one of $x+5,x-5$ is divisible by $p$, it follows that exactly one of $x+5,x-5$ is divisible by $p^k$.
Therefore $x \equiv \pm 5\;(\text{mod}\;p^k)$, as was to be shown.
Best Answer
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$.