Results 1 to 9 of 9

Thread: When is 2 a quadratic residue?

  1. #1
    Junior Member guildmage's Avatar
    Joined
    Aug 2009
    From
    Philippines
    Posts
    35

    When is 2 a quadratic residue?

    Let $\displaystyle p$ be a prime such that $\displaystyle p \equiv 1\bmod 4$.
    I want to understand how 2 is a square in $\displaystyle {\mathbb{Z}_p}$.

    I have already found this link to the proof: -1 and 2 as Quadratic Residues. But I'm having trouble understanding it.

    I kinda need this for graph theory actually. I'm studying Paley graphs.

    Thanks in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by guildmage View Post
    Let $\displaystyle p$ be a prime such that $\displaystyle p \equiv 1\bmod 4$.
    I want to understand how 2 is a square in $\displaystyle {\mathbb{Z}_p}$.

    I have already found this link to the proof: -1 and 2 as Quadratic Residues. But I'm having trouble understanding it.

    I kinda need this for graph theory actually. I'm studying Paley graphs.

    Thanks in advance!


    What is it EXACTLY that you don't understand? I think it is pretty clear...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member guildmage's Avatar
    Joined
    Aug 2009
    From
    Philippines
    Posts
    35
    I hope you don't mind me going through it piece by piece.

    What does the author mean when he/she said that "Once we pass $\displaystyle s$, the right side still has the even numbers,..."

    It is also not clear to me how the right side of the equation come to contain $\displaystyle \left( {s!} \right)\left( {{2^s}} \right)$.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by guildmage View Post
    I hope you don't mind me going through it piece by piece.

    What does the author mean when he/she said that "Once we pass $\displaystyle s$, the right side still has the even numbers,..."

    It is also not clear to me how the right side of the equation come to contain $\displaystyle \left( {s!} \right)\left( {{2^s}} \right)$.
    Do an example, say with $\displaystyle p=17\Longrightarrow s:=\frac{p-1}{2}=8$ . Once we pass s means here "once we pass 8", so we'd get:

    $\displaystyle 9\times (-1)^9=-9=8\!\!\pmod{17}\,,\,\,10\times (-1)^{10}=10\,,\,\,11\times (-1)^{11}=-11=6\!\!\pmod{17}$ , and etc.

    So we get even numbers in "disguise" of negative ones...

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Nov 2010
    Posts
    58
    Thanks
    18
    Quote Originally Posted by guildmage View Post
    I hope you don't mind me going through it piece by piece.

    What does the author mean when he/she said that "Once we pass $\displaystyle s$, the right side still has the even numbers,..."

    It is also not clear to me how the right side of the equation come to contain $\displaystyle \left( {s!} \right)\left( {{2^s}} \right)$.
    The web page in your link, and the one it links to, are difficult for me to read. This is what I think they're trying to say:

    Let's use p = 17 as was suggested by tonio. Then s = 8. The equations that we want to consider are

    1 = (-1)(-1)^1
    2 = (2)(-1)^2
    3 = (-3)(-1)^3
    4 = (4)(-1)^4
    5 = (-5)(-1)^5
    6 = (6)(-1)^6
    7 = (-7)(-1)^7
    8 = (8)(-1)^8

    Now we multiply all eight equations together, yielding

    8! = (-1)(2)(-3)(4)(-5)(6)(-7)(8)(-1)^(1+2+3+4+5+6+7+8)

    or, since the last factor on the RHS of the equation equals +1,

    8! = (-1)(2)(-3)(4)(-5)(6)(-7)(8)

    Here's where it get confusing. It seems to me that the author wants to convert this last equation into a congruence mod p (or mod 17, in our example). So now we have

    8! == (-1)(2)(-3)(4)(-5)(6)(-7)(8) (mod 17)

    When the author says "Once we pass s, the right side still has the even numbers, but they are disguised as negative numbers.", I think he/she means to replace the negative factors -1, -3, -5 and -7 in this congruence with 17-1=16, 17-3=14, 17-5=12 and 17-7=10. So now we have

    8! == (16)(2)(14)(4)(12)(6)(10)(8) (mod 17)

    Each factor on the RHS of the congruence has a factor of 2, so we get a factor of 2^8. The remaining cofactors are just 1, 2, ..., 8, so we get

    8! == (2^8)8! (mod 17)

    or, dividing by 8!,

    2^8 == 1 (mod 17)

    On this page, the author states that "Therefore [a\p] is the same as a^(p-1)/2." Evidently, the author means

    [a\p] == a^(p-1)/2 (mod p)

    which is usually known as Euler's Criterion. Putting this together, we get

    [2\17] == 2^8 == 1 (mod p)

    which implies that [2\17] = 1, or 2 is a quadratic residue mod 17.

    Perhaps you'd now like to modify this argument to apply to any odd prime p.
    Last edited by Petek; Feb 6th 2011 at 01:28 PM. Reason: Typos
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member guildmage's Avatar
    Joined
    Aug 2009
    From
    Philippines
    Posts
    35
    I'm trying to do the same for any prime $\displaystyle p \equiv 1 \bmod 4$.

    In my analysis of the situation, multiplying equations 1 to s we'll have:

    $\displaystyle s! = (-1)(2)(-3)...(s)(-1)^{1+2+3+...+s}$.

    In the link (that contains the proof), the author said "Finally, the right side includes (-1)1+2++s. The exponent simplifies to s(s+1)/2. This is even when s is 3 or 4 mod 4, which means 2 is a quadratic residue iff p = 1 or 7 mod 8. 2 is the square of 6 mod 17, but it isn't the square of anything mod 13."

    It's not very clear how the author came to conclude that $\displaystyle \frac{s(s+1)}{2}$ is even when s is 3 or 4 mod 4.

    Could you shed a little light on that? Thanks.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    3
    Quote Originally Posted by guildmage View Post
    I'm trying to do the same for any prime $\displaystyle p \equiv 1 \bmod 4$.

    In my analysis of the situation, multiplying equations 1 to s we'll have:

    $\displaystyle s! = (-1)(2)(-3)...(s)(-1)^{1+2+3+...+s}$.

    In the link (that contains the proof), the author said "Finally, the right side includes (-1)1+2++s. The exponent simplifies to s(s+1)/2. This is even when s is 3 or 4 mod 4, which means 2 is a quadratic residue iff p = 1 or 7 mod 8. 2 is the square of 6 mod 17, but it isn't the square of anything mod 13."

    It's not very clear how the author came to conclude that $\displaystyle \frac{s(s+1)}{2}$ is even when s is 3 or 4 mod 4.

    Could you shed a little light on that? Thanks.

    If $\displaystyle s=4=0\!\!\pmod 4$ then it is obvious that $\displaystyle \displaystyle{\frac{s(s+1)}{2}}$ is even, and if

    $\displaystyle s=3k+4=3\!\!\pmod 4$ , then $\displaystyle s+1=0\!\!\pmod 4$ and we're back in the first case above.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member guildmage's Avatar
    Joined
    Aug 2009
    From
    Philippines
    Posts
    35
    Ah... I see. The proof on the link is making much more sense now. Thanks to your replies.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    Quote Originally Posted by guildmage View Post
    Let $\displaystyle p$ be a prime such that $\displaystyle p \equiv 1\bmod 4$.
    I want to understand how 2 is a square in $\displaystyle {\mathbb{Z}_p}$.

    I have already found this link to the proof: -1 and 2 as Quadratic Residues. But I'm having trouble understanding it.

    I kinda need this for graph theory actually. I'm studying Paley graphs.

    Thanks in advance!
    Check out the law of quadratic reciprocity.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quadratic residue mod 2^r
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 12th 2010, 08:37 PM
  2. Quadratic residue -5
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Mar 10th 2010, 01:35 PM
  3. Quadratic Residue
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: Nov 25th 2009, 08:36 PM
  4. quadratic non residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 13th 2009, 09:36 AM
  5. law of quadratic residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Nov 9th 2008, 09:53 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum