2
$\begingroup$

I am practicing some modular arithmetic and I am trying to find the multiplicative inverse of a large number. Here is the problem:

345^-1 mod 76408

I'm not sure how to go about solving this problem. I set it up the following way:

x = 345^-1 mod 76408

345x = 1 mod 76408

76408 = 345 * 221 + 163

345 = 163 * 2 + 19

163 = 19 * 8 + 11

19 = 11 * 1 + 8

11 = 8 * 1 + 3

8 = 3 * 2 + 2

3 = 2 * 1 + 1

2 = 1 * 2

I watched a video where i would then use the extended euclidean algorithm, but I'm unsure as to how to do it.

Any help/advice to solve this would be appreciated! Thanks.

$\endgroup$
  • $\begingroup$ This method is generally the easiest way to organize the Extended Euclidean Algorithm (to compute modular inverses). $\endgroup$ – Bill Dubuque Jan 29 '15 at 23:15
3
$\begingroup$

Here is a way of writing things: $q_i$ and $r_i$ are the quotient and the remainder of the $i$-th division, $u_i$ and $v_i$ are Bézout's coefficients of $r_i$ relative to $76408$ and $345$ respectively.

The recurrence relations are $$u_{i+1}=u_{i-1}-q_iu_i, \quad v_{i+1}=v_{i-1}-q_iv_i.$$

$$ \begin{array}[t]{r@{\qquad}r@{\qquad}r@{\qquad}r} r_i & u_i & v_i & q_i\\ \hline 76408 & 1 & 0 & \\ 345 & 0 & 1 & 221\\ \hline 163 & 1 & -221 & 2\\ 19 & -2 & 443 & 8 \\ 11 & 17 & -3765 & 1 \\ 8 & -19 & 4208 & 1\\ 3 & 36 & -7973 & 2\\ 2 & -91 & 20154 & 1\\ 1 & 127 & -28127 \\ \hline \end{array}$$

So $\,1=127\cdot 76408-28127\cdot 345$ from which we conclude $$ 345^{-1}\equiv -28127\equiv 48281\mod 76408. $$

$\endgroup$
  • $\begingroup$ Remark that this is the same method described in the post linked my above comment. $\endgroup$ – Bill Dubuque Feb 5 '15 at 23:33
  • $\begingroup$ Certainly. It's only a systematised version that I didn't discover! You can find it in, say, Modern Computer Algebra (by Joachim von zur Gathen and Jürgen Gerhardt. $\endgroup$ – Bernard Feb 5 '15 at 23:45
  • $\begingroup$ In fact it is very old. My remark was merely meant to help guide readers to further examples. Cheers. $\endgroup$ – Bill Dubuque Feb 5 '15 at 23:50

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.