Number of Solutions to d(p)


by flouran
Tags: cardinality, primes, solutions
flouran
flouran is offline
#1
Aug29-09, 12:40 PM
P: 64
What is the number of solutions d(p) of
[tex]N-n^2 \equiv 0 \pmod p[/tex]

where p is a prime and n and N are positive and N => n?
Phys.Org News Partner Science news on Phys.org
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
JustSam
JustSam is offline
#2
Aug29-09, 01:37 PM
P: 21
I'm not sure what you are really asking, but for each prime p, there are an infinite number of solutions (N,n) satisfying your criteria. Take n = 1, and N= k*p + 1, for k = 1, 2, 3, ...
flouran
flouran is offline
#3
Aug29-09, 01:39 PM
P: 64
Quote Quote by JustSam View Post
I'm not sure what you are really asking, but for each prime p, there are an infinite number of solutions (N,n) satisfying your criteria. Take n = 1, and N= k*p + 1, for k = 1, 2, 3, ...
I have a trivial upper bound for d(p). That is, d(p) < p-1 for [tex]p\nmid N[/tex]. I think that suffices for my usages of d(p) for now.

flouran
flouran is offline
#4
Aug29-09, 04:06 PM
P: 64

Number of Solutions to d(p)


I am an idiot.
Hint: quadratic residue
JustSam
JustSam is offline
#5
Aug29-09, 05:24 PM
P: 21
I still don't understand what you are asking.
Quote Quote by flouran View Post
What is the number of solutions d(p) of
[tex]N-n^2 \equiv 0 \pmod p[/tex]

where p is a prime and n and N are positive and N => n?
Let p be a prime number. Define d(p) as the cardinality of

[tex]$
\{ (N,n) : N \ge 1, n \ge 1, N \ge n, N \equiv n^2 \pmod p \}
[/tex]

Clearly you intend something different.
flouran
flouran is offline
#6
Aug29-09, 07:28 PM
P: 64
Quote Quote by JustSam View Post
I still don't understand what you are asking.

Let p be a prime number. Define d(p) as the cardinality of

[tex]$
\{ (N,n) : N \ge 1, n \ge 1, N \ge n, N \equiv n^2 \pmod p \}
[/tex]

Clearly you intend something different.
I can be clearer:
Let F(n) be a polynomial of degree g => 1 with integer coefficients. Let d(p) denote the number of solutions to the congruency [tex]F(n) \equiv 0 \pmod p[/tex] for all primes p (and suppose that d(p) < p for all p). We may take F(n) = N-n^2, where N is an integer greater than (or equal to) n. What is d(p) then in this case?
JustSam
JustSam is offline
#7
Aug29-09, 07:46 PM
P: 21
Quote Quote by flouran View Post
I can be clearer:
Let F(n) be a polynomial of degree g => 1 with integer coefficients. Let d(p) denote the number of solutions to the congruency [tex]F(n) \equiv 0 \pmod p[/tex] for all primes p (and suppose that d(p) < p for all p). We may take F(n) = N-n^2, where N is an integer greater than (or equal to) n. What is d(p) then in this case?
Let p be a prime number. Define d(p) as:

[tex]$
\max_{N \ge 1} \left| \{ n \pmod p : N \equiv n^2 \pmod p \} \right|
[/tex]

Then d(2) = 1, d(p) = 2 for odd primes p.
srijithju
srijithju is offline
#8
Aug31-09, 01:46 PM
P: 57
Quote Quote by JustSam View Post
Let p be a prime number. Define d(p) as:

[tex]$
\max_{N \ge 1} \left| \{ n \pmod p : N \equiv n^2 \pmod p \} \right|
[/tex]

Then d(2) = 1, d(p) = 2 for odd primes p.
I dont think this is the right solution . Consider p = 3 and N = 2. We know that no square number is congruent to 2 modulo 3. So in this case d(3) = 0
JustSam
JustSam is offline
#9
Aug31-09, 01:57 PM
P: 21
Quote Quote by srijithju View Post
I dont think this is the right solution . Consider p = 3 and N = 2. We know that no square number is congruent to 2 modulo 3. So in this case d(3) = 0
Which is why it is important to have a precise definition of d(p). According to my second version, d(p) is the maximum number of solutions over all possible choices for N, so it makes sense that you can find particular values of N that have fewer than d(p) solutions.

Perhaps "d(p,N) = exact number of solutions" would be a more useful function.
srijithju
srijithju is offline
#10
Aug31-09, 01:59 PM
P: 57
I think you mean that N is fixed , but

If the question is :
Find all N < p such that n^2 = N ( mod p) for some n ( By some n , I mean that corresponding to each N there will be one n) , then :

d(p) = greatest integer less than square root of p
srijithju
srijithju is offline
#11
Aug31-09, 02:11 PM
P: 57
Quote Quote by JustSam View Post
Which is why it is important to have a precise definition of d(p). According to my second version, d(p) is the maximum number of solutions over all possible choices for N, so it makes sense that you can find particular values of N that have fewer than d(p) solutions.

Perhaps "d(p,N) = exact number of solutions" would be a more useful function.
Considering d(p,N) :

take remainder of N divided by p . Let it be r.
Now if r is a perfect square , then d(p.N) will have infinite solutions of the form r + kp
else there is no solution
flouran
flouran is offline
#12
Sep7-09, 06:43 PM
P: 64
Would d(p) be different if it was instead the number of solutions to:
[tex]F(n) \equiv 0 \pmod p[/tex]? Here F(n) = n - q where q = m^2 is a perfect square where m is a natural number.
CRGreathouse
CRGreathouse is offline
#13
Sep8-09, 04:56 PM
Sci Advisor
HW Helper
P: 3,680
Is m fixed or can it take any integer value? Are there any limits on the value of n or m?
flouran
flouran is offline
#14
Sep8-09, 05:43 PM
P: 64
Quote Quote by CRGreathouse View Post
Is m fixed or can it take any integer value? Are there any limits on the value of n or m?
There are no limits on the value of n or m. Nice to see you on the forums, by the way Charles!
CRGreathouse
CRGreathouse is offline
#15
Sep9-09, 02:07 PM
Sci Advisor
HW Helper
P: 3,680
Quote Quote by flouran View Post
Would d(p) be different if it was instead the number of solutions to:
[tex]F(n) \equiv 0 \pmod p[/tex]? Here F(n) = n - q where q = m^2 is a perfect square where m is a natural number.
Quote Quote by flouran View Post
There are no limits on the value of n or m.
So there are, trivially, infinitely many solutions.

Quote Quote by flouran View Post
Nice to see you on the forums, by the way Charles!
You too.


Register to reply

Related Discussions
Number of solutions to summation General Math 3
number of solutions General Math 2
Number of solutions to complex eq. Calculus & Beyond Homework 9
Find Solutions- Number Theory Linear & Abstract Algebra 10
Count the number of integer solutions Calculus 1