Use Gauss' Lemma to find Legendre symbol $\left(\frac{-1}{n}\right)$ for $n \equiv 1, 3, 5, 7 \pmod 8$.

Question

I know that if $ n \equiv 1 \pmod 4$, then $\left(\frac{-1}{n}\right)=1$, but in this case we are dealing with mod $8$.

If $n \equiv 1 \pmod 8$, then $n=1+8k$. So, $(8k+1-1)/2=4k$. So, we have: $$1,2, \dots, 4k$$ Multiplying each term by $(-1)$: $$-1,-2, \dots, -4k$$ $$8k+1-1, 8k+1-2, \dots , 8k+1-4k$$ $$8k, 8k-1, \dots, 4k+1$$

Each term is greater than $4k$ and there are $4k$ such terms, so Gauss' Lemma says $\left(\frac{-1}{n}\right)=(-1)^{4k}=1$

Is there an easier and/or neater way to do this. I must use Gauss' Lemma to find $\left(\frac{-1}{n}\right), \left(\frac{2}{n}\right), \left(\frac{-2}{n}\right)$ for $n \equiv 1,3,5,7 \pmod 8$.

Answer 1

I'll give you the idea:

$\left(\frac{2}{p}\right) = (-1)^x $ where $ x =\left|\{1 \leq j \leq \frac{p-1}{2} \mid p \geq 2j \pmod p \text{ (the least such positive integer value mod p)} \geq 0\} \right|$ by Gauss' Lemma.

Use the floor function on $p$, and test cases $p = 8k +1, \dots 8k + 7$ noting that $ x = \frac{p-1}{2} - \lfloor \frac{p}{4} \rfloor$ (Why? Check for yourself, but it's just a bit of algebraic manipulation)

Then for $\left(\frac{-2}{p}\right)$ will follow from multiplicativity of the Legendre symbol.

Your method above is fine for the $-1$ case.