In Serge Lang’s Algebra he leaves a direct proof of the following statement to the reader:
Let $G$ be a finite abelian group. If $G$ is not cyclic, then there exists a prime $p$ and a subgroup of $G$ isomorphic to $C$$\times$$C$, where $C$ is cyclic of order $p$.
I have come up with this so far:
Consider such a group $G$ and let $r$,$s$ be non-identity elements such that neither can be expressed as a power of the other (such elements exist because $G$ is not cyclic.) We then have two cases: either the periods of $r$ and $s$ are coprime or they aren't (and thus both are divisible by some prime $p$.) Suppose the periods are $m$ and $k$ respectively.
If their periods are coprime, then let $p$ divide $mk$. The group $\langle r\rangle\times\langle s\rangle$ is then cyclic(since $m$ and $k$ are coprime) of order $mk$. Given a generator $x$, the cyclic group $\langle x^{mk/p}\rangle$ is of order $p$ and we have our group $C$. Now we must prove that $s^i$ does not equal $r^k$ for any nontrivial $i,k$. If this were true, then $r^k$ would generate a subgroup of $\langle s\rangle$. The order of this subgroup then divides both $\langle s\rangle$ and $\langle r\rangle$ contradicting $m$ and $k$ being coprime. Hence we have an isomorphism between the subgroup $\langle s,r\rangle$ and $\langle x^{mk/p}\rangle$.
I can not seem to find a similar result for the case where $m$ and $k$ are not coprime (that is, I cannot figure out why $(r^{m/p})^i=(s^{k/p})^j$ cannot happen for nontrivial $i,j$.)
So, overall, is what I have in the first case correct and how do I prove the second?
Here's a proof that does not use the structure theorem for finite(ly generated) abelian groups. I will use multiplicative notation throughout
Let $h\in G$ be of maximal order, and let $H=\langle h\rangle$; let the order of $h$ be $n$. We know that $H\neq G$, since $G$ is not cyclic. Let $x\in G$ be such that $x\notin H$. Let the order of $x$ be $m$.
I claim that $m$ must divide $n$. Indeed, in an abelian group, the orders of elements are lcm-closed; that is, if you have an element of order $m$ and an element of order $n$, then there must exist an element of order $\mathrm{lcm}(m,n)$. Since $n$ is the largest possible order, we must have $\mathrm{lcm}(m,n)\leq n$, and therefore $\mathrm{lcm}(m,n)=n$, proving that $m$ divides $n$, as claimed.
Case 1. $\langle x\rangle \cap H=\{e\}$.
Let $p$ be a prime that divides $m$. Then $x^{m/p}$ has order $p$, $h^{n/p}$ has order $p$, and $\langle x^{m/p}\rangle\cap\langle h^{n/p}\rangle=\{e\}$, so $\langle x^{m/p},h^{m/p}\rangle \cong C_p\times C_p$, as desired.
Case 2. $\langle x\rangle \cap H\neq \{e\}$.
Say $r\gt 0$ is the smallest integer such that $x^r\in H$. Because $x\notin H$, we know that $r\gt 1$. Since $\langle x^r\rangle$ is a proper subgroup of $\langle x\rangle$, we know that $r|n$. Let $s$ be the smallest positive integer such that $h^s\in\langle x\rangle\cap H$. Then we also know that $s|n$, and $s\gt 1$. Moreover, $\langle x^r\rangle = \langle h^s\rangle$, so the order of $h^s$ is the same as the order of $x^r$. That is, $\frac{n}{s}=\frac{m}{r}$. Therefore, $s = \left(\frac{n}{m}\right)r$, and since $m$ divides $n$, it follows that $r$ divides $s$. Write $s=rk$.
Now, $x^r\in \langle h^s\rangle$, so there exists $t$ such that $x^r=(h^s)^t = h^{st} = (h^{kt})^r$. Consider $y=xh^{-kt}$; note that $y\notin\langle h\rangle$, since $x\notin\langle h\rangle$. Also, the smallest positive integer $c$ such that $y^c\in\langle h\rangle$ is $c=r$, because if $y^c\in\langle h\rangle$, then $x^ch^{-ktc}\in \langle h\rangle$, hence $x^c\in\langle h\rangle$. But $y^r = x^rh^{-ktr} = x^r h^{-st} = e$. Thus, $\langle y\rangle \cap \langle h\rangle = \{e\}$, and we are reduced to Case 1, proving that $\langle y,h\rangle$ contains a subgroup of the form $C_p\times C_p$, as desired.