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

  • $\begingroup$ correct. Use Chinese Remainder. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\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$ – Vladimir Nabokov May 5 '15 at 11:16
  • $\begingroup$ Have you covered Hensel's Lemma? $\endgroup$ – Mathmo123 May 5 '15 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$ – Vladimir Nabokov May 5 '15 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 May 5 '15 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$ – 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.

| cite | improve this answer | |
  • $\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$ – Vladimir Nabokov May 5 '15 at 11:03
  • $\begingroup$ @VladimirNabokov Mathmo123 gives a nice counterexample. $\endgroup$ – wythagoras May 5 '15 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.