1
$\begingroup$

I'm having some troubles understanding the solution (going from step $2$ to step $3$) of this linear congruence equation. Here's the problem with the solution:

Solve the congruence $2x + 11 \equiv 7 \pmod 3$.

First, we reduce all the coefficients $\pmod 3$:

$$2x + 2 \equiv 1 \pmod 3. \tag{1}$$

Next, we add $1$ to both sides, using the fact that $2 + 1 \equiv 0 \pmod 3$:

$$2x \equiv 2 \pmod 3. \tag{2}$$

Finally, we multiply both sides by $2$, using the fact that $2 · 2 = 4 \equiv 1 \pmod 3$:

$$x \equiv 1 \pmod 3. \tag{3}$$

That is, any number in the set $\{\ldots, −5, −2, 1, 4, \ldots\}$ will solve the original congruence.


Like I said my problem is the step between $(2)$ and $(3)$. If I multiply both sides of $(2)$ by $2$ I get:

$$4x \equiv 4 \pmod 3.$$

Now, I understand that $4$ is congruent to $1 \pmod 3$ so the RHS "simplifies" to $1 \pmod 3$ but I don't understand why the LHS "simplifies" to $x$. Can someone help me with this?

$\endgroup$
3
  • $\begingroup$ Do you understand that $3x \equiv 0 \pmod{3}$? $\endgroup$ – quid Aug 22 '16 at 15:23
  • 1
    $\begingroup$ Note that by multiplying by 2, you have already used that 'going mod-3 preserves multiplication', i.e., if $a \equiv a' \pmod 3$ and $b \equiv b' \pmod 3$, then $ab \equiv a'b' \pmod 3$. Now use that once more: $1 \equiv 4 \pmod 3$, so $x \equiv 4x \pmod 3$. $\endgroup$ – Magdiragdag Aug 22 '16 at 15:26
  • 1
    $\begingroup$ $4x\equiv 1x=x\mod3$. $\endgroup$ – Bernard Aug 22 '16 at 15:26
2
$\begingroup$

By the Congruence Product Rule $\ 4\equiv 1\,\Rightarrow\, 4x\equiv 1x\ [\equiv\, x]$. Alternatively note that $\,2 \equiv -1\,$ and it is simpler to scale the congruence by by $-1,\,$ which amounts to simply negating it. More generally when the coef of $x$ is coprime to the modulus then we can compute its inverse by the extended Euclidean algorithm, then scale the congruence by the inverse to transform the coef of $x$ to be $1$.

Note that these solution steps for a linear congruence are the same as they are for linear equations on real numbers, i.e. isolate $x$ by adding and multiplying equal (equivalent) numbers to both sides. That these operations remain valid for congruences follows by the Congruence Sum & Product Rules in the linked post (both are unified when one studies rings in abstracr algebra, where congruences $\bmod n\,$ are reified algebraically in the quotient ring $\,\Bbb Z_n = $ integer $\bmod n)$

Remark $ $ Note also that you need to make it clear that the congruences are equivalent (and not simply that the former imply the latter) if you want to deduce that the obtained solution is actually a solution, i.e. you need to use bidirectional arrows $(\!\!\iff\!\!)$ not unidirectional $(\Rightarrow)$ connecting the congruences. The arrows go both ways because you used only invertible operations $\,(n\mapsto n+a\,$ and $\,n\mapsto bn\,$ for invertible $\,b).\,$ The arrows generally do not reverse if you use noninvertible operations (e.g. squaring), which may introduce extraneous solutions (in which case you'd need to verify that solution candidates are actually solutions).

$\endgroup$
2
  • $\begingroup$ This makes perfect sense know. The link you provided is also very helpful, thank you. $\endgroup$ – user347616 Aug 22 '16 at 16:10
  • $\begingroup$ See also this answer for more on extraneous rooots. $\endgroup$ – Bill Dubuque Sep 15 '20 at 7:57
1
$\begingroup$

$4x \equiv 1 \mod 3 \implies$

$4x - 1 = 3k; k \in \mathbb Z \implies$

$x + 3x - 1 = 3k \implies$

$x -1 = 3k - 3x = 3(k-x) \implies$

$x - 1 = 3j; j= (k-x) \in \mathbb Z \implies$

$x \equiv 1 \mod 3$.

====

This is always true. If $k \equiv a \mod N$ than $kV \equiv aV \mod N$ because $k \equiv a \mod N \implies k - a = mN$ so $kV - aV = mVN$. Works even if $x$ is a variable. $4 \equiv 1 \mod 3$ so $4x \equiv x \mod 3$. Easy-peasy. (Assuming $x$ is presumed to be solved for a congruency class.)

$\endgroup$
0
$\begingroup$

For the LHS you want $4x\equiv x\pmod 3$. This is true because $3$ divides $4x-x=3x$. (Recall the definition of modulo: "$a\equiv b\pmod n$" means "$n$ divides $a-b$".)

$\endgroup$
0
$\begingroup$

Notationally, it is simpler to use bar notation:

$\overline{2x+11}=\overline{7}=\overline{1}\Longrightarrow$

$\overline{2x}+\overline{11}=\overline{1}\Longrightarrow$

$\overline{2x}=\overline{1}-\overline{11}=\overline{-10}$ $=\overline{2}\Longrightarrow$

$\overline{x}=\overline{1}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy