From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math.num-analysis Subject: Re: Feeling stupid Date: 24 May 1997 06:15:47 GMT In article , Dan S. Camper wrote: >Given a positive integer j, find four positive integers (a, b, c d) that >satisfy the following equations: > > 1) a < b < c < d > 2) a + d + 1 = j > 3) b + c = j > 4) ad/j = (a positive integer) > 5) (bc+1)/j = (a positive integer) > 6) 2a + 1 = c > 7) a + b = d Three of the equations define b, c, d in terms of a; then the others are redundant except for (1) and (8) a^2 = -a mod j. You get all the solutions by solving (8) mod j and rejecting solutions not satisfying (j-2)/4 < a < (j-2)/3. Equation (8) clearly has solutions a=0 and a=-1 mod j (i.e., a=j-1). These don't satisfy your inequalities, but your ability to find other solutions depends on your ability to factor j so I hope j isn't too big. If you know j is a product of relatively prime integers P1, P2, ... then you can find more solutions a by using the Chinese remainder theorem to find numbers a congruent to 0 modulo some of the P_i and congruent to -1 modulo the others. If the P_i are each a power of a prime, these are the only solutions. (Your examples had j=21=3*7 and j=8383=83*101. The listed choices of a had in the first case a=0 mod 3 and a=-1 mod 7; in the second case a=0 mod 101 and a=-1 mod 83.) You had better be sure that the guarantee given (that there is a solution) is correct, since for some j (e.g. j= a prime) there is no a with a^2=-a in the given interval, and thus no solution to (1)-(7). I see no reason the solution should be unique, either; if j has n distinct prime divisors, then there are 2^n solutions to (8) (mod j); it certainly seems possible to have more than one of those lie in the interval ( (j-2)/4, (j-2)/3 ). But then again I also wouldn't be surprised to see someone prove the solution _must be_ unique. dave