1

I have to solve a Chinese remainder theorem example where one of the congruence relations is $x^2 = 1 (4)$. I figured out that it should also be possible to write $x=1(2)$. Is this correct and is there a general way how such problems (relations with squares) can be approached? Unfortunately this special case was not covered in the lecture.

Thanks

user116732
  • 131
  • I don't see a way except to take the congruence for a square, solving it (might give two solutions), and solve the different cases that arise. – vonbrand Feb 02 '14 at 12:09
  • @vonbrand, solving a quadratic congruence might have a lot more than 2 solutions. – Gerry Myerson Feb 02 '14 at 12:29

1 Answers1

1

Yes, it is correct, $x^2\equiv 1\pmod4$ is equivalent to $\ x\equiv 1\pmod2$, so you can write that linear congruence in place of the first one.

As for a general similar case, I would suggest to actually solve the quadratic congruence, and then -- unless you can write it as a single linear congruence, as in this example -- replace the quadratic congruence with the solutions, separated by 'or' (yielding thus many solutions for the final composite congruence).

Berci
  • 90,745