This has been studied a lot. You might look at "Integer Sequences having prescribed quadratic character" by D.H. and Emma Lehmer and Dan Shanks, in Math. Comp. vol 24, April 1970 (page 433---), in which they look at this from a computational point of view. If m,n are your two integer which have the same set of values for quadratic residues of a bunch primes, use quadratic reciprocity of the Jacobi symbol (assume, for convenience that m,n are odd): (m/p_i) = +/- (p_i/m) (where the sign comes from quadratic reciprocity). Then look at chi(r) = (r/m)*(r/n) (i.e the product of the two quadratic residue symbols. Your hypothesis is that chi(p_i) = 1 for all i. The conductor of this character is <= 4*m*n. The generalized RH says that if it's non-trivial (not identically 1) then there is an integer q <= C*log^2 (4*m*n), for some absolute constant C (I believe that Eric Bach showed that you can take C=2), so that chi(q) != 1. If you don't assume the generalized RH, the bound is something like C*sqrt(4*m*n) log(4*m*n). Victor On Mon, Sep 29, 2014 at 3:58 PM, Andy Latto <andy.latto@pobox.com> wrote:
The quadratic character of a wrt N depends only on the residue class of a mod N.
So if you know the residue class of a for a set of values N_i, the best you can do is reconstruct a up to a multiple of the lcm of the N_i.
Andy Latto andy.latto@gmail.com
On Mon, Sep 29, 2014 at 12:49 PM, Henry Baker <hbaker1@pipeline.com> wrote:
The following question occurred to me on a long bike ride (?!?) yesterday:
Suppose I know the quadratic character of a wrt N for lots of different N's.
Under what conditions can I reconstruct N ?
I.e., is there a "Chinese Remainder Theorem" for quadratic residues?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun