Solving Linear Equations over $Z_q$ Suppose we are given a linear equation $Ax = b$, where $A \in Z_{q}^{m \times n}$ and $b \in Z_{q}^{m}$.

Note that $q$ is NOT necessarily a prime here. I wonder whether the following can be done in $poly(n, m ,q)$ time:


Check whether there exists $x \in Z_{q}^{n}$ such that $Ax = b$.
Suppose there exists $x$ such that $Ax = b$, find such $x$.


Thanks.
Yes, it is well known it can be done by diagonalizing the matrix using row and column operations. An outline of the procedure is given in the paper The Complexity of Solving Equations over Finite Groups by Goldmann and Russell.