$p\equiv\pm1\pmod8\to$ 2 not a quadratic residue

Question

Do not understand this statement: if p is congruent to 1 mod 8 then p is congruent to 1 mod 2 so p is a quadratic residue. How to prove 2 is one I'm not sure..

Answer 1

If $p$ is odd, so $p=2n+1$ then $$p^2=(2n+1)^2=4n^2+4n+1=4n(n+1)+1 \equiv 1 \mod 8$$

since $n(n+1)$ is always even. So no number $\equiv -1 \mod 8$ is a quadratic residue.

Answer 2

question statement is not clear. Examples for primes $p \equiv \pm 1 \pmod 8$

$$ 3^2 = 9 \equiv 2 \pmod 9 $$ $$ 6^2 = 36 \equiv 2 \pmod {17} $$ $$ 5^2 = 25 \equiv 2 \pmod {23} $$ $$ 8^2 = 64 \equiv 2 \pmod {31} $$ $$ 17^2 = 289 \equiv 2 \pmod {41} $$ $$ 7^2 = 49 \equiv 2 \pmod {47} $$ $$ 12^2 = 144 \equiv 2 \pmod {71} $$ $$ 32^2 = 1024 \equiv 2 \pmod {73} $$

Answer 3

I will answer what I believe you meant to ask, which is that $$\left(\frac{2}p\right) = 1 \;\text{iff}\; p\equiv \pm1 \mod 8$$

I will use Gauss' Lemma, which states that if $p$ is an odd prime and $I\subset(\Bbb{Z}/p\Bbb{Z})^{\times} $ such that $(\Bbb{Z}/p\Bbb{Z})^{\times}$ is the disjoint union of $I$ and $-I$. Then if $a$ is an integer coprime to $p$, $\left(\frac{a}p\right) = (-1)^t$ where $t= \#\{j\in I : aj\in -I\}$ -this is not too hard to prove but if you have any questions then ask!

Now, we'll take $I= \{1, 2, ... \frac{p-1}2\}$ as is almost invariable...

Write for an odd prime $p = 8k + 2r +1, r\in \{0, 1, 2, 3\}$
Then $I = \{1, 2, ..., 4k+r\}$ and $-I = \{4k + r +1,..., 8k+2r\}$

The elements $j \in I $ with $2j \in -I$ are exactly : $$2k + r', ..., 4k +r $$ where $r'$ is the smallest integer such that $2r' \ge r+1$.
We need the parity of $t$, the size of this set, but taking away/adding an even number of elements from this set keeps the parity the same so we can just find the parity of $u = \# \{r', .., r+2 \}$
We can now just split in to cases;

$\bullet \text{when}\; r=0, r'=1, u=2$
$\bullet \text{when}\; r=1, r'=1, u=3$
$\bullet \text{when}\; r=2, r'=2, u=3$
$\bullet \text{when}\; r=3, r'=2, u=4$
So we get the result that $\left(\frac{2}p\right) = (-1)^t = (-1)^u = 1 \;\text{iff}\; p\equiv \pm1 \mod 8$