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

1. Sep 8, 2012

### Heute

1. The problem statement, all variables and given/known data

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

2. Relevant 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}$ )

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 = ( ($\overline{1}$ )($\overline{2}$ )($\overline{3}$ )...($\overline{(p-1)/2}$ ) )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. Sep 9, 2012

### 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

3. Sep 9, 2012

### HallsofIvy

Staff Emeritus
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)$.

4. Sep 9, 2012

### susskind_leon

9 is not prime

5. Sep 9, 2012

### Arian.D

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.

Last edited: Sep 9, 2012
6. Sep 9, 2012

### HallsofIvy

Staff Emeritus
Ouch! I knew that!

7. Sep 9, 2012

### Heute

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)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 $\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}$ !)2 $\equiv$ -1 $\equiv$ p-1 (mod p) I'd be done.

Last edited: Sep 9, 2012
8. Sep 10, 2012

### 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!

9. Sep 10, 2012

### Arian.D

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.

Last edited: Sep 10, 2012