Jacobi Symbol To Determine Quadratic Residue

Question

I have an exam tomorrow and I have no idea how I would do this type of question and I'm pretty sure its coming up can someone please help me out by maybe doing one as an example and explaining what then done and why I'd really appreciate it

Answer 1

Well, for an odd prime $p$, the Jacobi symbol in modulus $p$ is by definition positive if and only if $2$ is a quadratic residue. Given the alternative formula for the Jacobi symbol provided in this problem, you know that $2$ is a quadratic residue modulo $p$ if and only if $(p^2 - 1)/8$ is even. Equivalently you need $p^2 \equiv 1 \pmod{16}$, and this will be satisfied if and only if $p \equiv a \pmod 8$ for certain $a \in \{1,3,5,7\}$. For example, if $p \equiv 1 \pmod 8$, then $p = 8n + 1 \implies p^2 = 64n^2 + 16n + 1 = 16(4n^2 + 1) + 1$. So if $p \equiv 1 \pmod 8$, then $2$ is a quadratic residue modulo $p$. Now you try the rest!