Lemma 5.14.1. (Primitive vectors and saturated lattices). A primitive vector of extends to a lattice basis. A saturated subgroup is generated by part of a basis and has a free quotient. The group is generated by row interchanges, sign changes, and adding an integer multiple of one row to another.
Proof
Proof. The Euclidean algorithm, applied successively to coordinate pairs, uses these invertible row operations to send a vector to , where is the greatest common divisor of its coordinates. For a primitive vector ; applying the inverse row-operation matrix to the standard basis proves the first assertion. If is saturated, divide a nonzero element by the greatest common divisor of its coordinates. Saturation puts the resulting primitive vector in . The image of in is saturated: if a nonzero integer multiple of a class lies in that image, a representative has that multiple in , since , and hence belongs to . Induction and lifting a quotient basis now give a basis whose first members generate .
For an invertible integral matrix, the greatest common divisor of its first column is one, since any common divisor would divide its determinant . Row operations reduce that column to the first standard vector. The lower-right block is again invertible over ; reduce it by induction, and then clear the remaining entries of the first row using the lower identity rows. This reduces the entire matrix to the identity and proves the generation assertion. ◻