Results 1 to 3 of 3

Math Help - Trivial quadratic residues (mod p^k)?

  1. #1
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1

    Trivial quadratic residues (mod p^k)?

    Context: I am coding a solver (in Java) for generalized Pell equations of the form x^2 - Dy^2 = N using a paper of John Robertson as a reference. The Lagrange-Matthews-Mollin algorithm requires a complete solution set to the congruence z^2 \equiv D\ (mod\ |m|) for various m.

    So, I've handled factoring |m| into prime powers p^k and am OK with Tonelli Shanks and Hensel lifting when D \not \equiv 0\ (mod\ p), but I'm stuck on the supposedly trivial case D \equiv 0\ (mod\ p). Say for example we want to find all solutions to x^2 \equiv 98\ (mod\ 7^3). It is easy to check that the solutions are x \equiv 21, 28, 70, 77, 119, 126, 168, 175, 217, 224, 266, 273, 315, 322 (mod 7^3). I can see that the solution set is simply  x \equiv \pm 21\ (mod\ 49). Likewise, I have determined that the solution set to x^2 \equiv 98\ (mod\ 7^4) is x \equiv \pm 70\ (mod\ 7^3). What would be an efficient algorithm for the general case? And will prime p = 2 need to be treated separately from primes p > 2?

    I have limited number theory background, so I'm probably missing something basic. The literature I've consulted seems to pass off such problems as trivial or easy or irrelevant, leaving them as exercises to the reader, either explicitly or by omission.

    After I've completed this step, straightforward application of the Chinese Remainder Theorem will allow me to complete the overall problem.

    Any help would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by undefined View Post
    Context: I am coding a solver (in Java) for generalized Pell equations of the form x^2 - Dy^2 = N using a paper of John Robertson as a reference. The Lagrange-Matthews-Mollin algorithm requires a complete solution set to the congruence z^2 \equiv D\ (mod\ |m|) for various m.

    So, I've handled factoring |m| into prime powers p^k and am OK with Tonelli Shanks and Hensel lifting when D \not \equiv 0\ (mod\ p), but I'm stuck on the supposedly trivial case D \equiv 0\ (mod\ p). Say for example we want to find all solutions to x^2 \equiv 98\ (mod\ 7^3). It is easy to check that the solutions are x \equiv 21, 28, 70, 77, 119, 126, 168, 175, 217, 224, 266, 273, 315, 322 (mod 7^3). I can see that the solution set is simply  x \equiv \pm 21\ (mod\ 49). Likewise, I have determined that the solution set to x^2 \equiv 98\ (mod\ 7^4) is x \equiv \pm 70\ (mod\ 7^3). What would be an efficient algorithm for the general case? And will prime p = 2 need to be treated separately from primes p > 2?

    I have limited number theory background, so I'm probably missing something basic. The literature I've consulted seems to pass off such problems as trivial or easy or irrelevant, leaving them as exercises to the reader, either explicitly or by omission.

    After I've completed this step, straightforward application of the Chinese Remainder Theorem will allow me to complete the overall problem.

    Any help would be appreciated.

    I won't be able to offer full proofs here (lack of time ), but I'll offer you what I believe to be true. Oh yeah, I'm also assuming  p>2 .

    We want to solve  x^2\equiv D\mod{p^k} where  D\equiv0\mod{p} .

    Here's my take:
    Your solution will always be of the form  x\equiv\pm a\mod{p^{k-1}} (assuming a solution exists), where  a\equiv 0\mod{p} .

    Now what's the value of  a ?

    I claim  a is the smallest value in  \{0,1,2,\cdots,p^k-1\} that satisfies  x^2\equiv D\mod{p^k} .

    So to find  a , I would just make a loop to scan all multiples of  p , until (or if) you find your solution.

    Also note, if  a exists, it's guaranteed that  a\leq\frac{p^k-1}{2} .

    Disclaimer: I won't have the time to prove these assertions, and they come from observations made from numerous and diverse examples I tried. If anyone else sees something wrong here, please say so!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Thanks for taking the time to work on my problem! Your input was helpful and matched with my results on a similar line of thought. In case anyone is interested, there is some continuing discussion for this problem on another math forum I posted on. It seems there is a faster, more analytic approach. I hope it's not bad etiquette to link to another math forum; I imagine the community attitude is one of cooperation rather than competition. Thanks again!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sum of quadratic residues
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: February 11th 2011, 10:05 PM
  2. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 12th 2009, 09:42 AM
  3. Quadratic residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 17th 2009, 04:13 PM
  4. Quadratic Residues
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: May 6th 2007, 11:14 AM
  5. quadratic residues
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 13th 2006, 11:34 AM

Search Tags


/mathhelpforum @mathhelpforum