Legendre Symbol (2/p)

  • Thread starter kingwinner
  • Start date
  • #1
1,270
0

Main Question or Discussion Point

"Let p be an odd prime, then we proved that the Legendre symbol
nt9.JPG


Note that this can be easily computed if p is reduced modulo 8.
For example, if p=59, then p3 (mod 8) and [tex](-1)^{(p^2-1)/8}[/tex] = [tex](-1)^{(3^2-1)/8}[/tex]" (quote from my textbook)
====================================

Now I don't exactly see WHY p can be reduced modulo 8 without changing the answer.
Why can we be so sure that [tex](59^2-1)/8[/tex] and [tex](3^2-1)/8[/tex] will have the same parity? How can we prove this?

Thanks for explaining!
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Why can we be so sure that [tex](59^2-1)/8[/tex] and [tex](3^2-1)/8[/tex] will have the same parity? How can we prove this?
Isn't parity just another word for looking at the number modulo 2?
 
  • #3
1,270
0
Yes, but my textbook says modulo 8 which I don't understand.

59≡3 (mod 2)
=> 592≡32 (mod 2)
=> 592-1 ≡ 32-1 (mod 2)
But the trouble here is that there is no rule saying that I can multiply both sides by 1/8 (since 1/8 is not an integer)
 
  • #4
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
But the trouble here is that there is no rule saying that I can multiply both sides by 1/8 (since 1/8 is not an integer)
That's right. But, still, there is a rule that deals with division....

By the way, it's the parity of (p2-1)/8, not the parity of p, so maybe you should start with that?
 
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Or, I suppose, you could start with p=q mod 8 and work from there.
 
  • #6
1,270
0
Sorry, I don't get it...

How should I begin?
 
  • #7
1,270
0
I guess I should look at two cases...(p2-1)/8 is even and the other case (p2-1)/8 is odd.

(2/p)=1
<=> (p2-1)/8 is even
<=> (p2-1)/8 = 2k
<=> p2= 16k + 1
<=> p2 ≡ 1 (mod 16)

<=> p ≡ ??? (mod 8) <-----------this is the step I'm stuck...

Can someone help me, please?
Thank you!
 
  • #8
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Can't you just try everything?
 
  • #9
1,270
0
How??? Can someone show me an example?

How do you go from mod 8 to mod 16??
 
  • #10
1,270
0
17eb39e435290b52c08e30078f40942d.png

To get the conrguence on the right hand side (i.e. precisely when (-1/p)=1), I will use the formula in the middle
(-1/p)=1 <=> (p-1)/2 is even <=> (p-1)/2 = 2k <=> p=1+4k <=> p≡1 (mod 4)

b84e4e92a3b8ac098c587cf814810b00.png

Following the same trick as above, to determine when (2/p)=1,
set [tex][(p^2 -1)/8][/tex] =2k
<=> [tex]p^2[/tex] = 16k +1
<=> [tex]p^2[/tex] ≡ 1 (mod 16)

<=> p ≡ ??? (mod 8) <-----I'm stuck on this step. Can someone explain how to go from the previous step to this step?

Thanks for any help!
 
Last edited:
  • #11
1,270
0
If we somehow already HAVE the answer on the right hand side, then it's easy to check that [tex]\frac{p^2-1}{8}[/tex] is odd for p = 3, 5 and it's even for p = 1, 7. But to do this, we actually need to know the correct answers in the first place.

b84e4e92a3b8ac098c587cf814810b00.png

But like in my textbook, it only proved the formula in the middle, without showing the conditions on the right, and I'm looking for a way to systematically derive the conditions on the right using the formula in the middle.

Also, why should the conditions be p≡ (mod 8)? Why not p≡ (mod 16)?? (as analogy, for (-1/p), the formula has 2 in the denominator of the exponent, and we get mod 4 on the right)
Having ONLY the formula in the middle, how to figure out what "modulus" to work with when we're trying to derive the conditions on the right?


Can someone explain this, please?
Thank you!
 
  • #12
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
Why not p≡ (mod 16)?
Do it for that then. What do you get?
 
  • #13
1,056
0
We know p is an odd prime so there are only four cases which can be placed in two catagories: [tex]\pm1+8k; \pm3+8k[/tex] Of course, in some cases k could be even and represent things like 1+32k, etc.

In the first case, squaring, subtracting off 1, and dividing by 8: [tex]\frac{\pm16k +64k^2}{8}}[/tex]

This gives an even result which goes for 8k+1 and 8k +7. The second situation is negative.

The factor 8 is introduced by use of a way to get the result. It comes from the sum formula for a product series of powers of -1: 1+2++++(p-1)/2 =(p-1)/2*(p+1)/2*1/2 =(p^2-1)/8. http://www.mathreference.com/num-mod,qr12.html

_In that case we arrive at 2^(p-1)/2 = (-1)^(p^2-1)/8. Since 2^(p-1)/2 can be only +/1, and all squares are +1--which is half the cases, we have our result.
 
Last edited:

Related Threads on Legendre Symbol (2/p)

  • Last Post
Replies
3
Views
8K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
7K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
7
Views
657
Replies
20
Views
9K
Replies
2
Views
4K
Replies
2
Views
2K
Top