The number of non-isomorphic Abelian groups depends on the partition number of the exponents in the prime factorization. Let $P(k)$ be the number of ways to partition $k$ (for example, $P(4) = 5$, since we have $4, 3+1, 2+2, 2+1+1$, and $1+1+1+1$). Then for $n=p_1^{e_1} \ldots p_r^{e_r}$, there are
$$\prod_i P(e_i)$$
non-isomorphic Abelian groups of order $n$. You missed $2+2$ among the ways to partition $4$, corresponding to $\mathbb Z/(2^2\mathbb Z) \times \mathbb Z/(2^2\mathbb Z) = \mathbb Z/4\mathbb Z \times \mathbb Z/4\mathbb Z$.
You can use this formula to answer the original question. The first few partition numbers are:
P(1) = 1 1
P(2) = 2 2, 1+1
P(3) = 3 3, 2+1, 1+1+1
P(4) = 5 4, 3+1, 2+2, 2+1+1, 1+1+1+1
P(5) = 7 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
and they obviously increase from here. Now, if there are $4$ Abelian groups of order $n$, then we must have $e_1=e_2=2$, and we choose as bases the two smallest primes. Thus the number we are looking for is $2^23^2=36$.
Approach one:
In this approach we directly show it is surjective. Given $(x,y)\in U(s)\times U(t)$. Consider $\phi(xt T+ys S)$ where $tT\equiv1~mod~(s),~sS\equiv1~mod~(t)$. Why does such $S,~T$ exists? Why is $xt T+ys S$ relative prime to $st$? What is $\phi(xt T+ys S)$?
Approach two:
In this approach we assume we know the fact that Euler phi function satisfies
$$\varphi(st)=\varphi(s)\varphi(t)$$
, say by method of elementary number theory. Hence the cardinality of $U(st)$ and $U(s)\times U(t)$ are same.
$U(st),~U(s)\times U(t)$: these are finite sets. Now you have a injective function between two finite sets. If these two finite sets have same cardinality, then by set theory, this injection is not only an injection but also a what?
Final remark:
Approach one gives a proof that $$\varphi(st)=\varphi(s)\varphi(t)$$ for relatively prime $s,t$.
Best Answer
(A) If $n$ is prime, then you know that $U(n)$ is cyclic, and so it cannot have a non-cyclic subgroup. So your goal is to find a composite $n$.
The simplest such would be $n = pq$, where $p, q$ are prime and $p\neq q$. Now $$ U(n) \cong U(p) \times U(q) \cong \mathbb{Z}_{p-1} \times \mathbb{Z}_{q-1} $$ To find a subgroup of the form $\mathbb{Z}_5\times \mathbb{Z}_5$, one can look for two primes $p$ and $q$ such that $$ 5\mid (p-1), \text{ and } 5\mid (q-1) $$ So you list down numbers of the form $(5k+1)$ until you hit two distinct primes : 11, and 31.
Hence, $U(341) \cong \mathbb{Z}_{10}\times \mathbb{Z}_{30}$ has a subgroup isomorphic to $\mathbb{Z}_5\times \mathbb{Z}_5$.
Now can you try the same thing for (B)?