Quadratic Reciprocity I've been asked to see if $x^2\equiv83$ $\pmod{101^{2000}}$ has solutions. Now I know $x^2\equiv83\pmod{101}$ has no solutions since the quadratic reside symbol $(\frac{83}{101})=-1$ using the quadratic reciprocity law. So by the Chinese Remainder Theorem, does this mean the former congruence has no solutions?
Similarly does $x^2\equiv83$ $\pmod{29^{2000}}$ have solutions since $(\frac{83}{29})=1$?
 A: The Chinese remainder theorem states that if $m,n$ are coprime integers, then the congruence 
$$y \equiv a \pmod m\\ y\equiv b \pmod n$$
has a unique solution mod $mn$. Since you don't have the coprimality condition, you can't quote the Chinese remainder theorem.
However, the converse to the Chinese remainder theorem is true even if $m,n$ are not coprime: for any integers $m,n$
$$y\equiv a \pmod {mn} \implies \begin{split}y\equiv a \pmod n\\ y\equiv a \pmod m\end{split}$$
You can use this for the first part.

For the second part, you have to be more careful. For example, $x^2\equiv -1 \pmod 2$ has solutions, but $x^2\equiv -1\pmod 4$ does not. (In fact this is a demonstration of why you need the coprimality condition to use the Chinese remainder theorem).
For the second part, you can use Hensel's lemma to show that a solution exists.
A: For the first one, yes. If $x^2 \equiv 83 \mod 101^{2000}$, then $x^2=101^{2000}k+83=101l+83$, thus $x^2 \equiv 83 \mod 101$. But the latter has no solutions, so the former has no solutions.
For the second one, no, not necessarily.
