Some equations in $\mathbb F_{37}$

Question

How to solve efficiently the equations:

1) $[17][b]=[21]$

2) $[17][b]=[1]$

in $\mathbb F_{37}$

Answer 1

Some ideas (doing arithmetic modulo $\;37\;$ all along):

$$\begin{align}&17=-20=(-4)\cdot5\\ &(-4)\cdot9=-36=1\implies (-4)^{-1}=9\\ &5\cdot15=75=1\implies ...\end{align}$$

Now finish the argument.

Answer 2

It's no different from usual algebra: if $a\ne0$, $$ ax=b \iff x=a^{-1}b $$ The only problem is to find $[17]^{-1}$, that is, an integer $r$ such that $$ [17][r]=[1] $$ This means $$ 17r+37s=1 $$ and you find $r$ and $s$ with the (reverse) Euclidean algorithm: \begin{align} \color{red}{37}&=\color{red}{17}\cdot 2+\color{red}{3}\\ \color{red}{17}&=\color{red}{3}\cdot 5+\color{red}{2}\\ \color{red}{3}&=\color{red}{2}\cdot 1+\color{red}{1} \end{align} so $$ \color{red}{1}=\color{red}{3}-\color{red}{2}= \color{red}{3}-\color{red}{17}+\color{red}{3}\cdot 5= -\color{red}{17}+(\color{red}{37}-\color{red}{17}\cdot2)\cdot 6= -13\cdot\color{red}{17}+6\cdot\color{red}{37} $$ Thus $r=-13$ and $[17]^{-1}=[r]=[-13]=[24]$.