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

  • Thread starter Heute
  • Start date
  • Tags
    Prime
In summary: By multiplying these congruences we get:1 \times 2 \times ... \times \frac{p-1}{2} \times \frac {p+1}{2} ... \times (p-2) \times (p-1) \equiv (\frac {p-1}{2} !)^2 \equiv (-1)^{\frac{p-1}{2}} (mod p) Looks like it's solved, right? But wait! What if p-1 is odd? We don't know if (-1)^{\frac{p-1}{
  • #1
Heute
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
 
Physics news on Phys.org
  • #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
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].
 
  • #4
9 is not prime
 
  • #5
Heute said:

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:
  • #6
susskind_leon said:
9 is not prime
Ouch! I knew that! :redface:
 
  • #7
Arian.D said:
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
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
Heute said:
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:

1. How can you prove that p is prime?

In order to prove that p is prime, we must show that it has exactly two divisors, 1 and itself. This can be done through various methods such as trial division or using the Sieve of Eratosthenes.

2. What does it mean for p to equal 1 (mod 4)?

When we say p = 1 (mod 4), it means that p leaves a remainder of 1 when divided by 4. In other words, p is one more than a multiple of 4.

3. How can we show that x^2 = -1 (mod p) has a solution?

To show that x^2 = -1 (mod p) has a solution, we can use the fact that p is prime and p = 1 (mod 4). This means that p can be written as p = 4k + 1, where k is a positive integer. By substituting this into the equation, we get x^2 = -1 (mod 4k + 1), which can be solved using modular arithmetic.

4. Can you provide an example to illustrate this statement?

One example that satisfies the statement is p = 5. 5 is a prime number and 5 = 1 (mod 4). When we substitute p = 5 into the equation, we get x^2 = -1 (mod 5), which has a solution of x = 2.

5. Why is it important to prove that this statement is true?

This statement is important because it helps us understand the relationship between primes and solutions to certain equations. It also has applications in cryptography and number theory. By proving this statement, we can gain a deeper understanding of prime numbers and their properties.

Similar threads

  • Calculus and Beyond Homework Help
Replies
15
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
692
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
2K
  • Calculus and Beyond Homework Help
Replies
15
Views
3K
  • Calculus and Beyond Homework Help
Replies
4
Views
929
  • Calculus and Beyond Homework Help
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
Back
Top