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

Question

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.

Answer 1

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