On Fri, May 25, 2012 at 3:24 AM, Dan Asimov <dasimov@earthlink.net> wrote:
I recently needed to solve a problem of the form below.
Problem: Let K, 0 <= K < 100, be an integer constant. Find solutions (x,N) in (Z+)^2 satisfying the equation:
(*) K*x + 1 = N^2
Write this as K*x = (N-1)(N+1). If K is a prime power, say p^m, with p > 2, then p divides at most one of N-1 and N+1, so the solutions are given by the N congruent to either K+1 or K-1 mod p^m. For p = 2, since 2 can divide both N-1 and N+1, but one of them only once, there are the additional solutions where N is congruent to 2^(m-1) +1 and 2^(m-1) - 1 mod K if m >= 3. Using the Chinese remainder theorem gives the solution for general K. So if K is the product of 2^m and r distinct odd primse, there are 2^r solutions if m = 0 or 1, 2^(r+1) solutions if m = 2, and 2^(r+2) solutions if m >= 3, where in all cases this is the number of values of N mod K that occur in solution pairs (N, x). Andy