modular arithmetic - 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.

Answer

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