I´m stuck with this problem, whose goal is to prove that (-2|p)=1 (i.e: -2 is a quadratic residue modulo p) if p=1,3 (mod 8).

first part is to prove it for p=1 (mod 8) and they tell me to use the following factorization (that´s the only hint for the exercise):
((x^8k)-1)=(((x^2k)-1)^2)+2(x^2k))((x^4k)-1) (if you write it in paper this factorization becomes pretty clear)

I´m aware that I have to use Euler´s Criterion: (a|p)=1 if and only if
(a)^(p-1/2)=1 (mod p), but I don´t know how.

I will appreciate any kind of help

thank you

2. Since $
p \equiv 1\left( {\bmod .8} \right)
$
set: $
4 \cdot k = \tfrac{{p - 1}}
{2}
$
for some $
k \in \mathbb{Z}^ +
$

So: $
\left( { - 2} \right)^{p - 1} - 1 = \left[ {\left( {\left( { - 2} \right)^{\tfrac{{p - 1}}
{4}} - 1} \right)^2 + 2 \cdot \left( { - 2} \right)^{\tfrac{{p - 1}}
{4}} } \right] \cdot \left[ {\left( { - 2} \right)^{\tfrac{{p - 1}}
{2}} - 1} \right]
$

By Fermat's Little Theorem: $
\left[ {\left( {\left( { - 2} \right)^{\tfrac{{p - 1}}
{4}} - 1} \right)^2 + 2 \cdot \left( { - 2} \right)^{\tfrac{{p - 1}}
{4}} } \right] \cdot \left[ {\left( { - 2} \right)^{\tfrac{{p - 1}}
{2}} - 1} \right] \equiv 0\left( {\bmod .p} \right)
$

At this point assume by absurd that -2 is not a quadratic residue mod p, thus we must have (by Euclid's Lemma): $
\left( {\left( { - 2} \right)^{\tfrac{{p - 1}}
{4}} - 1} \right)^2 + 2 \cdot \left( { - 2} \right)^{\tfrac{{p - 1}}
{4}} \equiv 0\left( {\bmod .p} \right)
$

Then: $
\left( {\left( { - 2} \right)^{\tfrac{{p - 1}}
{4}} - 1} \right)^2 \equiv \left( { - 2} \right)^{\tfrac{{p + 3}}
{4}} \left( {\bmod .p} \right)
$
so the RHS is a quadratic residue, thus by Euler's Criterion: $
\left[ {\left( { - 2} \right)^{\tfrac{{p + 3}}
{4}} } \right]^{\tfrac{{p - 1}}
{2}} = \left[ {\left( { - 2} \right)^{\tfrac{{p - 1}}
{2}} } \right]^{\tfrac{{p + 3}}
{4}} \equiv 1\left( {\bmod .p} \right)
$

However: $
\left( {\tfrac{{ - 2}}
{p}} \right) = - 1 \Rightarrow \left[ {\left( { - 2} \right)^{\tfrac{{p - 1}}
{2}} } \right]^{\tfrac{{p + 3}}
{4}} \equiv \left[ { - 1} \right]^{\tfrac{{p + 3}}
{4}} \equiv - 1\left( {\bmod .p} \right)
$
( since 4 divides p+3, but 8 doesn't) CONTRADICTION!

PS.
Do not double post, see here

3. Excellent, it works.
Thanks!

4. We can do something stronger. We can show that the only primes that have $(-2/p)=1$ are $p\equiv 1,3 (\bmod 8)$.

Notice that $(-2/p) = (-1/p)(2/p)$.
Thus, we require that:
• $(-1/p)=(2/p)=1$
• $(-1/p)=(-2/p)=-1$

In case one: $p\equiv 1(\bmod 4)$ and $p\equiv \pm 1(\bmod 8)$.
In case two: $p\equiv 3(\bmod 4)$ and $p\equiv \pm 3(\bmod 8)$.
Combining these congruences tells us that $p\equiv 1(\bmod 8)$ or $p\equiv 3(\bmod 8)$.
--------
A typical approach is to use Gauss' lemma however here is another approach using algebraic integers.
An algebraic integer is a complex number that solves a monic (non-zero) polynomial in integer cofficient i.e. $\alpha$ is algebraic integer iff it solves some $x^n + a_{n-1}x^{n-1}+...+a_1x+a_0 = 0$ where $a_i \in \mathbb{Z}$.
Now let us define $\alpha \equiv_0 \beta (\bmod \gamma)$ if $(\alpha - \beta) = \gamma \delta$ for algebraic integer $\delta$.
If $a\equiv_0 b (\bmod c)$ then it can be shown that $a\equiv b (\bmod c)$ i.e. $c$ divides $a-b$ in the regular case.
Therefore, we will drop $\equiv_0$ notation because it is compatible with the old $\equiv$ definition if the numbers are regular integers.

If $p$ is a prime then $(\alpha + \beta)^p \equiv \alpha^p + \beta^p (\bmod p)$, we will use this fact soon.
--------
Let $\zeta = e^{2\pi i/8}$, this is an algebraic integer.
Notice that $\zeta^2 + \zeta^{-2} = 0$. Set $\alpha = \zeta + \zeta^{-1}$.
It is easy to see that $\alpha^2 = 2$ therefore:
$\alpha^{p-1} = \left( \alpha^2 \right)^{(p-1)/2} = 2^{(p-1)/2} \equiv (2/p) (\bmod p)$ and so $\alpha^p \equiv (2/p)\alpha (\bmod p)$.
However, $\alpha^p = (\zeta + \zeta^{-1})^p \equiv \zeta^p + \zeta^{-p} (\bmod p)$. .... [1]

If $p\equiv \pm 1(\bmod 8)$ then $\zeta^p + \zeta^{-p} = \zeta + \zeta^{-1} = \alpha$.
If $p\equiv \pm 3(\bmod 8)$ then $\zeta^p+\zeta^{-p} \equiv \zeta^3 + \zeta^{-3} = -(\zeta + \zeta^{-1}) = -\alpha$.

Define the function $f( p ) = 1 \text{ if }p\equiv \pm 1(\bmod 8) \text{ and } -1 \text{ if }p\equiv \pm 3(\bmod 8)$.

Combining these results with [1] we see that,
$f(p ) \alpha = (2/p)\alpha (\bmod p)$
Multiply by $\alpha$ to get,
$2f(p) \equiv 2(2/p) (\bmod p) \implies f(p) \equiv (2/p) (\bmod p)$.
Since $f(p)$ and $(2/p)$ can only take $\pm 1$ values.
It means $f(p) = (2/p)$.

Consequently, $(2/p) = 1$ if and only if $p\equiv \pm 1(\bmod p)$. And that is our quadradic charachter.

By the way, with a little work we can show $f(p) = (-1)^{(p^2 - 1)/8}$.

Thus, $\boxed{ (2/p) = (-1)^{(p^2-1)/8} }$