Quadratic reciprocity problem

**Inti** · November 24th 2008, 08:29 AM

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

**PaulRS** · November 24th 2008, 10:47 AM

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

**Inti** · November 24th 2008, 01:17 PM

Excellent, it works.
Thanks!

**ThePerfectHacker** · November 24th 2008, 07:04 PM

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)$ .
--------
You may ask how do we know the quadradic charachter of two?
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} }$

Thread: Quadratic reciprocity problem

LinkBack

Thread Tools

Display

Quadratic reciprocity problem

Similar Math Help Forum Discussions

[SOLVED] Another quadratic reciprocity problem

[SOLVED] Quadratic reciprocity

Quadratic Reciprocity

need help on quadratic reciprocity

Quadratic Reciprocity

Search Tags