$(a,b)=1$ $\iff~\Bbb Z_a\times\Bbb Z_b$ is cyclic

Question

Assuming $(a,b)=1$, I want to construct an isomorphism $\phi:\Bbb Z_a\times\Bbb Z_b\mapsto\Bbb Z_{a\cdot b}$ defined by $\phi(1,1)=1$. So I need to prove that for any $(x,y)\in \Bbb Z_a\times\Bbb Z_b$ there exists $n\in \Bbb N$ such that $n\equiv x \mod a$ and $n\equiv y\mod b$

For example $(1,2)\in\Bbb Z_2\times\Bbb Z_3$ is $(5\mod2,5\mod3)$

I'm not sure how to prove that, I tried using the Bezout equality...

For the other way we need to assume $\Bbb Z_a\times\Bbb Z_b$ is cyclic i.e. $\Bbb Z_a\times\Bbb Z_b =\langle(x,y)\rangle$ for some $(x,y)$

Since $0\in\langle(x,y)\rangle$, $\exists n\in \Bbb N~:~nx\equiv0\mod a~\text{and } ny\equiv 0\mod b$

And here I'm stuck again.

Answer 1

First note that the order of an element $(x,y) \in \mathbb{Z}_a \times \mathbb{Z}_b$ is $\text{lcm}(r_1,r_2)$, where $r_1$ is the order of $x \in \mathbb{Z}_a$ and $r_2$ is the order of $y \in \mathbb{Z}_b$. Also note that $\text{lcm}(a,b) = ab$ iff $a$ and $b$ are relatively prime.

For the forward direction, we can just prove the contrapositive. So suppose $\mathbb{Z}_a \times \mathbb{Z}_b$ is not cyclic. Then there exists some $r \lt ab$ such that $r(1,1) = (0,0)$ otherwise $\mathbb{Z}_a \times \mathbb{Z}_b$ would be cyclic. But this means that $\text{lcm}(1,1) \le r \lt ab$ so that $a$ and $b$ are not relatively prime.

For the other direction, suppose that $\mathbb{Z}_a \times \mathbb{Z}_b$ is cyclic. Now $(1,1) \in \mathbb{Z}_a \times \mathbb{Z}_b$ has order $\text{lcm}(r_1, r_2)$ where $r_1$ is the order of $1 \in \mathbb{Z}_a$ and $r_2$ is the order of $1 \in \mathbb{Z}_b$. Then $\text{lcm}(r_1, r_2) = ab$ iff $a$ and $b$ are relatively prime. So if $\mathbb{Z}_a \times \mathbb{Z}_b$ is cyclic, the order of $(1,1)$ is $ab$ since $(1,1)$ has to generate the group and hence $a$ and $b$ must be relatively prime by the previous statement.

Answer 2

The group $\mathbb{Z}_a \times \mathbb{Z}_b$ is generated by $(1,0)$ and $(0,1)$, so the choices of $\phi(1,0)$ and $\phi(0,1)$ determine the homomorphism completely. You shall pick those values such that: $$ \begin{align*} &a \cdot \phi(1,0) \equiv 0 \quad\bmod ab \\ & b \cdot \phi(0,1) \equiv 0 \quad \bmod ab \\ \end{align*} $$ Let's pick: $$ \phi(x,y)=(bx+ay) \bmod ab $$ Bezout's identity ensures that the integers of the form $bx+ay$ are exactly the multiples of $(a,b)=1$.

This implies that $\phi$ is a bijection and thus an isomorphism.