I am trying to prove the following theorem on finitely generated free abelian groups (which thus for simplicity may be assumed to be $\Bbb Z^n$):
Let $\alpha \in \Bbb Z^n$ be such that for all $k > 1$, $\alpha \notin k \Bbb Z^n$.
Then there exists a basis for $\Bbb Z^n$ containing $\alpha$.
It is easy to see that for $\alpha = (\alpha_1, \ldots, \alpha_n)$ to satisfy the premises, it is necessary and sufficient that $\gcd(\alpha_1, \ldots, \alpha_n) = 1$, since $k \Bbb Z^n = (k \Bbb Z)^n$.
It is also easy to solve the problem if for some $i$, $\alpha_i = 1$.
In general, I have tried to write up some matrix equations (the problem is equivalent to the existence of a matrix $M \in \mathrm{GL}(n, \Bbb Z)$ with first column $\alpha$) but I haven't been able to work it out; there may be an inductive argument possible but if so, I failed to find it.
Your help is much appreciated.
This is well-known and there are several proofs. Here is a proof using the classification of finitely generated abelian groups:
Consider $A:=\mathbb{Z}^n / \langle \alpha \rangle$. Since the rank of $\langle \alpha \rangle$ is $1$, the rank of $A$ is $n-1$. One computes that the torsion subgroup of $A$ is trivial. This implies $A \cong \mathbb{Z}^{n-1}$, i.e. we have an exact sequence $0 \to \langle \alpha \rangle \to \mathbb{Z}^n \to \mathbb{Z}^{n-1} \to 0$. Since $\mathbb{Z}^{n-1}$ is free, the sequence splits and we are done.