Use of congruence arithmetic laws to solve linear congruences

Solution 1:

1. How do you get the scalar 4 in order to obtain $8x+8y$. Is it because $8≡1\mod7$ and therefore we need an $ 8$, $8/2 = 4$, and that's it? Or is there a totally different logic behind this step?

Congruences are generalized equations. In particular they enjoy many of the same properties that equations do, e.g. they remain true if we multiply both sides by the same (or congruent) numbers, and also if we add or subtract to both sides the same (or congruent) numbers. Let's examine these properties more closely to see how they yields answers to your queries.

The Congruence Product Rule implies that congruences are preserved under integer scalings, i.e.

$$ b\equiv c\!\!\pmod{\!n}\, \Rightarrow\, ab\equiv ac\!\!\pmod{\!n}$$

Thus the idea is to scale $\, 2x+2y\equiv 0\,$ by some integer $\,a\,$ to simplify it by making the coefficients smaller. Here we can make them $1$ because $2$ is invertible: $\,2a\equiv 1\equiv 8\iff a\equiv 4\pmod{\!7}.\,$ Therefore scaling by $\,4\equiv 2^{-1}$ simplifies both coefficients to $\,4\cdot 2\equiv 8\equiv 1,\,$ i.e.

$$ 2x+2y\equiv 0\!\!\pmod{\!7}\iff x+y\equiv 0\!\!\pmod{\!7}$$

Beware generally scaling yields only the direction $(\Rightarrow)$ but scaling by an invertible $\,a\,$ means the direction $(\Leftarrow)$ holds too (by scaling RHS by $\,a^{-1}\equiv 4^{-1}\equiv 2,\,$ which is obvious in this case). When the scale factor $\,a\,$ is not invertible then we need to check that the solutions of the scaled equations are not extraneous, i.e. they actually satisfy the original equation. Here is an extraneous example.

2. I assume you get rid of the $8$s simply by dividing the whole congruence by $8$?

No we used $\,8\equiv 1\,$ so $\,8x\equiv 1x\equiv x\,$ by the Congruence Product Rule.

3. In the final solution it is stated that $y=-x+7k$; to obtain the $-x$, can you simply move it on the other hand of the equation? So if we had anything else, could we just move it, like in normal equations?

The Congruence Sum Rule implies that congruences are preserved under integer shifts, i.e.

$$ b\equiv c\!\!\pmod{\!n}\, \Rightarrow\, a+b\equiv a+c\!\!\pmod{\!n}$$

Thus shifting $\,y+ x\equiv 0\,$ by adding $\,a\equiv -x\,$ to both sides yields $\, y\equiv -x\pmod{\!7}$.

Remark $\ $ In more advanced contexts we don't usually explicitly mention invocation of these basic congruence rules (laws). It's essential to know the scope of such laws to avoid mistakes (e.g. such sum and product rules don't apply analogously to exponentiation, but a more limited rule exists).

By induction, the congruence rules imply that we can replace arguments of sums and products by any congruent argument and we will obtain a congruent result (this is the congruence generalization of equalities being preserved upon replacing function arguments with equal arguments). In particular this holds true for all polynomial expressions (with integer coef's) because they are composed of sums and products (see the Polynomial Congruence Rule).

We can think of a congruence as a generalized equality. Generally congruences are equivalence relations that are also compatible with the ambient arithmetical operations (here addition and multiplication in a ring), which is the gist of the Sum and Product Rules, i.e. addition and multiplication operations don't depend on which congruence class rep is chosen (which implies that they induce well-defined operations on the congruence classes - which is reified structurally when one studies quotient rings, e.g. above the ring $\,\Bbb Z_7 \cong \Bbb Z\bmod 7 = $ integers modulo $7)$.

Solution 2:

For a slightly simpler answer to Bill Dubuques very complete answer.

1) The idea if $a \equiv b \mod n$ we can do $a*k \equiv b*k \pmod n$.

So if we want to solve $ax = b \pmod n$ we can do $(ak)x \equiv bk \pmod n$ and if $ak\equiv 1 \pmod n$ we will have solved $(ak)x \equiv 1*x \equiv x \equiv bk\pmod n$.

2) "I assume you get rid of the 8s simply by dividing the whole congruence by 8? "

I'm not sure what you mean but I don't think so. You aren't dividing anything. (For reasons I'll get into [see 3] division is one operation you can not safely do over modulo.)

Instead we are simply noting if $a \equiv b\pmod n$ and if we have $ax$ in an equation we can simply replace it with $bx$ because $ax \equiv bx \pmod n$.

To prove this.

If $a \equiv b \pmod n$ then $n|a-b$ and so $\frac {a-b}n = k $ for some integer $k$.

In other word $a-b = kn$ and $a = b + kn$ for some integer $k$.

In fact for my intuition $a \equiv b \pmod n$ is easier to think of as "$a$ and $b$ have the same remainder when divided by $n$". Or even easier, $a = b \pm$ some multiple of $n$.

So if $a = b + kn$ then $ax = bx + (kx)n$ and $ax -bx = (kx)n$ so (assuming $x$ is an integer) $n|ax-bx$ so $ax\equiv bx\pmod n$.

(Or in my words $ax = bx +(kx)n$ so $ax = bx \pm$ some multiple of $n$ so $ax \equiv bx \pmod n$).

3) Yes. You can move things over to each side of the equation.

Note:

$A \equiv B + K \pmod n \iff A = B + K \pm$ some multiple of $n$.

So

$A - K = (B+K) - K \pm$ some multiple of = B \pm$ some multiple of $n$

so

$A-K = B\pmod n \iff A-K = B \pm$ sumple multiple of $n$.

........

We can also multiply both sides by a constant.

$A \equiv B \pmod n \iff A = B \pm$ some multiple of $n$

$Ak \equiv Bk \pmod n \iff Ak = Bk \pm$ $k$ times some multiple of $n = Bk \pm$ another multiple of $n$.

...

But we can NOT do division.

$A \equiv B \pmod n \implies$

$A = B \pm$ some multiple of $n\implies$

$\frac Ak = \frac Bk \pm$ $\frac {\text{some multiple of } n}k$.

$\not \implies\not \frac Ak = \frac Bk \pm$ some multiple of $n$ THIS STEP IS BAD.

$\implies \frac Ak \equiv \frac Bk \pmod n$