Find the inverse of 789 in $\mathbb{Z^*}_{1234}$

Question

I'm confused on this homework question and not sure how to go about solving it. Any guidance would be appreciated. Thanks!

I need to find the inverse of 789 in (nonzero integers mod1234) $\mathbb{Z^*}_{1234}$

Answer 1

$1234=2\cdot 617$, hence it is enough to find the inverse of $789$ in $\mathbb{Z}/(2\mathbb{Z})^*$ (trivial) and $\mathbb{Z}/(617\mathbb{Z})^*$. In terms of continued fractions We have:

$$ \frac{789}{617} = \{1; 3, 1, 1, 2, 2, 1, 2, 1, 2\} $$ and $$ \{1; 3, 1, 1, 2, 2, 1, 2, 1\} = \frac{289}{226} $$ with $$ 789\cdot 226-617\cdot 289 = 1 $$ hence in $\mathbb{F}_{617}$ we have $789^{-1}=226$. By the Chinese remainder theorem, $$ 789^{-1} \equiv 226+617 \equiv \color{red}{843}\pmod{1234}.$$

Answer 2

You just need to solve the equation $$\overline{789}\cdot \overline{x}=\overline1$$ Now $$789\cdot x \equiv 1\pmod{1234}$$ Using Euclidean algorithm we found that $(789, 1234)=1$ so $1=-539\cdot 1234 + 843\cdot789$.That means $$x \equiv 843\pmod{1234} \implies \overline{x}=\overline{843}$$