3
$\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$
5
$\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$
  • $\begingroup$ thanks for replying. Your answer is a lot simpler. Will this subtracting/adding always work out the problem? $\endgroup$ – Tehmas Dec 7 '14 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$ – Fmonkey2001 Dec 7 '14 at 13:36
  • $\begingroup$ Ahan. But you didn't even use the inverse(-2). Was it a useless step? @_@ $\endgroup$ – Tehmas Dec 7 '14 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$ – Fmonkey2001 Dec 7 '14 at 13:48
  • $\begingroup$ Thanks Fmonkey2001. :) Your method is truly simpler and thanks for replying to other questions as well. $\endgroup$ – Tehmas Dec 7 '14 at 14:43
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$
  • $\begingroup$ Taussig, thank you for replying. I don't understand this: "Observe that −6≡1(mod7) and that −8≡6(mod7)." $\endgroup$ – Tehmas Dec 7 '14 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$ – N. F. Taussig Dec 7 '14 at 19:27
1
$\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$
  • $\begingroup$ kingW3, thank you for answering. Can you please elaborate step 3? $\endgroup$ – Tehmas Dec 7 '14 at 13:15
  • 1
    $\begingroup$ @Tehmas: $8 \equiv 1\pmod 7$. $\endgroup$ – user 170039 Dec 7 '14 at 13:16
  • $\begingroup$ @Tehmas Edited,you can also look the comment below you $\endgroup$ – kingW3 Dec 7 '14 at 13:25
  • $\begingroup$ I apologize for repeatedly asking about step 3 but what did you do there now? −6x≡−1−7 $\endgroup$ – Tehmas Dec 7 '14 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$ – Fmonkey2001 Dec 7 '14 at 14:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.