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

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?

• difference is a multiple of 7 – Will Jagy Feb 12 '15 at 4:04
• Since $-2$ is the inverse of $3$ modulo 7 (which you can verify since $(-2)(3)=-6 \equiv 1$ (mod 7)), multiply both sides of the congruence $3x \equiv 4$ (mod 7) by $-2$ to obtain... what? – Ducky Feb 12 '15 at 4:06
• And the congruence $x\equiv 6$ (mod 7) means that $x-6$ is divisible by $7$, by definition. I think of it as meaning that $x$ is $6$ higher than some multiple of $7$ (hence it might be 13, 27, 34, etc). – Ducky Feb 12 '15 at 4:10
• @WillJagy I get that -6 ≡ 1 (mod 7) means difference is a multiple of 7. But what does x ≡ -8 ≡ 6 (mod 7)? mean? – committedandroider Feb 12 '15 at 5:09
• It means $-8-6 = -14 = (-2) \cdot 7$ is a multiple of 7. Or $6 - (-8) = 14$ – Will Jagy Feb 12 '15 at 5:11

## 2 Answers

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

• For Congruence product rule A≡a, and B≡b ⇒ AB≡ab (mod m), how is −2⋅3 $\equiv$ 1? – committedandroider Feb 12 '15 at 5:15
• @com Use $\ {-}2\equiv -2\,$ times $\,3x\equiv 4,\,$ which scales the latter by $\,-2\,$ as in the answer. – Bill Dubuque Feb 12 '15 at 5:19
• Can you elaborate on that? I thought the whole point of this $\equiv$ sign was to go along with a modulus expression like 9 $\equiv$ 4(mod 5) is saying the difference between 9 and 4 is a multiple 5. What does it mean when you don't have the modular expression? – committedandroider Feb 12 '15 at 5:23
• @com Some writers omit the $\!\pmod m\,$ if the modulus is clear from the context. That is not advised if one is working with congruences wrt more than one modulus (possible ambiguity). – Bill Dubuque Feb 12 '15 at 5:25
• I don't get how -2 * 3 is scaled to 1 and -2 * 4 is scaled to 6? – committedandroider Feb 12 '15 at 5:32

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

• Quick question: Why did you break −24 into -28 + 4? – committedandroider Feb 13 '15 at 3:31
• So -8 + 7n would also be a solution then? – committedandroider Feb 13 '15 at 8:21
• I broke $-24$ into $-28 + 4$ since $-28 = -4 \cdot 7$, so $-28 \equiv 0 \pmod{7}$, from which we can conclude that $-24 \equiv -28 + 4 \equiv -4 \cdot 7 + 4 \equiv 4 \pmod{7}$. In answer to your second question, $-8 + 7n$ is another way of writing the solution. I wrote it in the form $6 + 7n$ since we usually express the solution of an equivalence modulo $m$ as a residue from the set $\{0, 1, 2, \ldots, m - 1\}$. For $m = 7$, this means we usually choose the appropriate residue from the set $\{0, 1, 2, 3, 4, 5, 6\}$ of remainders obtained when an integer $k = 7q + r$, with $0 \leq r < 7$. – N. F. Taussig Feb 13 '15 at 11:32
• Oh ok so both are accepted solutions then? But then isn't remainder defined as a value r that >= 0 and < m? Based off that I would think that my solution -8 + 7n isn't valid because I use a negative remainder and your solution is valid because you use a positive remainder, 6. – committedandroider Feb 13 '15 at 23:24
• The best way to think of it is that $-8$ is a member of the residue class of $6 \pmod{7}$ since $-8 = 6 - 2 \cdot 7$. By the residue class of $6 \pmod{7}$, I mean all integers $n$ that differ from $6$ by an integer multiple of $7$. Since $-8$ and $6$ are in the same residue class, the solution $-8 + 7m, m \in \mathbb{Z}$ is valid since it produces the same set of integers as $6 + 7n, n \in \mathbb{Z}$ (take $m = n + 2$). That said, if $n$ is an integer such that $n = qk + r$, with $0 \leq r < k$, we usually think of $n$ as belonging to the residue class of the remainder $r \pmod{k}$. – N. F. Taussig Feb 13 '15 at 23:53