How many subgroups does $\mathbb{Z}_{13}\times\mathbb{Z}_{13}$ have? 
How many subgroups does $\mathbb{Z}_{13}\times\mathbb{Z}_{13}$ have ?

My attempt:
Firstly, we observe that the possible orders for an element of this group are $1$ and $13$ only.
So, we would need to find the subgroups of order $13$ other than the group $$\mathbb{Z}_{13}\times\mathbb{Z}_{13}$$
itself and the trivial group order $1$ to determine the total number groups.
Now to find the number of subgroups of order $13$, let us first find the number of cyclic subgroups of order $13$ first (moreover, group of order $13$ is already cyclic, fortunately), let us find the number of elements of order $13 $ in $\mathbb{Z}_{13}\times\mathbb{Z}_{13}$
Suppose $o(a,b)=13$ then ${\rm lcm}(o(a),o(b))= 13$. The possiblities are:

*

*$o(a)=1,o(b)=13$ there are $12$ such elements

*$o(a)=13, o(b)=1$ there are $12$ such elements

*$o(a)=13, o(b)=13$ there are $144$ such elements

So, there are a total of $144+12+12=168$ elements of order $13$ in $\mathbb{Z}_{13}\times\mathbb{Z}_{13}$. So, there are $\frac{168}{\phi(13)}=\frac{168}{12}=14$ cyclic subgroups of order $13$ in $\mathbb{Z}_{13}\times\mathbb{Z}_{13}$ (which are in fact the only subgroups of order $13$)
So, we found out that there are a total of $14+2=16$ subgroups in $\mathbb{Z}_{13}\times\mathbb{Z}_{13}$
I was fortunate enough to have a group $\mathbb{Z}_{p}\times\mathbb{Z}_{p}$ where $p$ is prime so that the subgroups of order $p$ are cyclic only, so that the computation becomes easy.

My question is how to tackle such direct sum problems where my p is not a prime and I have to find the number of non-cyclic subgroups ?
How to find the number of subgroups (cyclic or non-cyclic) for any group of type $G_1\times G_2$ ? My focus is mainly of non-cyclic type*

 A: This is not an answer, but more of a long comment on for a generalization in the specific case to find the number of sub-groups of $(\mathbb{Z}/p\mathbb{Z})^n$ when $p$ is prime.
You may know or may not know that, $\mathbb{Z}/p\mathbb{Z}$ is a field if and only if $p$ is prime, so for notational emphasis, we write $\mathbb{F}_p\colon=\mathbb{Z}/p\mathbb{Z}$. In particular, this means that we may consider the direct sum $\mathbb{F}_p^n$ as a vector space over $\mathbb{F}_p$ instead.
It is trivial that each vector sub-space of $\mathbb{F}_p^n$ is a sub-group of $\mathbb{F}_p^n$ under addition. Each sub-group $H$ of $\mathbb{F}_p^n$ is a vector space because it contains the additive identity element, it is trivially closed under addition, and it is closed under scalar multiplication because for $c\in\mathbb{F}_p,m\in H$, we have
$$c\cdot m=\underbrace{m+\cdots+m}_{c\text{ times}}\in H$$
This demonstrates that the set of sub-groups of $\mathbb{F}_p^n$ is equal to the set of vector sub-spaces of $\mathbb{F}_p^n$.
With this preliminary result, we may obtain an explicit formula for the number of sub-groups of $\mathbb{F}_p^n$ by counting the number of sub-spaces of $\mathbb{F}_p^n$.
Lemma: The number of $m$-dimensional sub-spaces of $\,\mathbb{F}_p^n\,$ is given by
$$\prod_{k=0}^{m-1}\frac{(p^n-p^k)}{(p^m-p^k)}=\frac{(p^n-1)(p^n-p)\cdots(p^n-p^{m-1})}{(p^{m}-1)(p^m-p)\cdots(p^{m}-p^{m-1})}\tag{$*$}$$
Note that in the special case of $m=0$, the products above are empty, thus the number of $0$ dimensional sub-spaces of $\mathbb{F}_p^n$ is equal to $1$, as expected.
To prove this, start by counting the number of linearly independent ordered sets of size $m$ in $\mathbb{F}_p^n$. Then, noting that each sub-space of dimension $m$ is isomorphic to $\mathbb{F}_p^m$, count the number of ways to choose an ordered basis of size $m$ in $\mathbb{F}_p^m$. After multiplying this with the number of sub-spaces of dimension $m$, you will have counted the number of ways to choose a linearly independent ordered set in $\mathbb{F}_p^n$ of size $m$ in two different ways. One might formalize this a bit more by considering the equivalence relation on the set of linearly independent sets of size $m$ in $\mathbb{F}_p^m$ by saying that two ordered sets are equivalent if and only if they generate the same sub-space.
Corollary: The number of sub-spaces of $\,\mathbb{F}_p^n\,$ is given by
$$\sum_{m=0}^n\prod_{k=0}^{m-1}\frac{(p^n-p^k)}{(p^m-p^k)}=\sum_{m=0}^n\prod_{k=0}^{m-1}\frac{(p^{n-k}-1)}{(p^{m-k}-1)}$$
Proof: From our lemma, the number of $m$-dimensional sub-spaces of $\mathbb{F}_p^n$ is give by $(*)$. Summing over all $m$ from $0$ to $n$ yields the desired result. $\square$
One can check that this does indeed agree with the answer you got above by observing that
$$1 + \frac{13^2-1}{13-1}+\frac{13^2-1}{13^2-1}\cdot\frac{13^2-13}{13^2-13}=16$$
A: To find the number of subgroups of order $p$ in $(\mathbb Z/p\mathbb Z)^2$, note that the group has $p^2-1$ elements of order $p$. Each of these elements generate a subgroup of order $p$ and each subgroup of order $p$ has exactly $p-1$ generators, hence there are $\frac{p^2-1}{p-1}=p+1$ subgroups of order $p$. In total there are $p+3$ subgroups.
To find the number of subgroups of $\mathbb Z/m\mathbb Z\times\mathbb Z/n\mathbb Z$. First we can decompose $\mathbb Z/m\mathbb Z$ and $\mathbb Z/n\mathbb Z$ into the direct sums of their $p$-primary parts by the Chinese Remainder Theorem. For finitely generated abelian groups $A=\oplus_p A_p\le B=\oplus_p B_p$ where $C_p=\{x\in C: \exists n\in\mathbb N, p^nx=0\}$ is the $p$-primary part of $C$ for $C=A,B$. Note that $A_p\le B_p$, it's enough to find the number of subgroups of each $B_p$. Therefore the problem reduces to find the number of subgroups of $\mathbb Z/p^a\mathbb Z\times\mathbb Z/p^b\mathbb Z$, where $p^a||m$ and $p^b||n$.
