
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
March 30th, 2010, 03:14 PM  #1 
Newbie Joined: Mar 2010 Posts: 2 Thanks: 0  Trivial quadratic residues for prime powers
(For convenience, "=" means congruent and "!=" means not congruent when followed by (mod m). If anyone can tell me how to type the actual symbols, please do so as this is my first time posting on this forum.) 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 LagrangeMatthewsMollin algorithm requires a complete solution set to the congruence z^2 = 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 != 0 (mod p), but I'm stuck on the supposedly trivial case D = 0 (mod p). Say for example we want to find all solutions to x^2 = 98 (mod 7^3). It is easy to check that the solutions are x = 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 = +21 (mod 49). Likewise, I have determined that the solution set to x^2 = 98 (mod 7^4) is x = +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. 
March 31st, 2010, 08:20 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Trivial quadratic residues for prime powers
So you want to solve with gcd(n, p) = 1. (You can of course solve mod each of the prime powers of m and CRT them together to get a solution for mod m rather than just mod p^b.) If a >= b, then of course and so the possibilities for z are just multiples of . If a < b and a is odd, then there are no solutions. If a < b and a is even, then with k and p coprime. You should be able to find solutions to and multiply them by . In your example, , solve and multiply the solution by 7. I've not worked with this before, but this seems to work. Let me know if you get your program finished, I'd be curious to see the result. 
April 1st, 2010, 10:21 PM  #3 
Newbie Joined: Mar 2010 Posts: 2 Thanks: 0  Re: Trivial quadratic residues for prime powers
Thank you! I was looking for an analytic approach like the one you presented. After reading your post, it seems very natural to have broken the problem down the way you did, and only the last part struck me as being potentially tricky to come up with. As a novice, I experience many "Why didn't I think of that?" moments. I have not implemented your method yet, as I have some other more pressing projects, but when I find time to complete everything I will post my code.


Tags 
powers, prime, quadratic, residues, trivial 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
residues and non residues of general quadratic congruences  smslca  Number Theory  5  October 12th, 2012 09:48 AM 
fpt problem in quadratic residues  smslca  Number Theory  0  October 12th, 2012 01:34 AM 
quadratic residues with primes  slippy  Number Theory  7  October 26th, 2009 02:40 PM 
how often is the sum of successive powers of (2)+1 prime?  soandos  Number Theory  12  December 5th, 2007 09:26 PM 
Prime Powers  MutenRo  Number Theory  12  September 30th, 2007 12:13 PM 