Solving the congruence $7x + 3 = 1 \mod 31$?

Solution 1:

We have that

$$7x + 3 \equiv 1 \mod 31 \implies 7x\equiv -2\mod 31$$

Then we need to evaluate by Euclidean algorithm the inverse of $7 \mod 31$, that is

• $31=4\cdot \color{red}7 +\color{blue}3$

• $\color{red}7=2\cdot \color{blue}3 +1$

then

• $1=7-2\cdot 3=7-2\cdot (31-4\cdot 7)=-2\cdot 31+9\cdot 7$

that is $9\cdot 7\equiv 1 \mod 31$ and then

$$9\cdot 7x\equiv 9\cdot -2\mod 31 \implies x\equiv 13 \mod 31$$

Solution 2:

Hint: The congruence $7x+3\equiv 1\mod 31$ is the same as $7x\equiv -2\mod 31$ with $-2\equiv 29\mod 31$. Compute the inverse of $7\mod 31$ using the extended Euclidean algorithm. Then $x\equiv 7^{-1}\cdot 29\mod 31$.

Solution 3:

By Gauss's algorithm $\bmod 31\!:\,\ 7x\equiv -2\iff x\equiv \dfrac{-2}7\equiv\dfrac{-8}{28}\equiv\dfrac{-39}{-3}\equiv \,\bbox[5px,border:1px solid #c00]{13}$

Or by Inverse Reciprocity

$\bmod 31\!:\,\ \dfrac{-2}{7}\equiv \dfrac{-2-31\!\!\!\!\overbrace{\left[\dfrac{-2}{\color{}{31}}\bmod 7\right]}^{\large -2/3\,\equiv\,-9/3 \,\equiv\, \color{#c00}{-3\ }}}7\equiv\dfrac{-2-31[\color{#c00}{-3}]}7\equiv\dfrac{91}7\equiv\,\bbox[5px,border:1px solid #c00]{13}$

Or by the forward extended Euclidean Algorithm (and its fractional form)

$\ \ \ \ \begin{array}{rr} [\![1]\!] &31\, x\,\equiv\ 0 \\ [\![2]\!] &\ \color{#0a0}{7\,x\, \equiv -2}\!\!\!\\ [\![1]\!]-4\,[\![2]\!] \rightarrow [\![3]\!] & 3\,x\, \equiv\, 8 \\ [\![2]\!]-2\,[\![3]\!] \rightarrow [\![4]\!] & \bbox[5px,border:1px solid #c00]{x\, \equiv 13}\!\!\!\! \end{array}$

said multi-fractionally $\ \ \dfrac{0}{31} \overset{\large\frown}\equiv \color{#0a0}{\dfrac{-2}7} \overset{\large\frown}\equiv \dfrac{8}3 \overset{\large\frown}\equiv\,\bbox[5px,border:1px solid #c00]{\dfrac{13}1}\ $ $\ \leftarrow\ \text{easiest}\, {\textit general} \text{ method}$