Using the Euclidean Algorithm how to find the inverse of 41 in Z(131) 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?
 A: To find an inverse we need to find a solution to the following equation (since if you take $\pmod{131}$ 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 \pmod{131}$ will be our inverse.
A: In this case, the extended Euclidean algorithm is particularly fast:
\begin{array}{rrrr}
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
\end{array}
so a Bézout's relation is $$16\cdot 41-5\cdot131 = 1$$
and $\;41^{-1}\equiv 16\bmod 131$.
A: $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$.
A: Below is a calculateion of $\ \color{#0a0}{x \equiv 41^{-1}}\pmod{\!131}\,$
by the forward extended Euclidean Algorithm.
$\ \ \ \ \begin{array}{rr}
[\![1]\!]  &131\, x\equiv\, 0  \\
[\![2]\!]  & \color{#0a0}{41\,x \equiv\, 1}\\
[\![1]\!]-3\,[\![2]\!] \rightarrow [\![3]\!] &  8\,x \equiv -3\!\!\! \\
[\![2]\!]-5\,[\![3]\!] \rightarrow [\![4]\!] & \bbox[5px,border:1px solid #c00]{x \equiv 16}\!\!\! 
\end{array}$

Or $\bmod 131\!:\,\ \dfrac{1}{41}\equiv \dfrac{3}{123}\equiv \dfrac{3}{-8}\equiv \dfrac{-128}{-8}\equiv\, \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.  
A: I use scaling method.  Since 8*41 > 131, go straight for final inverse.
1
8
41 → $(-1)^2\lfloor 1/8*131 \rfloor = 16 \equiv 41^{-1} \text{ (mod 131)} $
131 
Example, it takes only 4 scalings so to calculate:  
1/1223334444 ≡ 3171632349 (mod 9988776655)
