Proof
Clearly the rank of $\mathbb{Z} \oplus \mathbb{Z}$ is $2$, so we must have that the rank of $(6,9)$ is $\leq 2$.Let $e_1 = (1,0)$ and $e_2 = (0,1)$ be a basis for $\mathbb{Z} \oplus \mathbb{Z}$, notice that: $$ \mathbb{Z} \oplus \mathbb{Z} = \{me_1 + ne_2\ |m,n \in \mathbb{Z}\}$$ $$ (6,9) = \{6me_1 + 9ne_2\ |m,n \in \mathbb{Z}\}$$ $$R = \mathbb{Z}$$
Now, for each $\mathbb{Z}$-module homomorphism $\phi:\mathbb{Z} \oplus \mathbb{Z} \longrightarrow \mathbb{Z}$, we have that $\phi((6,9))$ is a submodule of $\mathbb{Z}$. In other words, $\phi((6,9))$ is an ideal in $\mathbb{Z}$. Now, recall that $\mathbb{Z}$ is a PID, then this ideal must be principal, but the ideal generated by two nonzero elements $x,y$ is the principal ideal generated by their greatest common divisor: $d:(x,y) = (d)$. In this case, we have: $d:(6,9) = (3) = \mathbb{Z}_3$.
Now, for $\mathbb{Z}$ being a PID, $\mathbb{Z}$ must contain a maximal ideal. Clearly, $\mathbb{Z}_3$ is a maximal ideal, since an ideal $\mathbb{Z}_n$ is maximal if and only if $\mathbb{Z}/\mathbb{Z}_n$ is a field, and the later occurs only is $n$ is prime.($3$ is a prime number).
On the other hand, let $y \in (6,9)$ such that there exist $v \in \ \mbox{Hom}(\mathbb{Z} \oplus \mathbb{Z}, \mathbb{Z})$ with the property that: $$v:v(y) = a_1,$$ where $a_1$ denote the maximal element, in this case: $a_1 = 3$ and $v((6,9)) = (3) = \mathbb{Z}_3$.
Now, let $\pi_i(m) \in \ \mbox{Hom}(M,R)$ defined as follows: $$\pi_1(m) = \pi_1(me_1 + ne_2) = m$$ $$\pi_2(m) = \pi_2(me_1 + ne_2) = n$$
We claim that $a_1 | \pi_i(y)$, since $y = 6\bar{m}e_1 + 9\bar{n}e_2$, then: $$\pi_1(y) = \pi_1(6\bar{m}e_1 + 9\bar{n}e_2) = 6\bar{m}$$ $$\pi_2(y) = \pi_1(6\bar{m}e_1 + 9\bar{n}e_2) = 9\bar{n}$$ Now we can rewrite the above expression as follows: $$\pi_1(y) = a_1b_1 = 3b_1$$ $$\pi_2(y) = a_1b_2 = 3b_2$$ On the other hand, as in the book define: $$y_1 = b_1e_1 + b_2e_2$$ Clearly: $ 3y_1 = y$, since: $$3y_1 = (3b_1)e_1 + (3b_2)e_2 = \pi_1(y)e_1 + \pi_2(y)e_2 = 6\bar{m}e_1 + 9\bar{n}e_2 = y$$
In particular, we have that: $a_1 = v(y) = v(a_1y_1) = a_1v(y_1) \Rightarrow v(y_1) = 1$.
Now, we can take $y_1$ to be a basis for $\mathbb{Z} \oplus \mathbb{Z}$ and $a_1y_1$ to be a basis for $(6,9)$, but then I need to prove that:
$$\mathbb{Z} \oplus \mathbb{Z} = \mathbb{Z}y_1 \oplus \ker(v) \ \ \ (1)$$ $$ (6,9) = \mathbb{Z}3y_1 \oplus ((6,9) \cap \ker(v)) \ \ \ (2)$$
To prove $(1)$, let $x \in \mathbb{Z} \oplus \mathbb{Z}$ and write: $$ x = v(x)y_1 + (x – v(x)y_1).$$ Now, $v(x – v(x)y_1) = v(x) – v(x)v(y_1) = 0$, so $(x – v(x))y_1$ is an element of the kernel of $v$(we used the fact that $v((6,9))$ is a principal ideal). Then, $x$ can be rewritten as an element in $\mathbb{Z}y_1$ and an element of the kernel of $v$, hence: $$ \mathbb{Z} \oplus \mathbb{Z} = \mathbb{Z}y_1 + \ker(v) $$ To see that the sum is direct, let $ry_1 $ to be an element in the kernel of $v$, then $$0 = v(ry_1) = rv(y_1) = r$$ To prove $(2)$, let $\bar{x} \in (6,9)$, since $a_1 = 3$ is a generator of $v((6,9))$, then $v(\bar{x})$ is divisible by $3$. Therefore, we have that: $v(\bar{x}) = 3b$ for $b \in \mathbb{Z}$, then by the similar procedure applied in $(1)$, we have that: $$\bar{x} = v(\bar{x}) y_1 + (\bar{x} - v(\bar{x})y_1) = b3y_1 + (\bar{x} – b3y_1) $$ Clearly, $(\bar{x} – b3y_1)$ is an element of the kernel of $v$, since: $$v(\bar{x} – b3y_1) = v(\bar{x}) – v(b3y_1) = v(\bar{x}) – v(\bar{x}) = 0 $$ This shows that: $$(6,9) = \mathbb{Z}3y_1 + ((6,9) \cap \ker(v)) $$ To prove that the sum is direct, let $r3y_1 $ to be an element of the kernel of $v$, then $v(r3y_1) = 0 = r3v(y_1) = r3 \Rightarrow r = 0$.
My question is:
How to finish this approach to give the definitive basis?
The first element in our basis should be such that $kv_1 = (6,9)$, and such that the coordinates are reduced to lowest terms: so $(2,3)$ is the natural choice. Now we want to expand this to a basis: e.g. we want to find $a,b$ such that the matrix $$\begin{pmatrix} 2 & a \\ 3 & b \end{pmatrix}$$ has determinant 1 ( or -1, we just want the determinant to be a unit in $\mathbb{Z}$ so that the matrix is invertible over $\mathbb{Z}$). By inspection, $a = -1, b = -1$ works. For a more systematic/generalizable approach, use Euclid's algorithm to write $$ 1 = \gcd(2,3) = 2s + 3t$$ and and then set $a = -t,b = s$. So now our basis is $v_1 = (2,3), v_2 = (-1,-1)$ which we see is a basis since it is the image of the standard basis under the invertible transform given by the above matrix.