Finding Formula for Number of QN*QN Pairs Between 1 and p-1

  • Thread starter Ad Infinitum NAU
  • Start date
  • Tags
    Formula
In summary, Casey is looking for a formula to find the number of pairs of QN*QN between 1 and p-1, using a specific sum involving Legendre symbols. They also mention knowing that the number of pairs of quadratic residues (QRQR) is equal to (1/4)*[p-4-(-1/p)]. They are seeking help and clarification on this problem and provide additional details and equations to explain their thought process.
  • #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
 
Mathematics news on Phys.org
  • #2
This will never get answered in Homework Help.

Off to Math with ye.

*kick*
 
  • #3
Refresh my memory, what do QN and QR mean?

Hurkyl
 
  • #4
Thanks for the kick Tom..
Hurkyl,
QR represents squares mod p, QN represents non-squares mod p.
 
  • #5
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
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
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
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
 

1. What is the purpose of finding a formula for the number of QN*QN pairs between 1 and p-1?

The purpose of finding this formula is to determine the total number of possible pairs of numbers that have a product less than the given prime number, p. This information can be useful in various mathematical and scientific applications, such as in number theory and cryptography.

2. How is the formula for the number of QN*QN pairs derived?

The formula for the number of QN*QN pairs is derived using number theory and combinatorics principles. It involves finding all the possible pairs of numbers that have a product less than p and then counting them.

3. Can the formula be applied to any prime number, p?

Yes, the formula can be applied to any prime number, p. It is a general formula that works for any given prime number and can be used to find the total number of QN*QN pairs between 1 and p-1.

4. Are there any limitations to the formula?

There are some limitations to the formula. It assumes that all numbers between 1 and p-1 are possible pairs, which may not always be the case. Additionally, the formula does not take into account any special properties of p that may affect the number of QN*QN pairs.

5. How can the formula be useful in real-world applications?

The formula for the number of QN*QN pairs can be useful in various real-world applications, such as in cryptography, where it can be used to determine the number of possible keys for a given encryption algorithm. It can also be used in number theory to study the distribution of prime numbers and in other mathematical problems that involve finding the total number of possible pairs of numbers.

Similar threads

Replies
2
Views
237
Replies
2
Views
790
Replies
1
Views
1K
Replies
1
Views
2K
Replies
4
Views
400
Replies
20
Views
1K
Replies
7
Views
1K
Replies
2
Views
1K
Replies
2
Views
614
Replies
3
Views
252
Back
Top