Topics in Algebra I.N.Herstein Problem 7 Given that if $A$ and $B$ are cyclic of orders m and n and $\gcd(m,n)=1$ then $A\times B$ is cyclic.
Using this prove that if $u,v\in \mathbb Z$ then $\exists x$ such that $x\equiv u(\mod m);x\equiv v(\mod n)$
My try:
Now $(u,v)\in \mathbb Z\times \mathbb Z\implies (u\mod m,v\mod n)\in \mathbb Z_m\times \mathbb Z_n$  
By above lemma $\mathbb Z_m\times \mathbb Z_n$  is cyclic so $\exists (a,b)\in \mathbb Z_m\times \mathbb Z_n$  such that $(u\mod m,v\mod n)=x(a,b)$ for some $ x\in \mathbb Z\implies u\mod m=xa;v\mod n=xb$
I am getting stuck here .Any help
 A: Start with the diagonal map, 
$$\mathbb{Z}/nm\mathbb{Z}\to \mathbb{Z}/n\mathbb{Z}\times \mathbb{Z}/m\mathbb{Z} $$
Now use Chinese remainder theorem. 
A: Let $g=(1\ \mathrm{mod}\ m,\ 1\ \mathrm{mod}\ n)\in \mathbb{Z}_m\times\mathbb{Z}_n$. What is $ng$? When does an element generate $\mathbb{Z}_m$? What is $mg$? When does an element generate $\mathbb{Z}_m$? Conclude that $g$ is a generator for $\mathbb{Z}_m\times\mathbb{Z}_n$.
More generally, you can try to prove that if $A$ and $B$ are cyclic groups of coprime order, then $A\times B$ is cyclic. Moreover, if $a$ and $b$ are generators of $A$ and $B$, then $(a,b)$ is a generator for $A\times B$.
A: Everything after this point is addressing a different question, which is why $A\times B$ is cyclic.

Proof 1
Consider the homomorphism $f:\mathbb{Z}/m \times \mathbb{Z}/n\to\mathbb{Z}/mn$ given by $f(a,b) = na + mb$.
If $(a,b)\in\ker f$, then $mn \mid (na+mb)$, so $m\mid na$ and $n\mid mb$.  Since $m$ and $n$ have no common factors, $m\mid a$ and $n\mid b$, i.e. $(a,b)=0$.
We conclude that $f$ is injective.
Since the domain and codomain of $f$ are finite sets of the same size, $f$ is also surjective, hence an isomorphism.
Note that this is implicitly a proof of Bézout's identity.

Proof 2
The natural homomorphism $\mathbb{Z}\to \mathbb{Z}/m\times\mathbb{Z}/n$ has kernel $mn$, since $mn \mid a \iff m\mid a, n\mid b$.  So the induced map $\mathbb{Z}/mn \to \mathbb{Z}/m \times \mathbb{Z}/n$ is injective, hence surjective.

Proof 3 (choice-free version!)
Let $G$ be cyclic with $|G|=mn$, and let $H,K$ be its (unique) cyclic subgroups with $|H|=m$ and $|K|=n$.
By Lagrange's Theorem, $|HK|\mid mn$, and also $m\mid |HK|,n\mid |HK|\implies mn\mid |HK|$, so $|HK|=mn$, hence $HK=G$.
It follows that $G$ is the internal direct product of $H$ and $K$.
Since cyclic groups of fixed order are unique up to isomorphism, we have $H\cong A$, $K\cong B$.  So $G\cong H\times K \cong A\times B$, hence $A\times B$ is cyclic.
A: Consider the element $(1,1)$. What is the order of this element? It is the smallest $N$ that is both a multiple of $m$ and $n$. Since $m$ and $n$ are relatively prime, $N=mn$. This the group has $mn$ elements and an element of order $mn$, hence it is cyclic.
To show $x$ exists, note that $u,v$ determine an element in the product group, $(u,v)$. Since we have found a generator $(1,1)$, this means there exists an $x$ such that $x(1,1)=(x,x)=(u,v)$, hence $x\equiv u\pmod m$ and $x\equiv v\pmod n$.
