1
$\begingroup$

A little help would be a lifesaver :)

I already used the Euclidean algorithm to find the GCD of $386$ and $97$, which is $1$. However, I'm stuck on this question posed by my professor: "Then use your computation to explain the statement: $241$ is the multiplicative inverse of $97$ $\mathrm{modulo}$ $386$."

I've been stuck on the topic of multiplicative inverses for days so any help would be greatly appreciated. Thank you so much!

$\endgroup$
2
$\begingroup$

Using Extended Euclidean algorithm determine $p$ and $q$ such that $$ 97 \cdot p - 386\cdot q = 1 $$ Then $97^{-1} \equiv p \mod 386$.

$\endgroup$
0
$\begingroup$

There is likely a typo in the question.


Using the Euclidean algorithm, we have that: \begin{align*} 386 &= 3(97) + 95 \\ 97 &= 1(95) + 2 \\ 95 &= 47(2) + 1 \end{align*} Working backwards, we see that: \begin{align*} 1 &= 95 - 47(2) = 95 - 47(97 - 95) \\ &= -47(97) + 48(95) = -47(97) + 48(386 - 3(97))\\ &= 48(386) - 191(97)\\ \end{align*} Hence, we see that: $$ 1 \equiv 48(386) - 191(97) \equiv -191(97) \equiv 195(97) \pmod{386} $$ So the multiplicative inverse of $97$ modulo $386$ is $195$.

$\endgroup$
0
$\begingroup$

Using formulae used here,

$$\frac{386}{97}=3+\frac{95}{97}=3+\frac1{\frac{97}{95}}$$

$$=3+\frac1{1+\frac2{95}}=3+\frac1{1+\frac1{\frac{95}2}}=3+\frac1{1+\frac1{47+\frac12}}$$

So, the previous convergent of $\displaystyle \frac{386}{97}$ is $\displaystyle3+\frac1{1+\frac1{47}}=3+\frac{47}{48}=\frac{191}{48}$

$$\implies386\cdot48-191\cdot97=1$$ $$\implies -191\cdot97=1\pmod{386}\implies 97^{-1}\equiv-191\equiv386-191$$

$\endgroup$

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.