Inverse of Homomorphism for product of cyclic groups

Question

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?

Answer 1

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}$$

Answer 2

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}$$