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

I am having a problem when the LHS has an addition function; if the question is just a multiple of $$x$$ it's fine.

But when I have questions like $$3x+3$$ or $$4x+7$$, I don't seem to get the right answer at the end.

• Are you sure you're not overlooking just moving the $3$ over? – Andrew Chin Oct 3 at 16:39
• yeah thought of that obviously but didn't know how to treat a negative mod, but now I know. Thanks, mate!!! – Charan Presence Oct 3 at 16:45
• Welcome to Mathematics Stack Exchange. How would you solve $7x+3=1$ where $x$ is a real number? – J. W. Tanner Oct 4 at 7:43

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$$

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$$.

• Thank you so much, I just started learning this concept so a bit weak in the basics. The answer checks out CHEERS!!! – Charan Presence Oct 3 at 16:45

$$7x+3\equiv1\implies7x\equiv1-3=-2\equiv29\equiv60\equiv91\implies x\equiv13\pmod {31}.$$

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}$$

$$\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 -18}\!\!\!\!\!\!\!\! \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{-18}1}\$$ $$\ \leftarrow\ \text{easiest } {\it general }\ \text{ method}$$