4
$\begingroup$

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

$\endgroup$

4 Answers 4

Reset to default
6
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ thanks for replying. Your answer is a lot simpler. Will this subtracting/adding always work out the problem? $\endgroup$ Commented Dec 7, 2014 at 13:32
  • 1
    $\begingroup$ 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 $\endgroup$ Commented Dec 7, 2014 at 13:36
  • $\begingroup$ Ahan. But you didn't even use the inverse(-2). Was it a useless step? @_@ $\endgroup$ Commented Dec 7, 2014 at 13:39
  • $\begingroup$ 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}$ $\endgroup$ Commented Dec 7, 2014 at 13:48
  • $\begingroup$ Thanks Fmonkey2001. :) Your method is truly simpler and thanks for replying to other questions as well. $\endgroup$ Commented Dec 7, 2014 at 14:43
2
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ kingW3, thank you for answering. Can you please elaborate step 3? $\endgroup$ Commented Dec 7, 2014 at 13:15
  • 1
    $\begingroup$ @Tehmas: $8 \equiv 1\pmod 7$. $\endgroup$ Commented Dec 7, 2014 at 13:16
  • $\begingroup$ @Tehmas Edited,you can also look the comment below you $\endgroup$ Commented Dec 7, 2014 at 13:25
  • $\begingroup$ I apologize for repeatedly asking about step 3 but what did you do there now? −6x≡−1−7 $\endgroup$ Commented Dec 7, 2014 at 13:47
  • 1
    $\begingroup$ 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$ $\endgroup$ Commented Dec 7, 2014 at 14:20
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Taussig, thank you for replying. I don't understand this: "Observe that −6≡1(mod7) and that −8≡6(mod7)." $\endgroup$ Commented Dec 7, 2014 at 13:43
  • $\begingroup$ $-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}$. $\endgroup$ Commented Dec 7, 2014 at 19:27

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.