0
$\begingroup$

We know that using Chinese Remainder Theorem, CRT, for solving a system of linear congruences will give a unique solution $x \pmod {n_1 n_2\cdots n_t}$ where ${n_1,n_2,\ldots,n_t}$ are coprimes. But the solution $x$ is not necessary to be in the least non-negative residue form i.e $x\in\mathbb Z_{n_1 n_2\cdots n_t}$.

Is it possible to use CRT so that $x\in\mathbb Z_{n_1 n_2\cdots n_t}$? And we don't have to compute $x \pmod {n_1 n_2\cdots n_t}$.

$\endgroup$
  • $\begingroup$ The implemetation of CRT will give you a number. That number may not be in the range qwhere you want it. So, you divide by the (big) modulus, and take the remainder. But it appears you object to that last step. Why? $\endgroup$ – Gerry Myerson Jan 17 '15 at 20:40
  • $\begingroup$ It was not an objection rather a question that is it possible to obtain a number less than $n_1n_2...n_t$ without computing remainder. Any way thank you and now it is clear to me. $\endgroup$ – user110219 Jan 19 '15 at 8:53
0
$\begingroup$

No, CRT only states that the solution exists. To find out the explicit solution, you will have to use extended Euclidean algorithm for the case $t=2$, and then rolling the result over, in a similar manner with mathematical induction.

$\endgroup$

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.