Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$?
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.
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.
