How to reduce a polynomial congruences

Question

Consider the Legendre Symbol

(2|p)

which give the congruences

$2^{\frac{p-1}{2}} = (-1)^{\frac{p^2-1}{8}} mod p$.

Now ${\frac{p^2-1}{8}}$ is odd if is equal to 2k+1 with k integer that gives $p^2 = 16 k + 9$ and brings to the polynomial congruences

$p^2 \equiv 9 (mod \,\,\,16)$.

Now the solution gives the congruences

$p \equiv \pm 3 (mod \,\,\,8)$ so a reduction is possible. Do you know why?

Thanks

Answer 1

If $2^{m+2}|(p-a)(p+a),m\ge1$ and $a$ odd

As $p+a,p-a$ have the same parity, both must be even

$\implies2^m|\dfrac{p-a}2\cdot\dfrac{p+a}2$

As the two multipliers have opposite parities

$2^m$ will divide exactly one of them

Answer 2

By direct calculation, you can find that $(\pm3)^2\equiv (\pm11)^2\equiv9\mod 16$. The result follows directly.

However, if you are asking for more general situations, you might be interested in quadratic residues.