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.

Even over a field, a fair amount goes into this. Here are two pages from Linear Algebra and Matrix Theory by Evar D. Nering, second edition:

From a row-echelon form for your data matrix $A,$ one can readily find the null space as a certain number of columns by placing $1$'s in certain "free" positions and back-substituting to get the other positions. 
Meanwhile, once you have that information, the square matrices you display above are not quite what Buchmann, Lindner, Ruckert, and Schneider want. At the bottom of page 2 they define their HNF for $B$ as being upper triangular as well, where the first several columns have merely a single $q$ on the diagonal element and otherwise $0$'s. So you were close. 
Note that, over a field ($q$ prime) there is a well-defined notion of the rank of $A.$ The number of non-trivial columns of $B$ is $m-n,$ as you have illustrated above. 
Anyway, I think everything about your problem is in ordinary linear algebra books for fields, then I recommend INTEGRAL MATRICES by Morris Newman. 
