# 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:

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

2. Suppose there exists $x$ such that $Ax = b$, find such $x$.

Thanks.

• This paper by Arkadev Chattopadhyay and Avi Widgerson may be relevant. May 28 '13 at 8:54