1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove is p is prime and p = 1 (mod 4), then x^2 = -1 (mod p) has a solution

  1. Sep 8, 2012 #1
    1. The problem statement, all variables and given/known data

    Prove that if p is prime and p [itex]\equiv[/itex] 1 (mod 4), then [itex]x^{2}[/itex] [itex]\equiv[/itex] -1 (mod p) has a solution (x).

    2. Relevant equations

    We already have proved (p-1)! [itex]\equiv[/itex] -1 (mod p)
    Hint: Use the properties of [itex]Z_{p}[/itex] - a field that partitions the integers into p equivalence classes denoted [itex]\overline{a}[/itex] where [itex]\overline{a}[/itex] = {integers z such that z [itex]\equiv[/itex] a (mod p) } and try x = ([itex]\overline{1}[/itex] )([itex]\overline{2}[/itex] )([itex]\overline{3}[/itex] )...([itex]\overline{(p-1)/2}[/itex] )

    3. The attempt at a solution

    The idea I have, judging from the hint and what we already know about (p-1)!, is that I need to show that

    x2 = ( ([itex]\overline{1}[/itex] )([itex]\overline{2}[/itex] )([itex]\overline{3}[/itex] )...([itex]\overline{(p-1)/2}[/itex] ) )2

    is equivalent to (p-1)! mod p

    I have no idea how to do this though. I figure if I knew why (p-1)/2 was chosen, I could figure it out.

    Others things I know:

    p = 4k + 1 for some integer k
    so p-1 is even
    so (p-1)/2 is an integer
     
  2. jcsd
  3. Sep 9, 2012 #2
    Let me give you two hints:
    you want to show that (p-1)!=(((p-1)/2)!)^2
    you can cancel out (p-1)/2 terms on both sides (I'll let you figure out which ones)
    now, with what's left, try to put in negative numbers and see if that gives you anything
     
  4. Sep 9, 2012 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    It seems to me a serious problem that this simply is NOT true for, say, p= 9= 4(2)+ 1.
    1^2= 1= 1 (mod 9)
    2^2= 4= 4 (mod 9)
    3^2= 9= 0 (mod 9)
    4^2= 16= 7 (mod 9)
    5^2= 25= 7 (mod 9)
    6^2= 36= 0 (mod 9)
    7^2= 49= 4 (mod 9)
    8^2= 64= 1 (mod 9).

    There is no x such that [itex]x^2= 8= -1 (mod 9)[/itex].
     
  5. Sep 9, 2012 #4
    9 is not prime
     
  6. Sep 9, 2012 #5
    well, I give you a hint:

    [itex]-1 \equiv p-1[/itex] (mod p)

    [itex]-2 \equiv p-2[/itex] (mod p)

    now, what is [itex]\frac{p-1}{2}[/itex] congruent to?

    Also, pay attention to the fact that if p is of the form 4k+1 (i.e [itex] p \equiv 1[/itex] (mod 4) ), then [itex]\frac{p-1}{2}[/itex] is even.

    Another thing that you need to remember is that [itex]x^2 \equiv 1[/itex] (mod p) has two solutions, namely 1 and -1 (or p-1 in other words). That means there are exactly two numbers that are their own inverses modulo p and since p is a prime number any integer numbers modulo p has inverses (except multiples of p that are congruent to 0).

    See if you could figure out how you should prove it now.
     
    Last edited: Sep 9, 2012
  7. Sep 9, 2012 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Ouch! I knew that! :redface:
     
  8. Sep 9, 2012 #7
    In class we haven't touched on how modulus works with rational numbers. Although I know (p-1)/2 is an integer, I want to use properties of modulus to say that
    [itex]-1 \equiv (p-1)/2[/itex] (mod p) - but I don't think I can do that "legally" unless I can say [itex]1/2 \equiv 1/2[/itex] (mod p).

    I wrote out a few examples and I think I can see what a previous poster means by "cancelling (p-1)/2 terms," but not really. Suppose p = 13. Then I want to show

    12*11*10*9*8*7*6*5*4*3*2*1 "=" (6*5*4*3*2*1)2

    I can cancel one "set" of ((p-1)/2)! to get:

    12*11*10*9*8 "=" 6*5*4*3*2*1

    which isn't true working with integers, but working mod p it is true. That is

    12*11*10*9*8 [itex]\equiv[/itex] 6*5*4*3*2*1 (mod p)


    Generalizing to some prime p of the form 4k+1, I can see that

    (p-1)! [itex]\equiv[/itex] p-1 [itex]\equiv[/itex] -1 (mod p)

    So if I could prove ([itex]\frac{p-1}{2}[/itex] !)2 [itex]\equiv[/itex] -1 [itex]\equiv[/itex] p-1 (mod p) I'd be done.
     
    Last edited: Sep 9, 2012
  9. Sep 10, 2012 #8
    Ah! Figured it out!

    The breakthrough was realizing z = -(p-z) (mod p) for all z and the negatives canceling.

    Whew! Crazy stuff.

    Thanks all for contributing your time to help random people like me out. I'm sure it's a thankless job a lot of the time, but you all have helped me a lot in the past so cheers!
     
  10. Sep 10, 2012 #9
    Actually this is how it's going to get proved, I think you have done the same thing, maybe a little different:

    By Wilson's theorem we know that

    [itex] 1 \times 2 \times .... \times \frac{p-1}{2} \times \frac {p+1}{2} ... \times (p-2) \times (p-1) \equiv -1 [/itex] (mod p)

    By what I had shown before we have:
    [itex] p-1 \equiv -1 [/itex] (mod p)
    [itex] p-2 \equiv -2 [/itex] (mod p)
    .
    .
    .
    [itex] \frac{p+1}{2} \equiv p - \frac{p-1}{2} \equiv -\frac{p-1}{2} [/itex] (mod p)

    By rearranging we see:

    [itex] (-1)^{\frac{p-1}{2}} \times ( 1 \times 2 \times ... \times \frac{p-1}{2})^2 \equiv -1 [/itex] (mod p)

    but (p-1)/2 is even, therefore
    [itex]( 1 \times 2 \times ... \times \frac{p-1}{2})^2 \equiv -1 [/itex] (mod p)

    Now setting [itex]1 \times 2 \times ... \times \frac{p-1}{2} = (\frac{p-1}{2})! [/itex] (mod p), we see that x= [itex](\frac{p-1}{2})![/itex] is a solution.

    The converse holds as well, that means if [itex] x^2 \equiv -1 [/itex] (mod p) has a solution then p must be congruent to 1 modulo 4. The proof is easy and you could do it if you want.
     
    Last edited: Sep 10, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook