Calculating whether A is a quadratic residue mod N, N composite?

Question

I know the Jacobi symbol is typically all we can work with for composite N when attempting to discern whether a given residue A is a quadratic residue mod N.

However, what if we have a composite N with a special property (it will thus be a pseudoprime to base A): what if A^((N-1)/2) actually IS congruent to either 1 or -1 even though N is composite? Would this always be an accurate result for whether or not A is a quadratic residue mod N?

In other words, if A^((N-1)/2) mod N does equal 1, does that mean A is necessarily a quadratic residue mod N even for composite N? If it equals -1, does that mean A is necessarily a quadratic nonresidue mod N even for composite N?

cheeser: Thank you for providing the Euler-Jacobi pseudoprimes link.

My original question was equivalent to asking if any Euler-Jacobi pseudoprimes existed such that the relevant Jacobi symbol was 1, while the relevant residue was in fact a quadratic nonresidue. The answer is yes, and 561 is an example with respect to the residue 2.

Of course, a Jacobi symbol with value -1 always means that residue is definitely NOT a quadratic residue mod N, because it is a quadratic nonresidue with respect to at least one of the prime factors of N.

In conclusion, the calculation A^((N-1)/2) mod N indeed cannot be relied on to determine whether A is a quadratic nonresidue when N is composite.

Having understood that, I still wonder if there is any reliable way to get more information about a residue when its Jacobi symbol is positive 1.

Answer 1

I think you're confused:

http://en.wikipedia.org/wiki/Legendre_symbol
http://en.wikipedia.org/wiki/Euler%27s_criterion
http://en.wikipedia.org/wiki/Jacobi_symbol

The Jacobi symbol is what allows the Legendre symbol to be used in a way that makes sense for composite numbers. It's the way to do it. When I say the way, I really mean the way, not just a way. As far as I've ever seen, there aren't better ways to do it, unless the Jacobi symbol itself simplifies into something more sensible.

What you're hoping is that Euler's criterion holds for a composite modulus. This is not generally true, and when it is true, I believe what you're looking for is Euler-Jacobi pseudoprimes. See:
http://en.wikipedia.org/wiki/Euler-Jacobi_pseudoprime