Can someone clarify the notation of x $\equiv$ -8 $\equiv$ 6 ($\bmod$ 7)

Question

This is an example from Discrete Mathematics and its Applications

This is example 1 that this example references

And here's Theorem 1 that the example references

Example 1 makes sense. We have to determine if the inverse of 3 modulo 7 exists first of all. It will exist based on theorem 1 if m > 1, which it is in this case bc m = 7 and if gcd(3, 7) is 1 - definition of relatively prime.

To determine if gcd(3, 7) is 1, you can use Euclid's Algorithm,

7 = 3(2) + 1

3 = 1(3) + 0

In this case, 1 is the gcd because it is last remainder before the remainder goes to zero. $\equiv$

Now you know the inverse exists. To find the actual inverse, you want the inverse to be in the form

a'a $\equiv$ 1 $\bmod$ m

where a' would be the inverse.

To do this, you would need to use Bezout's Theorem that gcd(a, b) = sa + tb, so from my work in Euclid's Theorem, you can see

7 = 3(2) + 1

-2(3) + 1(7) = 1

then

-2(3) - 1 = -1(7)

-2(3) $\equiv$ 1$\bmod$(7) which is in the form of a'a $\equiv$ 1 $\bmod$ m, so a' or the inverse of a modulo m is -2.

Here's where I get lost. In example 3, the author uses the result he got from the inverse to solve the linear congruence of 3x $\equiv$ 4(mod 7).

I understand that -6 $\equiv$ 1 ($\bmod$ 7) and -8 $\equiv$ 6 ($\bmod$ 7), but how does that lead to x $\equiv$ -8 $\equiv$ 6 ($\bmod$ 7)? What does that even mean?

Answer 1

$\qquad\ \ 3\,x\,\equiv\, 4 \pmod 7\ $ scaled by $\ {-2}\equiv 3^{-1}_{\phantom{I_{I_{I_I}}}} $ yields

$\smash[t]{\ \ \overbrace{-2\cdot 3}^{\Large\ \equiv\, \color{#c00}1}\,x\,\equiv\,\overbrace{-2\cdot 4}^{\Large\! \equiv\, \color{#0a0}6}\pmod 7}$

$\ \Rightarrow\ \color{#c00}1\cdot x\equiv \color{#0a0}6\pmod 7,\, $ where we've used the Congruence Product Rule to scale it.

Indeed $\ x\equiv 6\,\Rightarrow\, 3x \equiv 18\equiv 4\pmod 7$

Alternatively $\ x\,\equiv\ \dfrac{4}{3}\,\equiv\, \dfrac{-3}3\,\equiv\, {-}1\,\equiv\, 6 $

Beware $ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

Answer 2

You are trying to find solutions to the equivalence $3x \equiv 4 \pmod{7}$. What the author is saying is that both $-8$ and $6$ are solutions to the equivalence, which we can verify by direct substitution.

If we substitute $-8$ for $x$, we obtain \begin{align*} 3(-8) & \equiv -24 \pmod{7}\\ & \equiv -28 + 4 \pmod{7}\\ & \equiv -4 \cdot 7 + 4 \pmod{7}\\ & \equiv 4 \pmod{7} \end{align*} If we substitute $6$ for $x$, we obtain \begin{align*} 3 \cdot 6 & \equiv 18 \pmod{7}\\ & \equiv 14 + 4 \pmod{7}\\ & \equiv 2 \cdot 7 + 4 \pmod{7}\\ & \equiv 4 \pmod{7} \end{align*} Moreover, \begin{align*} -8 & \equiv -14 + 6 \pmod{7}\\ & \equiv -2 \cdot 7 + 6 \pmod{7}\\ & \equiv 6 \pmod{7} \end{align*} In fact, if $n \in \mathbb{Z}$, then $6 + 7n$ is a solution to the equivalence since \begin{align*} 3(6 + 7n) & \equiv 18 + 21n \pmod{7}\\ & \equiv 14 + 4 + 21n \pmod{7}\\ & \equiv 7(2 + 3n) + 4 \pmod{7}\\ & \equiv 4 \pmod{7} \end{align*} The author found the particular solution $-8$ (which corresponds to the choice $n = -2$). However, we usually wish to express the solution of an equivalence modulo $n$ as one of the residues $0, 1, \ldots, n - 1$. Since $n = 7$, the answer in the set of residues $\{0, 1, 2, 3, 4, 5, 6\}$ that is equivalent modulo $7$ to $-8$ is $6$.