Solving a linear equation system in $\mathbb{Z}_q$, where $q$ prime

34 Views Asked by At

I am wondering about the following: Assume you have a linear equation system of the form: $$Ax = b$$, where $A \in \mathbb{Z}_q^{n \times m}$, $x \in \mathbb{Z}_q^m$, $b \in \mathbb{Z}_q^n$ and we want to solve for $x$. I know that in the $\mathbb{R}$, one can do this via Gaussian Elimination for example. Do such algorithms also exists for linear equation systems in $\mathbb{Z}_q$, where $q$ prime (which should guarantee that every element in $Z_q$ has an inverse, correct?). It seems to me we can directly transfer the Gaussian Elimination algorithm directly, because the division operation is not defined in $\mathbb{Z}_q$.