0
$\begingroup$

This is an example from Discrete Mathematics and its Applications enter image description here

This is example 1 that this example references enter image description here

And here's Theorem 1 that the example references enter image description here

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?

$\endgroup$
  • 1
    $\begingroup$ difference is a multiple of 7 $\endgroup$ – Will Jagy Feb 12 '15 at 4:04
  • $\begingroup$ 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? $\endgroup$ – Ducky Feb 12 '15 at 4:06
  • $\begingroup$ 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). $\endgroup$ – Ducky Feb 12 '15 at 4:10
  • $\begingroup$ @WillJagy I get that -6 ≡ 1 (mod 7) means difference is a multiple of 7. But what does x ≡ -8 ≡ 6 (mod 7)? mean? $\endgroup$ – committedandroider Feb 12 '15 at 5:09
  • $\begingroup$ It means $-8-6 = -14 = (-2) \cdot 7$ is a multiple of 7. Or $6 - (-8) = 14$ $\endgroup$ – Will Jagy Feb 12 '15 at 5:11
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ For Congruence product rule A≡a, and B≡b ⇒ AB≡ab (mod m), how is −2⋅3 $\equiv$ 1? $\endgroup$ – committedandroider Feb 12 '15 at 5:15
  • $\begingroup$ @com Use $\ {-}2\equiv -2\,$ times $\,3x\equiv 4,\,$ which scales the latter by $\,-2\,$ as in the answer. $\endgroup$ – Bill Dubuque Feb 12 '15 at 5:19
  • $\begingroup$ 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? $\endgroup$ – committedandroider Feb 12 '15 at 5:23
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque Feb 12 '15 at 5:25
  • $\begingroup$ I don't get how -2 * 3 is scaled to 1 and -2 * 4 is scaled to 6? $\endgroup$ – committedandroider Feb 12 '15 at 5:32
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Quick question: Why did you break −24 into -28 + 4? $\endgroup$ – committedandroider Feb 13 '15 at 3:31
  • $\begingroup$ So -8 + 7n would also be a solution then? $\endgroup$ – committedandroider Feb 13 '15 at 8:21
  • $\begingroup$ 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$. $\endgroup$ – N. F. Taussig Feb 13 '15 at 11:32
  • $\begingroup$ 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. $\endgroup$ – committedandroider Feb 13 '15 at 23:24
  • $\begingroup$ 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}$. $\endgroup$ – N. F. Taussig Feb 13 '15 at 23:53

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.