2
$\begingroup$

My question is somewhat related to this thread: How to solve congruence with two variables x and y

I can not post a comment to ask directly there, therefore I need to create this thread

Anyhow, as was pointed out in there,

  • $8x+8y≡x+y≡0\mod7$
  • $y≡−x\mod7$

My questions are:

  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?
  2. I assume you get rid of the $8$s simply by dividing the whole congruence by $8$?
  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?

Thanks in advance!

$\endgroup$
4
  • 1
    $\begingroup$ Actualy in that question its simply that $A \equiv B \pmod n \implies Ak \equiv Bk \pmod n$ for any $k$. We chose $4$ simply because it works. We could have multiplied by, say $3$ and gotten $6x + 6y \equiv -x - y \equiv 0 \pmod 7$ or by $5$ and gotten $10x + 10y \equiv 3x + 3y \equiv 0\pmod 7$ but those wouldn't work. $\endgroup$ – fleablood Jun 18 '19 at 20:44
  • 2
    $\begingroup$ What we can't do is $2x + 2y \equiv 0 \pmod 7$ so $2x \equiv -2y \pmod 7$ so $\frac {2x}2 \equiv \frac{-2y}2 \pmod 7$ without first verifying $\gcd(2,7) = 1$. For example if $x=2; y = 4$ and $4x + 4y \equiv 0 \pmod 8$ we can not conclude $4x \equiv -4y\pmod 0$ and $x \equiv -y \pmod 0$. $\endgroup$ – fleablood Jun 18 '19 at 20:50
  • $\begingroup$ @fleablood so we do take the 8 because 8≡1mod7? Kind of lost all in all $\endgroup$ – alps Jun 18 '19 at 21:07
  • $\begingroup$ Yes. $8 \equiv 1 \pmod 7$ and $4*2 = 8$ so $2x + 2y \equiv 0 \pmod 0\implies 4(2x+2y) \equiv 4*0\pmod 7 \implies 8x +8y \equiv 0 \pmod 7 \implies x + y \equiv \pmod 7$. But notice if $\gcd(k,n)\ne 1$ you can not find any $ak\equiv 1 \pmod n$ so you can not do $kx + ky\equiv 0 \pmod n\implies a(kx+ky)\equiv 0\implies akx + aky\equiv 0 \pmod n$ because $ak \not \equiv 1 \pmod n$ for any $a$. $\endgroup$ – fleablood Jun 18 '19 at 22:33
1
$\begingroup$
  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?

The Congruence Product Rule implies that congruences are preserved uder 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 coefficents 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 coefficient 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.

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

  1. 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). But it is essential to know the scope of such laws to avoid mistakes (e.g. such sum and product rules don't apply analogously to exponentiation). 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, 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 algebraically in the study of quotient rings - above the ring $\,\Bbb Z_7 \cong \Bbb Z\bmod 7 = $ integers modulo $7)$.

$\endgroup$
1
$\begingroup$

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$

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