Lattice basis for lattice consisting of the set of integer solutions of $a_1 x_1 + \dots + a_1 x_n = 0 \pmod q$

Question

Consider the following set $$ \bigl\{ x \in \mathbb{Z}^n \mid \; a_1 x_1 + \dots + a_n x_n = 0 \!\pmod q \bigr\}. $$

Clearly, this set is a lattice. But I cannot find a basis for it. How would one identify a basis for this lattice?

Answer 1

The answer is not straightforward. These are called q-ary lattices. Appendix A.6 of this thesis:

http://doi.org/10.17638/03003839

explains a way of getting a basis. Hope it helps.