# fine the inverse of $[2]$ and $[23]$ in$\mathbb{Z}_{41}$

I know the inverse of [23] is

[23] * [25] = 575

575 congruent to 1 mod 41

[25] is the inverse

I have started the other one but I am doing something wrong I got

[2] * [41] = [82] = [0]

82 congruent to 0 mod 41

I thought 41 would be the inverse but it is not.

• What about $21$, what happens when you multiply by $2$? – André Nicolas Nov 16 '15 at 21:20
• it seems like that would work so would 21 be the inverse then? – bella Nov 16 '15 at 21:22
• Yes The inverse of $2$ modulo any odd number is easy. – André Nicolas Nov 16 '15 at 21:24
• You are welcome. In more general situations, and in particular when the modulus is not small, something systematic like the Extended Euclidean Algorithm needs to be used. – André Nicolas Nov 16 '15 at 21:30

Here is a general method for finding the inverse of $a$ in $Z_n$:

• Set $x_1=1$
• Set $x_2=0$
• Set $y_1=0$
• Set $y_2=1$
• Set $r_1=n$
• Set $r_2=a$
• Repeat until $r_2=0$:
• Set $r_3=r_1\bmod{r_2}$
• Set $q_3=r_1/r_2$
• Set $x_3=x_1-q_3\cdot{x_2}$
• Set $y_3=y_1-q_3\cdot{y_2}$
• Set $x_1=x_2$
• Set $x_2=x_3$
• Set $y_1=y_2$
• Set $y_2=y_3$
• Set $r_1=r_2$
• Set $r_2=r_3$
• If $y_1>0$ then output $y_1$, otherwise output $y_1+n$

And here is an equivalent code in C:

int Inverse(int n,int a)
{
int x1 = 1;
int x2 = 0;
int y1 = 0;
int y2 = 1;
int r1 = n;
int r2 = a;

while (r2 != 0)
{
int r3 = r1%r2;
int q3 = r1/r2;
int x3 = x1-q3*x2;
int y3 = y1-q3*y2;

x1 = x2;
x2 = x3;
y1 = y2;
y2 = y3;
r1 = r2;
r2 = r3;
}

return y1>0? y1:y1+n;
}

Calling Inverse(41,2) returns $21$.

Calling Inverse(41,23) returns $25$.

• That is an implementation of the Extended Euclidean algorithm. – Bernard Nov 16 '15 at 21:50
• @Bernard: Thank you for the enlightenment, I wasn't aware of that (I just used it "as is" during Cryptography course for hw assignments, etc). – barak manos Nov 16 '15 at 22:04
• You might be interested in a ‘naive’layout in the form of a table that can be performed by hand, and may be easier to follow for non-programmers. I gave a few examples in some answers, such as this one. – Bernard Nov 16 '15 at 22:19