Finding a basis for the solution space of a system of Diophantine equations Let $m$, $n$, and $q$ be positive integers, with $m \ge n$.
Let $\mathbf{A} \in \mathbb{Z}^{n \times m}_q$ be a matrix.
Consider the following set:
$S = \big\{ \mathbf{y} \in \mathbb{Z}^m \mid \mathbf{Ay} \equiv \mathbf{0}  \pmod q \big\}$.
It can be easily shown that $S$ constitutes a lattice, because it is a discrete additive subgroup of $\mathbb{R}^m$.
I want to find the basis of this lattice. In other words, I want to find a matrix $\mathbf{B} \in \mathbb{Z}^{m \times m}$, such that the following holds:
$S = \{\mathbf{Bx} \mid \mathbf{x} \in \mathbb{Z}^m \}$.
Let me give some examples:


*

*$q=2$, and $\mathbf{A} = [1,1]$  $\quad \xrightarrow{\qquad}\quad$ 
$\mathbf{B} = \left[ \begin{array}{cc} 2&1 \\ 0&1 \end{array} \right]$

*$q=3$, and $\mathbf{A} = \left[ \begin{array}{ccc} 0&1&2 \\ 2&0&1 \end{array} \right]$
$\quad \xrightarrow{\qquad}\quad$ 
$\mathbf{B} = \left[ \begin{array}{ccc} 3&0&1 \\ 0&3&1 \\ 0&0&1 \end{array} \right]$

*$q=4$, and $\mathbf{A} = \left[ \begin{array}{ccc} 0&2&3 \\ 3&1&2 \end{array} \right]$
$\quad \xrightarrow{\qquad}\quad$ 
$\mathbf{B} = \left[ \begin{array}{ccc} 4&2&1 \\ 0&2&1 \\ 0&0&2 \end{array} \right]$
Note that in all cases, $\mathbf{AB} =\mathbf{0} \pmod q$. However, $\mathbf{B}$ is not an arbitrary solution to this equivalence, since it must span $S$. For instance, in the example 1 above, matrix $\mathbf{\hat B} = \left[ \begin{array}{cc} 2&0\\ 0&2 \end{array} \right]$ satisfies $\mathbf{A \hat B} =\mathbf{0} \pmod 2$, but generates a sub-lattice of $S$. 
Also note that if $\mathbf{B}$ is a basis of $S$, any other basis $\mathbf{\bar B}$ is also a basis of $S$, provided that there exists a unimodular matrix $\mathbf{U}$, for which $\mathbf{\bar B} = \mathbf{BU}$.
My questions:

  
*
  
*How to obtain $\mathbf{B}$ from $\mathbf{A}$ and $q$?
  
*Is it possible that $\mathbf{B}$ is not full rank, i.e. $\text{Rank}(\mathbf{B})< m$?
  
*Is there any difference between the case where $q$ is prime and the case where it is composite?
  

Side note: As far as I understood, $S$ is the solution space of a system of linear Diophantine equations. The solution has something to do with Hermite normal forms, but I can't figure out how.

Will Jagy has provided an instructive example but no formulae. I will write these here, in case they are still of any interest/use to anyone:
1) We start with the matrix A and we perform elementary row operations to bring it to the form
$$A\sim\left[\begin{array}{c c} I |& C \end{array}\right].$$
We are allowed to do all operations $\mod q$.
2) A basis for the lattice $S$ is then given by the matrix
$$B=\left[\begin{array}{c c} qI & -C\\
0 & I\end{array}\right]$$
The above basis is in (almost) Hermite Normal Form. If we do want it in HNF all we have to do is add multiples of q to the entries of -C to bring them to the range $\{0,\cdots,q-1\}$.
In terms of terminology, the S lattice is (the complement of) a q-ary lattice.
The case where we are not able to bring A to the form in 1) is handled in Will Jagy's answer.
