Re: Squares in AP's
- --- In primenumbers@y..., "jbrennen" <jack@b...> wrote:
>I was wondering after I wrote this, and thought maybe somebody
> 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.
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
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?