Results 1 to 4 of 4

Math Help - Quadratic reciprocity problem

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    50

    Quadratic reciprocity problem

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Since <br />
p \equiv 1\left( {\bmod .8} \right)<br />
set: <br />
4 \cdot k = \tfrac{{p - 1}}<br />
{2}<br />
for some <br />
k \in \mathbb{Z}^ +  <br />

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

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

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

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

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

    PS.
    Do not double post, see here
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    50
    Excellent, it works.
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    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} }
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Another quadratic reciprocity problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 21st 2011, 06:04 PM
  2. [SOLVED] Quadratic reciprocity
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: July 21st 2011, 03:51 AM
  3. Quadratic Reciprocity
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 20th 2009, 03:14 PM
  4. need help on quadratic reciprocity
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 15th 2009, 02:01 PM
  5. Quadratic Reciprocity
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 25th 2008, 10:09 AM

Search Tags


/mathhelpforum @mathhelpforum