I've been asked to see if $x^2\equiv83$ $(\mathrm {mod} \ 101^{2000})$ has solutions. Now I know $x^2\equiv(\mathrm{mod} \ 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$ $(\mathrm {mod} \ 29^{2000})$ have solutions since $(\frac{83}{29})=1$?

• correct. Use Chinese Remainder. – user237393 May 5 '15 at 10:56

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.

• Thank you very much. Now makes more sense of when I can apply CRT and when its not relevant. How would I go about justifying the second case has solutions or not? I can't think of anything other than the CRT. – Vladimir Nabokov May 5 '15 at 11:16
• Have you covered Hensel's Lemma? – Mathmo123 May 5 '15 at 11:16
• I'm going to revise it later today. But I haven't been asked to find solutions, just to justify it. – Vladimir Nabokov May 5 '15 at 11:20
• Hensel's Lemma does exactly that. It tells you that a solution exists, without needing to calculate it. – Mathmo123 May 5 '15 at 11:21
• Just to clarify: Since 29 doesn't divide 2(83) and $(\frac{83}{29})=1$ we have by a corollary of Hensel's Lemma that $x^2\equiv83(mod \ p^n)$ has solutions for any $n\in \Bbb N$ – Vladimir Nabokov May 5 '15 at 13:10

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.

• So how can I prove that the second has one has solutions or not? Why can't I use what you just said for it? – Vladimir Nabokov May 5 '15 at 11:03
• @VladimirNabokov Mathmo123 gives a nice counterexample. – wythagoras May 5 '15 at 11:13