Stuck : Using inverses to solve linear congruences?

Question

Question : What are the solutions of the linear congruence 3x ≡ 4 (mod 7)?

Step 1 - We know that −2 is an inverse of 3 modulo 7.

Step 2 - Multiplying both sides of the congruence by −2 shows that

−2·3x ≡−2·4(mod7).

Step 3 - Because

−6 ≡ 1 (mod 7) - Equation 1

and −8 ≡ 6 (mod 7) - Equation 2

it follows that if x is a solution,

then x ≡ −8 ≡ 6 (mod 7).

---

In Step 3, I am unable to understand how Equation 1 and Equation 2 lead to the statement

x ≡ −8 ≡ 6 (mod 7).

Here are the conclusions I was able to derive from these facts,

-6 mod 7 = 1 mod 7

-8 mod 7 = 6 mod 7

(-1) is the inverse of 6 modulo 7

It'd be great if you can help me figure out what other conclusion I'm missing.

Answer 1

$$\begin{eqnarray} \overbrace{(-2)\,3}^{\large{\equiv -6\equiv\color{#c00}{\bf 1}}}x &\equiv& \overbrace{(-2)\,4}^{\large\equiv -8\equiv\color{#0a0}{\bf -1}}\pmod 7\\ \Rightarrow\quad\ \ \color{#c00}{\bf 1}\cdot x&\equiv& \color{#0a0}{\bf -1}\equiv 6\ \, \pmod 7 \end{eqnarray}$$

Above we applied the following fundamental

Congruence Product Rule $\rm\quad\ \, A\!\equiv a\ \Rightarrow\ Ab\equiv ab\ \pmod{\!n}\ \ \ $

when we made the inference $\ (-2)3 \equiv 1\,\Rightarrow\, (-2)3x \equiv 1\cdot x$

and also we used that congruence is an equivalence relation.

Answer 2

$x\equiv-8\pmod7$ comes from Step 2.

Answer 3

$-6$ and $1$ are in the same equivalence-class in $\mathbb{Z}_7$. In modulo arithmetic in the ring $\mathbb{Z}/n\mathbb{Z}$ (Z modulo nZ) you can add the modulus to any number and the numbers are still congruent to each other since they have the same residue when divided by $n$ because we've only added multiples of $n$ to the number. Thus, $$-6 \equiv -6 + 7 \equiv 1 \mod 7$$ Also then,

$$-8 \equiv -8 + 7 \equiv -1 + 7 \equiv 6 \mod 7$$

I find this to be a very weird way to solve the eqation

$$3x \equiv 4 \mod 7$$ We just have to find the inverse of $3$ in $\mathbb{Z}_7$, and since $7$ is prime, we know that $3^{-1} \mod 7$ exists. We would then use the extended eucledian algorithm (EEA) to compute that inverse.

\begin{aligned} \text{I} \quad 7 &\quad 0 && \\ \text{II} \quad 3 &\quad 1 &&\\ \text{I-2II} \quad1 &\quad 0-2\cdot 1 = -2 \equiv 5 \mod 7 \end{aligned} This we have $$3\cdot5 \equiv 1 \mod 7$$, thus $$3^{-1} \equiv 5 \mod 7$$. Multiplying both sides with the multiplicative inverse gives

$$3x \equiv 4 \mod 7 \quad |\cdot 3^{-1}$$ $$x \equiv 4\cdot 5\mod 7 $$ $$x \equiv 20 \mod 7$$ Now just reduce 20 to the smallest residue modulo 7 (subtract 7 two times) and we get $$x \equiv 6 \mod 7$$

Answer 4

In step 2, you have $$-2 \cdot 3x \equiv -2 \cdot 4 \pmod{7}$$ Since $-2 \cdot 3 = -6$ and $-2 \cdot 4 = -8$, we have $$-6x \equiv -8 \pmod{7}$$ Since $-6 \equiv 1 \pmod{7}$ and $-8 \equiv 6 \pmod{7}$, we may substitute $1$ for $-6$ and $6$ for $-8$ in the equivalence $-6x \equiv -8 \pmod{7}$ to obtain $$x \equiv 6 \pmod{7}$$

Answer 5

From equation 1,

$$\begin{align*} -6&\equiv 1&\pmod7\\ -6x&\equiv x&\pmod 7 \end{align*}$$

From step 2, $$\begin{align*} -2\cdot3x&\equiv -2\cdot4&\pmod7\\ -6x&\equiv -8&\pmod 7 \end{align*}$$

Combining with equation 2: $-8\equiv6\pmod7$, all of the below four are equivalent:

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