Question 7.9.12

1. Find $11^{-1}\pmod{31}$. Show answer

   We can find the $s$-values as we do the Euclidean algorithm: \begin{align*} 31 - 2\times11 &= 9\\ &\equiv -2\times11 \pmod{31}\\ 11 - 1\times9 &= 2\\ &\equiv 11 -1\times(-2\times11) \pmod{31}\\ &\equiv 3\times11 \pmod{31}\\ 9 - 4\times2 &= 1 \\ &\equiv (-2\times11) - 4\times(3\times11) \pmod{31}\\ &\equiv -14\times11 \pmod{31} \end{align*} But by this point you’ve probably gotten sick of writing ‘$\times11 \pmod{31}$’ so many times, and abbreviated it somehow (mathematicians invent new notation all the time). I’ve chosen to write ‘$:-2$’ to mean ‘$\equiv -2\times11 \pmod{31}$’, for example, so I’d write out that whole thing as: \begin{align*} 31 - 2\times11 &= 9\quad:-2\\ 11 - 1\times9 &= 2\quad:1 - 1\times-2 = 3\\ 9 - 4\times2 &= 1\quad:-2 - 4\times3 = -14 \end{align*} Basically we’re noting down the number of $11$s that each remainder is equivalent to.

   Now we have \begin{align*} 11^{-1} &\equiv -14 \pmod{31}\\ &\equiv 17\pmod{31} \end{align*} If you’re unsure of your answer, you can check by finding $17\times11$ and making sure that it has a remainder of $1$ when divided by $31$.

   

2. Use this result to solve the equation $11x \equiv 5\pmod{31}$ for $100\le x \le 150$ Show hint

   Multiply both sides of the equation by the inverse of $11$.

   Show answer

   \begin{align*} 11 x &\equiv 5 \pmod{31}\\ x &\equiv 11^{-1}\times5 \pmod{31}\\ &\equiv 17\times5 \pmod{31}\\ &\equiv 85 \pmod{31}\\ &\equiv 23 \pmod{31} \end{align*} In the range $100$ to $150$, there are two solutions: $x = 116, 147$.