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$?

  • $\begingroup$ correct. Use Chinese Remainder. $\endgroup$
    – user237393
    Commented May 5, 2015 at 10:56

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$ Commented May 5, 2015 at 11:16
  • $\begingroup$ Have you covered Hensel's Lemma? $\endgroup$
    – Mathmo123
    Commented May 5, 2015 at 11:16
  • $\begingroup$ I'm going to revise it later today. But I haven't been asked to find solutions, just to justify it. $\endgroup$ Commented May 5, 2015 at 11:20
  • 1
    $\begingroup$ Hensel's Lemma does exactly that. It tells you that a solution exists, without needing to calculate it. $\endgroup$
    – Mathmo123
    Commented May 5, 2015 at 11:21
  • $\begingroup$ 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$ $\endgroup$ Commented May 5, 2015 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.

  • $\begingroup$ 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? $\endgroup$ Commented May 5, 2015 at 11:03
  • $\begingroup$ @VladimirNabokov Mathmo123 gives a nice counterexample. $\endgroup$
    – wythagoras
    Commented May 5, 2015 at 11:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .