I would like to compute the solution space of the following system of linear congruences

$\begin{alignat*}{2} a_{11}x_1+&\ldots&a_{1n}x_n&\equiv& b_1&\pmod{n}\\ a_{21}x_1+&\ldots&a_{2n}x_n&\equiv& b_2&\pmod{n}\\ \vdots\\ a_{n1}x_1+&\ldots&a_{nn}x_n&\equiv& b_n&\pmod{n} \end{alignat*}$

Here $n$ need not be a prime and there is no restriction on $a_i$'s and $b_i$'s.

While searching in the literature, I came across this article by Knill. I also encountered a few posts on math.SE, for example:

In fact as mentioned in this post, I had also written a programme using brute force.

I would like to know whether there is any efficient algorithm (like CRT or some linear algebra methods) or any implementation in some CAS is available?


Your Answer

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

Browse other questions tagged or ask your own question.