Finding $7$ inverse modulo $11$

Question

I'm trying to find the inverse of $7$ modulo $11$. From what I understand, the steps are:

\begin{align} &11 = 1(7) + 3 \\ &7 = 2(3) + 1 \\ \end{align}

From here, you work backwards

\begin{align} 1 &= 7 - 2(3) \\ &= 7 - 2(11-7) \\ &= 7 - 2(11) + 2(7) \\ &= -2(11) + 3(7) \end{align}

Now, here I see that $7$'s inverse modulo is $3$ but there can be many more (right?). The answer book says that one of them is $8$. Now, assuming my previous steps are correct; how do I find the others?

Thanks!

EDIT:

\begin{align} 11 &= 1(7) + 4 \\ 7 &= 1(4) + 3 \\ 4 &= 3(1) + 1 \end{align}

Then,

\begin{align} 1 &= 4 - 1(3) \\ &= 4 - 1(7 - 4) \\ &= 4 - 7 + 4 \\ &= -7 + 2(4) \\ &= -7 + 2(11 - 7)\\ &= -7 + 2(11) - 2(7) \\ &= 2(11) - 3(7) \end{align}

Answer 1

I believe, I have figured out how they arrived at $8$. My first mistake was the incorrect euclidean algorithm execution. So, below is the correct one:

\begin{align} 11 &= 1(7) + 4 \\ 7 &= 1(4) + 3 \\ 4 &= 3(1) + 1 \end{align}

Then we work backwards

\begin{align} 1 &= 4 - 1(3) \\ &= 4 - 1(7 - 4) \\ &= 4 - 7 + 4 \\ &= -7 + 2(4) \\ &= -7 + 2(11 - 7)\\ &= -7 + 2(11) - 2(7) \\ &= 2(11) - 3(7) \end{align}

From here, we can use the following:

\begin{align} x &= x_0 + jb \quad\quad j \in \mathbb{Z} \\ y &= y_0 + ka \quad\quad k \in \mathbb{Z} \\ \end{align}

In this case, we have $x = -3 + 11j$ and $y = 2 + 7k$. Ignoring $y$, we can yield $8$ with $j=1$.

Answer 2

Hint $\ {\rm mod}\ 11\!:\ 7\equiv -\color{#c00}4,\,$ and $\ {\rm mod}\ 2n\!-\!1\!:\ 2n\equiv 1\,\Rightarrow\, 4n^2\equiv 1\,\Rightarrow\,\color{#c00}4^{-1}\equiv n^2$

Answer 3

Hint: $7x \equiv 1 \equiv 56 \;\; \text{mod} \; 11$ and $\gcd(7,11)=1.$

Answer 4

$8 \times 7 = 56$

$56 \ \mbox{mod $7$} = 1$

Done.

$7^{-1} \ \mbox{mod $11$} = 8$

Answer 5

You can use the Fermat's theorem to find the modular inverse. $$a^p \equiv a \mod p$$ Multiply $a^{-2}$ on both sides: $$\implies a^{p-2} \equiv a^{-1} \mod p$$

Hence, $a$ inverse modulo $p$ is $a^{p-2} \mod p$

In your case,

$7^9 \mod 11 \equiv 49^4*7 \equiv 5^4*7 \equiv 9*7 \equiv 8$