solving $151x − 294 \equiv 44 \pmod{7}$

Question

I've solved normal congruence equations like $ax \equiv b \pmod{m}$ but now I am trying to solve $ 1 5 1 x − 294 \equiv44\pmod{7}$. How do I solve this one? Can I just add $294$ to both sides and solve as normal using Euclidean algorithm?

I read the answer by quanta in this question but it is still not clear to me.

Can anyone please elaborate more on this?

Thanks for any help.

Answer 1

We have that

$$151x − 294 \equiv 44 \pmod{7} \iff 4x-0\equiv 2 \pmod{7} \iff 2x\equiv 1 \pmod{7}$$

and by Euclidean algorithm we can find

$$4\cdot 2-1\cdot 7=1$$

therefore $4$ is the inverse of $2 \pmod 7$ and we find

$$4\cdot 2x\equiv 4\cdot 1 \pmod{7} \implies x\equiv 4 \pmod{7}$$

Answer 2

The first right thing to do is to simplify all coefficients and write them in the range of $\{0,1,2,3,4,5,6\}$, using Euclidian division.

$$151=21\times7 +4 \quad;\quad 294 = 42\times 7 \quad;\quad 44=7\times 6 + 2$$

So the equation is the same as

$$4x\equiv 2 \pmod{7}$$

All we need to do is find the inverse of $4\pmod{7}$. After a few tries, we find that it is $2$ since $2\times 4 \equiv 8 \equiv 1 \pmod{7}$. Hence, we get

$$x \equiv 2\times 2 \equiv 4\pmod{7}$$

as the answer of your equation.