Re: Squares in AP's

Expand Messages
• ... 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
--- 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.