# Making a free module out of a non-free one

Suppose that $M$ is a submodule of $\mathbb{Z}^n$, but $\mathbb{Z}^n/M$ is not free. We can write

$\mathbb{Z}^n/M \simeq \mathbb{Z}/(q_1)\oplus\cdots\oplus \mathbb{Z}/(q_r) \oplus \mathbb{Z}^t$

for some $r$ and $t$ and $q_1|q_2|\cdots|q_r$.

[Question] I'd like to construct a submodule $M'\subset M$ such that $\mathbb{Z}^n/M'$ is free, specifically, $\mathbb{Z}^n/M' \simeq \mathbb{Z}^{r+t}$. Is this always possible? How should I define $M'$?

(I know how to construct $M'\supset M$ such that it removes the torsion part of $\mathbb{Z}^n/M$, i.e., $\mathbb{Z}^n/M'\simeq \mathbb{Z}^t$. One can simply let $M' = \{x: \text{there exists }a\neq 0\text{ such that } ax\in M\}$. But I am not sure how to shrink $M$ to make $\mathbb{Z}^n/M$ free as desired above.)

Thanks.

-
I assume that $M$ is a submodule of ${\Bbb Z}^n$, and that the $q_i$s are defined so that $q_1>1$ and $q_r>0$. Here is an algorithm for constructing $M'$.
If $M$ has generators $a_1$, $\dots$, $a_m$, and if we pick a basis $b_1$, $\dots$, $b_n$ of ${\Bbb Z}^n$, we can represent each $a_i$ as $\sum_j s_{ij} b_j$, where $s_{i1}$, $\dots$, $s_{in}\in{\Bbb Z}$, so that the generating set of $M$ can be represented by the $m$ by $n$ matrix $S=(s_{ij})$ over $\Bbb Z$. Then, $S$ can be reduced to Smith normal form by left- and right-multiplying by invertible square matrices over $\Bbb Z$. This is equivalent to picking a new generating set for $M$ and a new basis for ${\Bbb Z}^n$.
Once $S$ is in Smith normal form it is a (possibly rectangular) diagonal matrix with $1$, $\dots$, $1$, $q_1$, $\dots$, $q_r$, $0$, $\dots$, $0$ along the diagonal. Supposing that there are $u$ $1$s, $M'$ will be generated by the first $u$ elements of the new basis for ${\Bbb Z}^n$, which are the same as the first $u$ elements of the new generating set for $M$.