Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Number of Solutions to d(p)

  1. Aug 29, 2009 #1
    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?
  2. jcsd
  3. Aug 29, 2009 #2
    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, ...
  4. Aug 29, 2009 #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.
    Last edited: Aug 29, 2009
  5. Aug 29, 2009 #4
    I am an idiot.
    Hint: quadratic residue
  6. Aug 29, 2009 #5
    I still don't understand what you are asking.
    Let p be a prime number. Define d(p) as the cardinality of

    \{ (N,n) : N \ge 1, n \ge 1, N \ge n, N \equiv n^2 \pmod p \}

    Clearly you intend something different.
  7. Aug 29, 2009 #6
    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?
    Last edited: Aug 29, 2009
  8. Aug 29, 2009 #7
    Let p be a prime number. Define d(p) as:

    \max_{N \ge 1} \left| \{ n \pmod p : N \equiv n^2 \pmod p \} \right|

    Then d(2) = 1, d(p) = 2 for odd primes p.
  9. Aug 31, 2009 #8
    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
  10. Aug 31, 2009 #9
    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.
  11. Aug 31, 2009 #10
    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
  12. Aug 31, 2009 #11
    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
  13. Sep 7, 2009 #12
    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.
  14. Sep 8, 2009 #13


    User Avatar
    Science Advisor
    Homework Helper

    Is m fixed or can it take any integer value? Are there any limits on the value of n or m?
  15. Sep 8, 2009 #14
    There are no limits on the value of n or m. Nice to see you on the forums, by the way Charles!
  16. Sep 9, 2009 #15


    User Avatar
    Science Advisor
    Homework Helper

    So there are, trivially, infinitely many solutions.

    You too.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook