Loading ...
Sorry, an error occurred while loading the content.

Re: Squares in AP's

Expand Messages
  • jbrennen
    ... I was wondering after I wrote this, and thought maybe somebody would have an answer, or maybe I m just crazy... Assume we have a large odd composite number
    Message 1 of 4 , Oct 1, 2002
    • 0 Attachment
      --- In primenumbers@y..., "jbrennen" <jack@b...> wrote:
      >
      > Go study the Jacobi / Legendre / Kronecker symbol, and the
      > law of quadratic reciprocity. You will be able to answer this
      > question for any arithmetic progression ak+b for which you can
      > factor a, and for many such progressions where you can't factor a.

      I was wondering after I wrote this, and thought maybe somebody
      would have an answer, or maybe I'm just crazy...

      Assume we have a large odd composite number N, of which no factors
      are known. Also assume that for some number M which is *not* a
      quadratic residue modulo N, we have kronecker(M,N) == 1.

      Is it ever possible to *prove* that M is a quadratic non-residue
      (modulo N) without knowing any factors of N? (Note that a
      "brute force" proof is excluded, because if we have enough
      computing power to prove M a non-residue through brute force,
      we have enough computing power to factor N...) If such a
      proof might be possible, under what circumstances would it
      be possible?

      For instance, if we have M=2, N=8k+/-1, proving that M is
      a non-residue requires proving that N has a prime factor of
      the form 8k+/-3. Is that ever possible without explicitly
      finding a factor? If so, what kind of special form must
      the number N have?
    Your message has been successfully submitted and would be delivered to recipients shortly.