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

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 :)

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

• thanks for replying. Your answer is a lot simpler. Will this subtracting/adding always work out the problem? – Tehmas Dec 7 '14 at 13:32
• yes you can always add multiples of $7$ (in this particular example) since $7\equiv0\pmod{7}$ so what you're doing is really just adding $0$ to the equation. More generally $a\equiv0\pmod{a}$ (just to make sure I don't confuse you and make you add $7$ to all mod equations lol – Fmonkey2001 Dec 7 '14 at 13:36
• Ahan. But you didn't even use the inverse(-2). Was it a useless step? @_@ – Tehmas Dec 7 '14 at 13:39
• It wasn't useless, it was just a different method to solving the same problem. You'd get the same answer if you did it your way. Just like @N. F. Taussig did you could always substitute the answer of $6$ back into the original equation to see that $x=6 \rightarrow 18\equiv4\pmod{7}$ – Fmonkey2001 Dec 7 '14 at 13:48
• Thanks Fmonkey2001. :) Your method is truly simpler and thanks for replying to other questions as well. – Tehmas Dec 7 '14 at 14:43

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

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

• Taussig, thank you for replying. I don't understand this: "Observe that −6≡1(mod7) and that −8≡6(mod7)." – Tehmas Dec 7 '14 at 13:43
• $-6 \equiv 1 \pmod{7}$ since both $-6$ and $1$ have remainder $1$ when divided by $7$. $-6 = -1 \cdot 7 + 1$, so $-6 \equiv 1 \pmod{7}$. Note that when you add $7$ to $-6$ you obtain $1$. Similarly, $-8 = -2 \cdot 7 + 6$, so $-8 \equiv 6 \pmod{7}$. – N. F. Taussig Dec 7 '14 at 19:27

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

• kingW3, thank you for answering. Can you please elaborate step 3? – Tehmas Dec 7 '14 at 13:15
• @Tehmas: $8 \equiv 1\pmod 7$. – user 170039 Dec 7 '14 at 13:16
• @Tehmas Edited,you can also look the comment below you – kingW3 Dec 7 '14 at 13:25
• I apologize for repeatedly asking about step 3 but what did you do there now? −6x≡−1−7 – Tehmas Dec 7 '14 at 13:47
• This was two steps in one. The first thing he did was to add $7$ to $-1$ to get $6$. The second part was a little bit harder to see. He added $7x$ to the left side since any multiples of $7$ are $0\pmod{7}$ Then after he did that he factored out the $x$to get $(7-6)x$ then he simplified that to just get $x$ – Fmonkey2001 Dec 7 '14 at 14:20