1
$\begingroup$

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.

$\endgroup$
6
  • 6
    $\begingroup$ $(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. $\endgroup$
    – Arturo Magidin
    May 3, 2021 at 19:46
  • $\begingroup$ @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)$. $\endgroup$
    – E2R0NS
    May 3, 2021 at 21:38
  • 1
    $\begingroup$ $(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. $\endgroup$
    – Arturo Magidin
    May 3, 2021 at 21:41
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Arturo Magidin
    May 3, 2021 at 21:43
  • 1
    $\begingroup$ $14 \equiv-1 \pmod{15}$. CRT has a constructive proof, so you can just use it. $\endgroup$
    – Arturo Magidin
    May 3, 2021 at 21:57

2 Answers 2

Reset to default
1
$\begingroup$

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).

$\endgroup$
1
  • 2
    $\begingroup$ 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.$$ $\endgroup$
    – Bernard
    May 3, 2021 at 20:47
1
$\begingroup$

$(1,1)\in\mathbb Z_m×\mathbb Z_n $ does the trick. Or any other $(x,y) $ such that $|x|=m $ and $|y|=n $.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .