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