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

  • Thread starter Heute
  • Start date
  • #1
25
0

Homework Statement



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).

Homework 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] )

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
 

Answers and Replies

  • #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
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,833
963
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
101
0

Homework Statement



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).

Homework 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] )

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

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:
  • #7
25
0
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.

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:
  • #8
25
0
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!
 
  • #9
101
0
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

[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:

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

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
7
Views
2K
Replies
3
Views
2K
Replies
16
Views
831
Replies
19
Views
7K
Replies
2
Views
673
  • Last Post
Replies
3
Views
1K
Top