3
$\begingroup$

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?

$\endgroup$

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.