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 🙂
Best Answer
$$\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.