0
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Always a good plan to remember with modular arithmetic: You can reduce things modulo $7$ right at the start, and this often simplifies things greatly (as in gimusi's answer). In other words, adding $294$ to both sides is an idea but is unnecessary work. You can reduce $294$ modulo $7$ immediately to save time. $\endgroup$ – Matt Aug 26 '18 at 19:33
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I think I see. $294$ is divisible by $7$, $44$ modulo $7$ gives us 2 remainder. What is the explanation behind this reasoning? $\endgroup$ – user575678 Aug 26 '18 at 19:35
  • $\begingroup$ When we work $\mod m$ we can reduce all the terms to the remainder $0\le r<m$. $\endgroup$ – user Aug 26 '18 at 19:37
  • $\begingroup$ Could we also say that $x = -3$? $\endgroup$ – user575678 Aug 27 '18 at 0:03
  • 1
    $\begingroup$ Yes of course all $x$ in the form $4+7k$ are solutions. Usually we use $4 \pmod 7$ but also $-3 \pmod 7$ is a correct result. $\endgroup$ – user Aug 27 '18 at 0:50
  • $\begingroup$ $2x \equiv 1$ can be solved a bit easier by replacing $1$ with a number that $2$ goes into. Since this is mod $7$, then just keep adding $7$. You only need do this once since $2x \equiv 1 \equiv 8$, so $x \equiv 4$ $\endgroup$ – steven gregory Feb 25 at 4:33
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy