Let $M \in M_n(\mathbb{Z})$ with nonzero determinant. We wish to show that there exists a matrix $A$ in $\mathrm{GL}_n(\mathbb{Z})$ such that $MA$ is upper triangular and, denoting $MA = (c_{ij})$, we have the inequalities $0 < c_{11}$ and $0 \leqslant c_{ij} < c_{ii}$ for all $i, j \in \{1, \ldots, n\}$ such that $i < j$.
5a. We denote $M = (x_1 | \cdots | x_n)$. Let $x_1', \ldots, x_n'$ be the elements of $\mathbb{Z}^{n-1}$ obtained by taking the last $(n-1)$ coordinates of $x_1, \ldots, x_n$. Show that there exist $a_1, \ldots, a_n$ in $\mathbb{Q}$, not all zero, such that $\sum_{i=1}^n a_i x_i' = 0$. Show that we can choose the $a_i$ to be integers that are coprime as a set.
5b. Show that there exists a matrix $A_1$ in $\mathrm{GL}_n(\mathbb{Z})$ such that the first column of $\tilde{C} = MA_1$ has all its coefficients $\tilde{c}_{i1}$ zero except the first $\tilde{c}_{11}$ which we can take to be strictly positive.
5c. By considering for all $j = 2, \ldots, n$ the Euclidean division $\tilde{c}_{1j} = q_j \tilde{c}_{11} + r_j$, $0 \leqslant r_j < \tilde{c}_{11}$, show that we can assume $\tilde{c}_{11} > \tilde{c}_{1j}$, if necessary by changing $A_1$.
5d. Conclude by induction.