Number Theory

  • #1
Ad Infinitum NAU
44
0
I'm stumped as to how to find a formula for the number of pairs QN*QN between 1 and p-1. I must use the following as the base...

[sum]x=0 to x=p-1 of [1+(x/p)]*[1+((k-x)/p)] where the (x/p) and ((k-x)/p) terms are legendre symbols.

I also know (and can use) the fact that the number of pairs of QR (QRQR) = (1/4)*[p-4-(-1/p)] where again, (-1/p) is a legendre symbol.

Any help is greatly appreciated!

Casey
 

Answers and Replies

  • #2
quantumdude
Staff Emeritus
Science Advisor
Gold Member
5,575
23
This will never get answered in Homework Help.

Off to Math with ye.

*kick*
 
  • #3
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
Refresh my memory, what do QN and QR mean?

Hurkyl
 
  • #4
Ad Infinitum NAU
44
0
Thanks for the kick Tom..
Hurkyl,
QR represents squares mod p, QN represents non-squares mod p.
 
  • #5
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
I guess I should ask what "pairs" you're looking for as well; I presume you're not simply just looking for the number of ways to choose 2 elements out of QN.
 
Last edited:
  • #6
Ad Infinitum NAU
44
0
Say I wrote out the numbers from 1 to p, and I underline the numbers that are QN to p. There will be "pairs" so to speak of QN within this group. By pairs I simply mean two QN lying next to each other.
 
  • #7
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
Aha, ok the question makes sense now.

My initial thoughts on how to solve the problem appear totally different than what you say is required. (basically a counting argument using the list of numbers 1 to p - 1)

One last question on the problem (I hope); what is k?

I was trying to figure out what the sum means; I can see how you could compute the number of pairs with the sum:

&Sigmax = 1 .. p - 2 (1 - (x \ p)) (1 - (x + 1 \ p)) / 4

(Where I've used the backslash to represent the Legendre symbol)

Whereas that sum you say must be used in your solution seems to be counting the number of x's such that both x and k - x are quadratic residues. It's not clear to me how that could be useful.
 
  • #8
Ad Infinitum NAU
44
0
1. k is the constant used in the sum of (x(x^2+k)\p), where the x's are summed. (to find S(k)). I ran through it once more after a day of not thinking about it and wound up with the number of pairs of QN in p = (1/4)*(p-2+(-1\p))...

I found this by using (1/4)*sum of x from 0 to p-2 of..
((1-(x\p))*(1-((x+1)\p)-(1-(0\p))*(1-(1\p))-(1-(-1\p))*(1-(p\p))

and just running this through, cancelling and wound up with the above eqn. I'm pretty sure this is right, appreciate a verification if you could. Thanks for all the help!
casey
 

Suggested for: Number Theory

Replies
1
Views
984
  • Last Post
Replies
1
Views
422
  • Last Post
Replies
1
Views
597
Replies
9
Views
463
  • Last Post
Replies
1
Views
508
Replies
1
Views
554
  • Last Post
Replies
4
Views
717
  • Last Post
Replies
1
Views
784
Replies
3
Views
535
Replies
1
Views
541
Top