Systems of linear equations over integers modulo n Let $\mathbb Z_n$ be the ring of integers modulo $n$. Let $A\in M_k(\mathbb Z_n)$ be a square matrix of size $k$. Let $X=[x_1, \ldots, x_k]^T$, where $x_i\in\mathbb Z_n$. 
There is some method to count the number of solutions in $\mathbb Z_n^k$ of the system
$$AX=O,$$
of linear equation? 
 A: Here is an algorithm to find all solutions, maybe it can help you to compute the number of solutions
Using Chinese remainder theorem you can reduce the problem to the problem of finding solutions over $\mathbb{Z}/p^k\mathbb{Z}$. For $\mathbb{Z}/p\mathbb{Z}$ find solutions by Gauss. Now, If $x_1$ is the solution of $Ax=b\mod p $ then to lift the solution to $\mathbb{Z}/p^2\mathbb{Z}$ you need to write $Ax_1-b=pb_1$ and solve $Ax=b_1 \mod p$. Then $x_1-px_2$ is your lift. You can proceed in the same way to lift the solution to $\mathbb{Z}/p^k\mathbb{Z}$. You can try to compute the number of lifts without solving the equation.
A: (I originally edited the previous answer, but I think it is better to post this as a new answer.)
Here is an algorithm to find a solution; it can probably be extended to compute the number of solutions.
Using the Chinese remainder theorem you can reduce to the case of finding solutions modulo $p^k$; below, assume $k=2$ just to give the idea. 
First solve the equation modulo $p$ using standard techniques, giving a solution $\vec x_1$. So $A \vec x_1=\vec b\bmod p$, and thus $A\vec x_1 = \vec b+p \cdot \vec b_2 \bmod p^2$ for some $\vec b_2$. To lift this solution to a solution modulo $p^2$, we will look for a solution of the form $\vec x=\vec x_1 + p\cdot \vec x'$. The equation $A \cdot (\vec x_1 + p \cdot \vec x') = \vec b \bmod p^2$ reduces to $pA\vec x' = -p \cdot \vec b_2 \bmod p^2$, which in turn reduces to $A \vec x' = -\vec b_2 \bmod p$; this can again be solved using standard techniques.
