# What is a generator for a direct product of groups of integers mod n which is cyclic?

Let $$\mathbb{Z}/ m\mathbb{Z} \times \mathbb{Z}/ n\mathbb{Z}$$ be such that $$m$$ and $$n$$ are relatively prime. We know that this direct product is isomorphic to the cyclic group $$\mathbb{Z}/mn\mathbb{Z}$$ and so is generated by a single element.

What is the element of the form $$(x,y)$$ which generates $$\mathbb{Z}/ m\mathbb{Z} \times \mathbb{Z}/ n\mathbb{Z}$$? We know that $$\mathbb{Z}/mn\mathbb{Z} = \langle1\rangle$$ but I do not see how that helps.

• $(1,1)$ generates the product additively in the case when $\gcd(m,n)=1$. More generally, $(a,b)$ will generate the product if and only if $a$ generates $\mathbb{Z}/m\mathbb{Z}$ and $b$ generates $\mathbb{Z}/n\mathbb{Z}$. This is an easy consequence of the Chinese Remainder Theorem. May 3, 2021 at 19:46
• @ArturoMagidin I thought of $(1,1)$ too but in a concrete example where $m=3$ and $n=5$ I could not see how to get $(2,4)$. May 3, 2021 at 21:38
• $(1,1)\to(2,2)\to(0,3)\to(1,4)\to(2,0)\to(0,1)\to(1,2)$ $\to (2,3)\to(0,4)\to(1,0)\to(2,1)\to(0,2)\to(1,3)$ $\to(2,4)\to (0,0)$. Or noting that $(2,4)=(-1,-1)$, it should suggest that $14(1,1) = (14\bmod 3,14\bmod 5) = (2,4)$ would work. May 3, 2021 at 21:41
• Alternatively, Chinese Remainder Theorem! You want $x$ with $x\equiv 2\pmod{3}$ and $x\equiv 4\pmod{5}$. The solution is $x\equiv 14\pmod{15}$. May 3, 2021 at 21:43
• $14 \equiv-1 \pmod{15}$. CRT has a constructive proof, so you can just use it. May 3, 2021 at 21:57

We in fact know more than "these are isomorphic": this isomorphism is fairly explicit, at least in one direction: from $$\mathbb Z/mn$$ to $$\mathbb Z/n \times \mathbb Z/m$$, it takes $$x \pmod{mn}$$ to the couple $$(x \pmod{n}, x \pmod{m})$$. Generators of $$\mathbb Z/n \times \mathbb Z/m$$ are the images of generators of $$\mathbb Z/mn$$, namely, all the couples $$(x \pmod{n}, x \pmod{m})$$ where $$x$$ is prime to $$mn$$ (equivalently, prime to $$m$$ and $$n$$, since these are relatively prime).
• It might be worth mentioning what the inverse isomorphism is: if $um+vn=1$ is a Bézout's relation between $m$ and $n$, it is the map $$(\alpha\bmod m,\;\beta\bmod n)\longmapsto um \beta + vn\alpha\bmod mn.$$ May 3, 2021 at 20:47
$$(1,1)\in\mathbb Z_m×\mathbb Z_n$$ does the trick. Or any other $$(x,y)$$ such that $$|x|=m$$ and $$|y|=n$$.