2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ hint: if a is the inverse of b (mod m), then what is ab (mod m)? How about ab*x (mod m)? $\endgroup$ – userNaN May 8 '16 at 21:05
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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.