Results 1 to 4 of 4

Thread: 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 $\displaystyle
    p \equiv 1\left( {\bmod .8} \right)
    $ set: $\displaystyle
    4 \cdot k = \tfrac{{p - 1}}
    {2}
    $ for some $\displaystyle
    k \in \mathbb{Z}^ +
    $

    So:$\displaystyle
    \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: $\displaystyle
    \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): $\displaystyle
    \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: $\displaystyle
    \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: $\displaystyle
    \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: $\displaystyle
    \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
    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 $\displaystyle (-2/p)=1$ are $\displaystyle p\equiv 1,3 (\bmod 8)$.

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


    In case one: $\displaystyle p\equiv 1(\bmod 4)$ and $\displaystyle p\equiv \pm 1(\bmod 8)$.
    In case two: $\displaystyle p\equiv 3(\bmod 4)$ and $\displaystyle p\equiv \pm 3(\bmod 8)$.
    Combining these congruences tells us that $\displaystyle p\equiv 1(\bmod 8)$ or $\displaystyle 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. $\displaystyle \alpha$ is algebraic integer iff it solves some $\displaystyle x^n + a_{n-1}x^{n-1}+...+a_1x+a_0 = 0$ where $\displaystyle a_i \in \mathbb{Z}$.
    Now let us define $\displaystyle \alpha \equiv_0 \beta (\bmod \gamma)$ if $\displaystyle (\alpha - \beta) = \gamma \delta$ for algebraic integer $\displaystyle \delta$.
    If $\displaystyle a\equiv_0 b (\bmod c)$ then it can be shown that $\displaystyle a\equiv b (\bmod c)$ i.e. $\displaystyle c$ divides $\displaystyle a-b$ in the regular case.
    Therefore, we will drop $\displaystyle \equiv_0$ notation because it is compatible with the old $\displaystyle \equiv$ definition if the numbers are regular integers.

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

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

    Define the function $\displaystyle 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,
    $\displaystyle f(p ) \alpha = (2/p)\alpha (\bmod p)$
    Multiply by $\displaystyle \alpha$ to get,
    $\displaystyle 2f(p) \equiv 2(2/p) (\bmod p) \implies f(p) \equiv (2/p) (\bmod p)$.
    Since $\displaystyle f(p)$ and $\displaystyle (2/p)$ can only take $\displaystyle \pm 1$ values.
    It means $\displaystyle f(p) = (2/p)$.

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

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

    Thus, $\displaystyle \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: Jul 21st 2011, 05:04 PM
  2. [SOLVED] Quadratic reciprocity
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jul 21st 2011, 02:51 AM
  3. Quadratic Reciprocity
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 20th 2009, 02:14 PM
  4. need help on quadratic reciprocity
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Apr 15th 2009, 01:01 PM
  5. Quadratic Reciprocity
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 25th 2008, 09:09 AM

Search Tags


/mathhelpforum @mathhelpforum