Computing an inverse modulo $25$

Question

Supposed we wish to compute $11^{-1}$ mod $25$. Using the extended Euclid algorithm, we find that $15 \cdot 25 - 34 \cdot 11 =1$. Reducing both sides modulo $25$, we have $-34 \cdot 11 \equiv 1$ mod $25$. So $-34 \equiv 16 $ mod $25$ is the inverse of $11$ mod $25$.

im realy confused about this problem, can someone go over this please and explain how this is done

Answer 1

Note that $25 | 15 \cdot 25$, so $15 \cdot 25 \equiv 0 \pmod{25}$. On the other hand, we see that

$$1 \equiv -15 \cdot 25 - 34 \cdot 11 \equiv 0 + (-34) \cdot 11 \pmod{25}$$

Finally,

$$-34 \equiv -34 + 50 \equiv 16 \pmod{25}$$

so we can rewrite the above as

$$1 \equiv 16 \cdot 11 \pmod{25}$$

and $16$ is the desired inverse.

---

Note that by direct computation,

$$16 \cdot 11 = 176 = 7 \cdot 25 + 1$$

---

Alternatively, we can use the Euclidean algorithm and find that

\begin{align*} 25 &= 2 \cdot 11 + 3 \\ 11 &= 3 \cdot 3 + 2 \\ 3 &= 1 \cdot 2 + 1 \end{align*}

Thus,

\begin{align*} 1 &= 3 - 1 \cdot 2 \\ &= 3 - 1 \cdot (11 - 3 \cdot 3) = 4 \cdot 3 - 1 \cdot 11 \\ &= 4 \cdot (25 - 2 \cdot 11) - 1 \cdot 11 = 4 \cdot 25 - 9 \cdot 11 \end{align*}

So $1 \equiv -9 \cdot 11 \equiv 16 \cdot 11 \pmod{25}$ as before.

Answer 2

What do we understand under $11^{-1} (\mod 25)$? We want to find such number $x\in \mathbb Z_{24}$ that $11x=1(\mod 25)$.

This leads to the equation $11x=25k+1$, or $x=\frac{25}{11}k+\frac{1}{11},k\in\mathbb Z$

Now let's find $k$:

Since $25k+1$ is divisible by $11$, one of $k$'s is $k=-4$ that yields to $x=-9$

But $-9 \equiv 16 (\mod 25)$.

The answer is $16$.

Answer 3

The general method by using Euclid's algorithm can be seen in the following calculation.

                0
 25             1
 11    2    2   2
  3    3    3   7
  2    1    1   9
  1    2    1  16
  0         1  25

We start column 1, with the number we wish to divide, here to find 1/11 of 25. Dividing 11 into 25 gives '2' (to the right), and 3 (below). We then divide 3 into 11, to get 3 (to the right), remainder 2 (below). This contines until we get a remainder of 0 in the first column.

The third column is the same as the second one, except we note that because the second column has an even number of items, and we want an odd number, we replace the last element $x$ by $x-1$ and $1$, so 2-1 and 1.

The fourth column always starts with 0,1. The next number is 2*1+0 = 2, 3*2+1=7, and so forth. It must end in the same as the first number in the first column (here 25), and the number immediately before it is the value of 1/11, mod 25.

A simple test shows that $11\times 16 = 176 \equiv 1 \pmod {25}$.

When the numbers are co-composite (ie not co-prime), the number immediately before the 0 in the first column is the LCM, and this is the result of the product of the second last in column 4, by the second in col 1.