# Inverse of Homomorphism for product of cyclic groups

I need to explicitly calculate the inverse of $$\mathbb{Z}/89081\mathbb{Z}\rightarrow\mathbb{Z}/229\mathbb{Z} \times \mathbb{Z}/389 \mathbb{Z}$$ with $$a \mod 89081 \mapsto (a\mod 229, a\mod 389)$$

Now I knew this: $$\mathbb{Z}/229\mathbb{Z}$$ and $$\mathbb{Z}/389$$ are cyclic and if an isomorphism exits between $$\mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/mZ \rightarrow \mathbb{Z}/nm\mathbb{Z}$$ with the groups cyclic, this is equivalent to $$\gcd(n,m)=1$$, so I know that $$\gcd(229,389)=1$$. Now I suspect that it has something to do with finding the inverse of the element modulo, I am not sure, maybe you could give me a hint. It needs to be such an $$a$$ that the inner product is $$a^{-1}$$. What do I need to do to get there? Do I have to calculate the inverse of $$229,389 \mod 89081$$? And where to next?

Using the chinese remainder Theorem: Indeed we first note that $$229\cdot 389=89081$$ and that $$229$$ and $$389$$ are coprime. So indeed your map is an isomorphism.

We want to construct an inverse. For this we are looking for two numbers $$e_1,e_2$$ such that $$e_i\equiv\delta_{i,j}\pmod{m_j}$$ for $$i,j\in\{1,2\}$$, where $$m_1=229$$ and $$m_2=389$$.

Indeed using the Extended_Euclidean_algorithm, we can find two integers $$r,s$$ such that $$r\cdot m_1+s\cdot m_2=1$$. By then setting $$e_1=s\cdot m_2$$ and $$e_2=r\cdot m_1$$, we have achieved our goal. Explicitly, we have $$r=265+c\cdot 389$$ and $$s=-156-229\cdot c$$ for any integer constant $$c$$ (that I will choose $$=0$$).

So $$e_1=-60684$$ and $$e_2=60685$$ will do the trick, i.e. we have the explicit inverse $$\mathbb{Z}/229\mathbb{Z} \times \mathbb{Z}/389 \mathbb{Z}\rightarrow\mathbb{Z}/89081\mathbb{Z}, \\(a,b)\mapsto- a \cdot60684+b\cdot60685\pmod{89081}$$

• Thank you but I've got $73$ and $-124$ vor r and s using the extended euclidian algorithm? – KingDingeling Feb 10 at 18:12
• @KingDingeling Your solutions correspond to choosing $c=-1$ instead of $c=0$, so our results are equivalent – Maximilian Janisch Feb 10 at 18:16
• Thank you, but how do you get the $265$ and $-156$? – KingDingeling Feb 10 at 18:37
• @KingDingeling I am not sure if I understand your question correctly: We have $265=-124+389$ and $-156=73-229$ (if the question is why I chose this pair over the other one, then I can tell you that there is no reason, indeed it is completely arbitrary) – Maximilian Janisch Feb 10 at 18:54
• Thank you very Max for your time and help! – KingDingeling Feb 10 at 18:56

Use the Chinese remainder theorem. The wikipedia page has constructive proofs using the extended Euclidean algorithm that can be used for implementation.

Note on "can be used": The linked page searches for simultaneous solution of: $$x=a_2 \mod n_1 \\ x=a_1 \mod n_2$$ In our case we have $$n_1=229$$, $$n_2=389$$ (or, if you prefer, $$n_2=229$$, $$n_1=389$$ in which case you have to adjust what follows accordingly).

Use the extended Euclidean algorithm to compute $$m_1$$ and $$m_2$$ such that $$1=m_1n_1 + m_2n_2$$ which is possible because our moduli are relatively prime. Then the solution is $$x = a_2m_1n_1 + a_1m_2n_2$$ This establishes a mapping $$(a_1,a_2)\mapsto x$$ where $$x$$ is a function of $$a_1$$ and $$a_2$$: \begin{align} \mathbb Z/n_1\mathbb Z \times Z/n_1\mathbb Z &\to \mathbb Z/n_1n_2\mathbb Z\\ (a_1,a_2)&\mapsto x=x(a_1,a_2) \end{align}

• Thank you, but what do you mean by "use" it, I mean use it to...? – KingDingeling Feb 10 at 15:12
• Thank you very much for your answer and time. – KingDingeling Feb 10 at 18:15