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

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

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

## Answers and Replies

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
Science Advisor
Homework Helper
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)$.

9 is not prime

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

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

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:
HallsofIvy
Science Advisor
Homework Helper
9 is not prime
Ouch! I knew that! 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)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:
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!

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.

Last edited: