My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum

LinkBack Thread Tools Display Modes
March 30th, 2010, 03:14 PM   #1
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 Lagrange-Matthews-Mollin 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.
undefined is offline  
March 31st, 2010, 08:20 AM   #2
Global Moderator
CRGreathouse's Avatar
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.
CRGreathouse is offline  
April 1st, 2010, 10:21 PM   #3
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.
undefined is offline  

  My Math Forum > College Math Forum > Number Theory

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

Copyright © 2019 My Math Forum. All rights reserved.