Is quadratic reciprocity problem in coNP? Quadratic reciprocity is in $\mathsf{NP}$, since to prove $x$ is quadratic residue you can show $y$ such that $y^2=x$.
Wikipedia claims the problem is in $\mathsf{coNP}$. This book claims it is not known. Is it?
It seems at:


*

*When $n$ is prime, one can use Euler's criterion so the problem is in $\mathsf{P}$,

*In general case one can give factorization of $n$ and reduce the problem to $n=p^k$.


Am I correct?
 A: I think you are correct. 
First of all, the prover can provide the prime factorization of $n$, so without loss of generality assume $n = p^k$ for some $k$. We have thus reduced the problem to the prime powers. 
I am taking the following sets of rules for determining if a number is a quadratic residue or not modulo $p^k$ from this wikipedia page. Be careful in reading the wikipedia page since it uses a different notation than in the question. 

If the modulus is $p^k$, then $p^x A$
  
  
*
  
*is a residue modulo $p^k$ if $x \geq k$
  
*is a nonresidue modulo $p^k$ if $x < k$ is odd
  
*is a residue modulo $p^k$ if $x < k$ is even and $A$ is a residue modulo $p$
  
*is a nonresidue modulo $p^k$ if $x < k$ is even and $A$ is a nonresidue modulo $p$.
  

And for $p=2$:

All odd squares are $\equiv 1 \pmod 8$ and a fortiori $\equiv 1 \pmod 4$. If $a$ is an odd number and $m = 8, 16$, or some higher power of $2$, then $a$ is a residue modulo $m$ if and only if $a \equiv 1 \pmod 8$. 
So a nonzero number is a residue modulo $8, 16$, etc., if and only if it is of the form $4^x(8y + 1)$. 

So we are finally reduced to the case of checking whether a given number is a quadratic residue or nonresidue modulo a prime $p$. But as the OP notes, that can be easily done in deterministic polynomial time using Euler's criterion. 
