4

Let $f: \mathbb{Z}_{21} \times \mathbb{Z}_{10} \to \mathbb{Z}_{210}$ such that $$f(a,b)= 10a +21b.$$

We have that $f$ is an isomorphism, but how does one go about finding explicitly the inverse $f^{-1}$ of $f$?

3 Answers3

4

Since both are cyclic, both have a generator. You need only find $(a,b)$ such that $f(a,b)=1$, which amounts to the division algorithm. Then

$$f^{-1}(c) = (ca, cb)$$

In this case we have $a=19, b=1$.

Further explanation:

Suppose you have $f(a,b)=1$, i.e. $10a+21b=1$. If $g(c)=(ca,cb)$ then

\begin{align*} g(f(x,y)) = g(10x+21y) &= ((10x+21y)a, (10x+21y)b)\\ &= (10ax,21by)\\ &= ((1-21b)x,(1-10a)y)\\ &= (x,y) \end{align*}

David P
  • 12,320
0

To construct a homomorphism (say, $h$) from a cyclic group $< a >$ (i.e, a group generated by the element $a$) to some group $G$, all we have to do is to assign an appropriate image of $a$ (i.e, we will assign some value to $h(a) \in G$ appropriately).

Since the group $\mathbb{Z}_{210}$ is generated by $1$, to find $f^{-1}$, all we have to do is to assign an appropriate element to $f^{-1}(1) \in \mathbb{Z}_{21}\times \mathbb{Z}_{10}$.

Since $f^{-1}$ is the inverse of $f$, to assign a value for $f^{-1}(1)$, all we have to do is to find which element in $\mathbb{Z}_{21} \times \mathbb{Z}_{10}$ that $f$ maps to $1$ in $\mathbb{Z}_{210}$, then assign $f^{-1}(1)$ to be that element, and the element we're talking about is $(19, 1)$. This element can be easily found by noticing the fact that: $(-2) \times 10 + 1 \times 21 = 1$, and the element $-2$ in $\mathbb{Z}_{21}$ is the same as the element $19$ in $\mathbb{Z}_{21}$.

So $f^{-1}: \mathbb{Z}_{210} \to \mathbb{Z}_{21} \times \mathbb{Z}_{10}$ is constructed so that $f^{-1}(1) = (19, 1) \in \mathbb{Z}_{21} \times \mathbb{Z}_{10}$, so, take any element $c \in \mathbb{Z}_{210}$, we'll have:

$$f^{-1}(c) = f^{-1}(\underbrace{1 + 1 + ... + 1}_{c \text{ elements } 1'\text{s}}) = \underbrace{f^{-1}(1) + f^{-1}(1) + ... + f^{-1}(1)}_{c \text{ elements } f^{-1}(1)'\text{s}} = (19c; c)$$

user49685
  • 4,539
  • $f^{-1}$, and $f$ are just inverses of each other, so it's the same as you are given $f$, and trying to find $f^{-1}$; and to do so, it totally depends on the problem. In this particular problem, since you are constructing a homomorphism from a cyclic group, it's easier, because all you need is to construct the image of the generator (this is what I'm trying to say in the first paragraph of my answer). You can read my reply again, in order to have a deeper understand of what I say. – user49685 Feb 12 '16 at 10:00
  • I claim that $\mathbb{Z}{21} \times \mathbb{Z}{10}$ is cyclic, can you find its generator? – user49685 Feb 12 '16 at 10:05
  • I know I've to find an element of period 210, but I'm not sure how to do it. –  Feb 12 '16 at 10:08
  • That's a good start; now just think simply, can you find an element $(a; b) \in \mathbb{Z}{21} \times \mathbb{Z}{10}$, such that the smallest positive number $n$ satisfying $(na; nb) = (0; 0) \in \mathbb{Z}{21} \times \mathbb{Z}{10}$ must be 210? Note that $x = 0 \in \mathbb{Z}{21}$ means that $x$ is divisible by 21; and $y = 0 \in \mathbb{Z}{10}$ means that $y$ is divisible by 10. I repeat, "think simply". – user49685 Feb 12 '16 at 10:14
  • Does it suffice that $a$ is not divisible by $21$ and $b$ is not divisible by $10$? –  Feb 12 '16 at 10:21
  • Not quite. Here's a counter-example: 3 is not divisible by 21; and 2 is not divisible by 10; but $(3; 2)$ is only of order (or, as you call it, period) 35; since $(35 \times 3; 35 \times 2) = (105; 70) = (0; 0) \in \mathbb{Z}{21} \times \mathbb{Z}{10}$. – user49685 Feb 12 '16 at 10:23
  • Well, $(1,1)$ should do the trick. –  Feb 12 '16 at 10:25
  • So far, so good. So $\mathbb{Z}{21} \times \mathbb{Z}{10}$ is generated by $(1; 1)$; and you are trying to construct a homomorphism $g^{-1}: \mathbb{Z}{21} \times \mathbb{Z}{10} \to \mathbb{Z}{210}$, all you have to do is to assign a value for $g^{-1}(1; 1)$. Now, using the definition for $g$ above, i.e $g(x) = (19x; x)$. Can you find the element $d \in \mathbb{Z}{210}$, such that $g(d) = (1; 1) \in \mathbb{Z}{21} \times \mathbb{Z}{10}$? Or put it this way, can you find $d$ such that $19d \equiv 1 \text{ mod } 21$; and $d \equiv 1 \text{ mod } 10$? – user49685 Feb 12 '16 at 10:28
  • Yes, $31$ works. –  Feb 12 '16 at 10:31
  • Great, so we'll assign $g^{-1}(1; 1) = 31 \in \mathbb{Z}{210}$; and since $(1; 1)$ generates $\mathbb{Z}{21} \times \mathbb{Z}{10}$, every element in $\mathbb{Z}{21} \times \mathbb{Z}{10}$ can be expressed as $(c; c)$ (for some appropriate $c$, of course); so the homomorphism you are looking for is $g^{-1}(c; c) = 31c \in \mathbb{Z}{210}$. This is a little bit hard to see that $g^{-1}$ and the original $f$ are the same; but in fact, they are. – user49685 Feb 12 '16 at 10:34
  • And how does one get back $g(a,b) = 10a + 21b$ from that? –  Feb 12 '16 at 10:36
  • You don't really need to get back to that, there are many ways to define just one mapping. But if you really want to do it, for every $(a; b) \in \mathbb{Z}{21} \times \mathbb{Z}{10}$, can you find a $c$, such that $(a; b) = (c; c) \in \mathbb{Z}{21} \times \mathbb{Z}{10}$? – user49685 Feb 12 '16 at 10:39
  • I'll try that. Another thing: is the generator of $G \times H$ the couple of the generators of $G$ and $H$? –  Feb 12 '16 at 10:42
  • No, in general, it does not hold. There are groups, such that $G$, and $H$ are both cyclic, but not $G \times H$ ($\mathbb{Z}_2 \times \mathbb{Z}_4$ is an example). The other way does hold however, i.e if $(a; b)$ is the generator of $G \times H$, then $a$ must be the generator of $G$, and $b$ must be the generator of $H$. – user49685 Feb 12 '16 at 10:44
  • You can work from (1; 1) onwards, like this: $(1; 1) = (1; 1)$; $(2; 2) = (2; 2)$; $(3; 3) = (3; 3)$; ...; $(10; 10) = (10; 0) \in \mathbb{Z}{21} \times \mathbb{Z}{10}$; $(11; 11) = (11; 1)$; $(12; 12) = (12; 2)$; ...; $(21; 21) = (0; 1) \in \mathbb{Z}{21} \times \mathbb{Z}{10}; (22; 22) = (1; 2)$; ... You'll find out that $(21; 21) = (0; 1)$, and $(190; 190) = (1; 0)$; hence $(a; b) = a(1; 0) + b(0; 1) = a(190; 190) + b(21; 21) = (190a + 21b; 190a + 21b)$. From here, I think it should be easy for you to prove the similarity between $g^{-1}$; and $f$. Hopefully you can go from here, right? – user49685 Feb 12 '16 at 10:58
  • 1
    Yes. Thanks a lot for everything. –  Feb 12 '16 at 11:10
0

It is well known, and easy to check, that if $m$ and $n$ are coprime, and $um+vn=1$ is a Bézout's relation between $m$ and $n$ the inverse isomorphism from $\mathbf Z/m\mathbf Z\times\mathbf Z/n\mathbf Z$ to $\mathbf Z/mn\mathbf Z$ is given by $$(x\bmod m,y\bmod n)\longmapsto yum+xvn\bmod mn.$$

Indeed $z=yum+xvn$ satisfies $$z\bmod m=xvn\bmod m=x(um+vn)\bmod m=x\cdot 1\bmod m=x\bmod m,$$ and similarly $\bmod n$.

Bernard
  • 175,478