1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you but I've got $73$ and $-124$ vor r and s using the extended euclidian algorithm? $\endgroup$ – KingDingeling Feb 10 at 18:12
  • 1
    $\begingroup$ @KingDingeling Your solutions correspond to choosing $c=-1$ instead of $c=0$, so our results are equivalent $\endgroup$ – Maximilian Janisch Feb 10 at 18:16
  • $\begingroup$ Thank you, but how do you get the $265$ and $-156$? $\endgroup$ – KingDingeling Feb 10 at 18:37
  • 1
    $\begingroup$ @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) $\endgroup$ – Maximilian Janisch Feb 10 at 18:54
  • 1
    $\begingroup$ Thank you very Max for your time and help! $\endgroup$ – KingDingeling Feb 10 at 18:56
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.