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

[Heute]

Homework Statement

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

Homework Equations

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

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

x² = ( (\overline{1} )(\overline{2} )(\overline{3} )...(\overline{(p-1)/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

 

[susskind_leon]

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

 

[HallsofIvy]

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 x^2= 8= -1 (mod 9).

 

[susskind_leon]

9 is not prime

 

[Arian.D]

Homework Statement

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

Homework Equations

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

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

x² = ( (\overline{1} )(\overline{2} )(\overline{3} )...(\overline{(p-1)/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

well, I give you a hint:

-1 \equiv p-1 (mod p)

-2 \equiv p-2 (mod p)

now, what is \frac{p-1}{2} congruent to?

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

Another thing that you need to remember is that x^2 \equiv 1 (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.

 

[HallsofIvy]

9 is not prime

Ouch! I knew that!

 

[Heute]

well, I give you a hint:

-1 \equiv p-1 (mod p)

-2 \equiv p-2 (mod p)

now, what is \frac{p-1}{2} congruent to?

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

Another thing that you need to remember is that x^2 \equiv 1 (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.

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
-1 \equiv (p-1)/2 (mod p) - but I don't think I can do that "legally" unless I can say 1/2 \equiv 1/2 (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)²

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 \equiv 6*5*4*3*2*1 (mod p)


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

(p-1)! \equiv p-1 \equiv -1 (mod p)

So if I could prove (\frac{p-1}{2} !)² \equiv -1 \equiv p-1 (mod p) I'd be done.

 

[Heute]

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!

 

[Arian.D]

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!

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

1 \times 2 \times ... \times \frac{p-1}{2} \times \frac {p+1}{2} ... \times (p-2) \times (p-1) \equiv -1 (mod p)

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

By rearranging we see:

(-1)^{\frac{p-1}{2}} \times ( 1 \times 2 \times ... \times \frac{p-1}{2})^2 \equiv -1 (mod p)

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

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

The converse holds as well, that means if x^2 \equiv -1 (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.