Prove that $\mathbb Z_{m}\times\mathbb Z_{n} \cong \mathbb Z_{mn}$ implies $\gcd(m,n)=1$. Prove that $\mathbb Z_{m}\times\mathbb Z_{n} \cong \mathbb Z_{mn}$ implies $\gcd(m,n)=1$.
This is the converse of the Chinese remainder theorem in abstract algebra. Any help would be appreciated.
Thanks!
 A: Suppose $\gcd(m, n) = d\gt 1$. 
Then $\frac{mn}{d}$ is divisible by both $\,m \text { and}\;n.\;$ Therefore, for any $(r, s) \in \mathbb Z_m \times \mathbb Z_n$ we have that $$\underbrace{(r, s) + (r, s) + \cdots + (r, s)}_{\Large \frac{mn}{d} \,\lt\, mn  \;\;\text{summands}} = (0, 0).$$ Hence no element $\,(r, s) \in \mathbb Z_m \times \mathbb Z_n\,$ can generate the entire group, whose order is $\,mn > \frac{mn}{d}.\,$ So, $\,\mathbb Z_m \times \mathbb Z_n\,$ is not cyclic, and thus, cannot be isomorphic to $\mathbb Z_{mn}$, a group we know is cyclic.
This proves the contrapositive of the claim. It proves : $$ \gcd(m, n) \neq 1 \implies \mathbb Z_m\times \mathbb Z_n \not\cong \mathbb Z_{mn}$$ 
Since an implication and its contrapositive are logically equivalent, we have thus shown:

$$\mathbb Z_{m}\times\mathbb Z_{n} \cong \mathbb Z_{mn}\,\text{ implies } \;\;\gcd(m,n)=1.$$

A: Approach: Contrapositively, $(m,n)>1 \implies \mathbb{Z}_m\times\mathbb{Z}_n$ not cyclic $\implies \mathbb{Z}_m\times\mathbb{Z}_n \ncong \mathbb{Z}_{nm}$ since the latter is cyclic.
Basically, the contrapositive is much easier to verify (which is fine for our purposes, since it is equivalent); all one needs to do is to find some "basic property", i.e., one that should hold under isomorphism, and show that these two groups do not share the property. The one I chose is "being cyclic". (I leave it to you justify the steps I gave though.)
A: Hint: Every element of $\mathbb{Z}_m\times \mathbb{Z}_n$ has order $\le$ the lcm of $m$ and $n$.
