Xjyuk

I need to find the inverse of 41 in the integers of Z131 and am confused as to how to go about it.

Do I use the Euclidean Algorithm as 41 mod 131?

To find an inverse we need to find a solution to the following equation (since if you take $pmod131$ this equation will give you $41X equiv 1$ for modulo $131$):

$$41X + 131Y = 1$$

We will find some pair $(X, Y)$ that satisfies this linear Diophantine equation by extended euclidean algorithm. First, we calculate the GCD of the pair $(131, 41)$.

$$(131, 41) = (41, 8) = (8, 1) = 1$$

This means we have a solution since GCD divides the result of Diophantine equation. Now we go the other way around. We have:

$$131 = 3 cdot 41 + 8,$$
$$41 = 5 cdot 8 + 1,$$
$$8 = 3 cdot 1 + 0.$$

We will rewrite them in the following form:

$$131 - 3 cdot 41 = 8,$$
$$41 - 5 cdot 8 = 1.$$

We are going to substitute $131 - 3 cdot 41$ for $8$:

$$41 - 5 cdot (131 - 3 cdot 41) = 1$$
$$16 cdot 41 - 5 cdot 131 = 1$$

Hence our pair of solution is $(16, -5) = (x, y)$. Yet don't forget there are infinitely many other solutions in this case which you can derive by one initial solution. But because they are all in the congruence class $[16]_131$ (AKA the set of numbers which leave the remainder $16$ when divided by $131$), they aren't different at all for the modular arithmetic.

$X equiv 16 pmod131$ will be our inverse.

$131 = 3*41 +8$ so $8 = 131 - 3*41$.

$41 = 5*8 + 1$ so $1 = 41- 5*8 = 41 - 5(131 - 3*41)= 16*41 - 5*131$

So $16*41 - 5*131 =1$.

Or $16*41 = 1 + 5*131$

Or $16*41 equiv 1 pmod 131$.

So $16$ is the multiplicative inverse $mod 131$ of $41$.

In this case, the extended Euclidean algorithm is particularly fast:

beginarrayrrrr
r_i&u_i&v_i&q_i\
hline
131 & 0 & 1\
41 & 1 & 0 & 3\
hline
8 & -3 & 1 & 5\
1 & 16 & -5\
hline
endarray

so a Bézout's relation is $$16cdot 41-5cdot131 = 1$$
and $;41^-1equiv 16bmod 131$.

Below is a calculateion of $ color#0a0x equiv 41^-1pmod!131,$
by the forward extended Euclidean Algorithm.

$ beginarrayrr
[![1]!] &131, xequiv, 0 \
[![2]!] & color#0a041,x equiv, 1\
[![1]!]-3,[![2]!] rightarrow [![3]!] & 8,x equiv -3!!! \
[![2]!]-5,[![4]!] rightarrow [![4]!] & bbox[5px,border:1px solid #c00]x equiv 16!!!
endarray$

Or $bmod 131!:, dfrac141equiv dfrac3123equiv dfrac3-8equiv dfrac-128-8equiv, bbox[5px,border:1px solid #c00]16 $ by Gauss's algorithm

Beware $ $ Modular fraction arithmetic is valid only for fractions with denominator coprime to the modulus. See here for further discussion.

Hint: You use the extended Euclidean algorithm to find $x,y in mathbb Z$ such that $41x+131y=1$.