Results 1 to 9 of 9

Math Help - 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 p be a prime such that p \equiv 1\bmod 4.
    I want to understand how 2 is a square in {\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
    2
    Quote Originally Posted by guildmage View Post
    Let p be a prime such that p \equiv 1\bmod 4.
    I want to understand how 2 is a square in {\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 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 \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
    2
    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 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 \left( {s!} \right)\left( {{2^s}} \right).
    Do an example, say with p=17\Longrightarrow s:=\frac{p-1}{2}=8 . Once we pass s means here "once we pass 8", so we'd get:

    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 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 \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; February 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 p \equiv 1 \bmod 4.

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

    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 \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
    2
    Quote Originally Posted by guildmage View Post
    I'm trying to do the same for any prime p \equiv 1 \bmod 4.

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

    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 \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 s=4=0\!\!\pmod 4 then it is obvious that \displaystyle{\frac{s(s+1)}{2}} is even, and if

    s=3k+4=3\!\!\pmod 4 , then 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 p be a prime such that p \equiv 1\bmod 4.
    I want to understand how 2 is a square in {\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: March 12th 2010, 08:37 PM
  2. Quadratic residue -5
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 10th 2010, 01:35 PM
  3. Quadratic Residue
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: November 25th 2009, 08:36 PM
  4. quadratic non residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 13th 2009, 09:36 AM
  5. law of quadratic residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 9th 2008, 09:53 AM

Search Tags


/mathhelpforum @mathhelpforum