Solving $3x\equiv 4\pmod 7$

Question

I'm trying to learn about linear congruences of the form ax = b(mod m). In my book, it's written that if $\gcd(a, m) = 1$ then there must exist an integer $a'$ which is an inverse of $a \pmod{m}$. I'm trying to solve this example:

$$3x \equiv 4 \pmod 7$$

First I noticed $\gcd(3, 7) = 1$.

Therefore, there must exist an integer which is the multiplicative inverse of $3 \pmod 7$.

According to Bezout's Theorem, if $\gcd(a, m) = 1$ then there are integers $s$ and $t$ such that $sa+tm=1$

where $s$ is the multiplicative inverse of $a\pmod{m}$.

Using that theorem:

$\begin{align}7 = 3\cdot2 +1\\7 - 3\cdot2 = 1 \\-2\cdot3 + 7 = 1\end{align}$

$s=-2$ in the above equation so $-2$ is the inverse of $3 \pmod{7}$.

The book says that the next step to solve $3x \equiv 4 \pmod{7}$ is to multiply $-2$ on both sides.

By doing that I get:

$\begin{align}-2\cdot3x \equiv -2\cdot4 \pmod 7\\-6x\equiv -8 \pmod 7\end{align}$

What should I do after that?

I am working on this problem for hours.

Thanks :)

Answer 1

$$\begin{align} 3x\equiv4\pmod{7} & (\text{Original equation})\\3x\equiv -3\pmod{7} &(\text{Replaced 4 with -3(by subtracting 7)})\\x\equiv-1\pmod{7}& (\text{Divide each side by 3})\\ x\equiv6\pmod{7} &(\text{replaced -1 with 6 (by adding 7))} \end{align}$$

P.S.- The reason you can add or subtract $7$ is one of the properties of $\pmod{7}$. You can add or subtract multiples of $7$ to the number in front of the $mod$ without effecting the equation.

Answer 2

$$3x\equiv4\pmod{7}\\-6x\equiv -8\pmod{7}\\-6x\equiv-1-7\\-6x\equiv-1\pmod{7}\\(7-6)x\equiv-1\equiv6\pmod{7}$$

Answer 3

You have arrived at

$$-6x=-8\pmod{7}.$$

Now: $$-6x=-8\pmod{7} \underbrace{\iff}_{\mathrm{add}\: 7x=0\pmod{7}} 7x-6x=-8\pmod{7}\\ \iff x=-8\pmod{7}\underbrace{=}_{\mathrm{add}\: 14=0\pmod{7}}(2\cdot 7-8)\pmod{7}=6\pmod{7}.$$

Answer 4

You obtained

$$-2 \cdot 3x \equiv -8 \pmod{7}$$

Simplifying yields

$$-6x \equiv -8 \pmod{7}$$

Observe that $-6 \equiv 1 \pmod{7}$ and that $-8 \equiv 6 \pmod{7}$. Thus, we obtain

$$x \equiv 6 \pmod{7}$$

Check: If $x \equiv 6 \pmod{7}$, then $3x \equiv 3 \cdot 6 \equiv 18 \equiv 4 \pmod{7}$.