Finding the Modular Multiplicative Inverse of a large number

Question

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.

Answer 1

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