1. ## Trivial quadratic residues (mod p^k)?

Context: I am coding a solver (in Java) for generalized Pell equations of the form $\displaystyle 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 $\displaystyle z^2 \equiv D\ (mod\ |m|)$ for various m.

So, I've handled factoring |m| into prime powers $\displaystyle p^k$ and am OK with Tonelli Shanks and Hensel lifting when $\displaystyle D \not \equiv 0\ (mod\ p)$, but I'm stuck on the supposedly trivial case $\displaystyle D \equiv 0\ (mod\ p)$. Say for example we want to find all solutions to $\displaystyle x^2 \equiv 98\ (mod\ 7^3)$. It is easy to check that the solutions are x $\displaystyle \equiv$ 21, 28, 70, 77, 119, 126, 168, 175, 217, 224, 266, 273, 315, 322 (mod $\displaystyle 7^3$). I can see that the solution set is simply $\displaystyle x \equiv \pm 21\ (mod\ 49)$. Likewise, I have determined that the solution set to $\displaystyle x^2 \equiv 98\ (mod\ 7^4)$ is $\displaystyle 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.

2. Originally Posted by undefined
Context: I am coding a solver (in Java) for generalized Pell equations of the form $\displaystyle 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 $\displaystyle z^2 \equiv D\ (mod\ |m|)$ for various m.

So, I've handled factoring |m| into prime powers $\displaystyle p^k$ and am OK with Tonelli Shanks and Hensel lifting when $\displaystyle D \not \equiv 0\ (mod\ p)$, but I'm stuck on the supposedly trivial case $\displaystyle D \equiv 0\ (mod\ p)$. Say for example we want to find all solutions to $\displaystyle x^2 \equiv 98\ (mod\ 7^3)$. It is easy to check that the solutions are x $\displaystyle \equiv$ 21, 28, 70, 77, 119, 126, 168, 175, 217, 224, 266, 273, 315, 322 (mod $\displaystyle 7^3$). I can see that the solution set is simply $\displaystyle x \equiv \pm 21\ (mod\ 49)$. Likewise, I have determined that the solution set to $\displaystyle x^2 \equiv 98\ (mod\ 7^4)$ is $\displaystyle 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 $\displaystyle p>2$.

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

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

Now what's the value of $\displaystyle a$?

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

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

Also note, if $\displaystyle a$ exists, it's guaranteed that $\displaystyle 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!

3. 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!