Congruence system with same modulus and same variable?

Question

I have this particular problem: $$\begin{cases} 3k \equiv 2 \pmod 8 \dots(*) \\ 7k \equiv 2 \pmod 8 \dots(**) \end{cases} $$

I know that the solution for this is $k = 8q + 6$. I can find this easily if I solve one of the equations alone.

Now, let's assume I subtract $(*)$ from $(**)$. I get $4k\equiv0[8]$ and $k = 2q$, which isn't coherent.

For example, if I take $q = 2$ then $3k=12$, which does not satisfy $(*)$ (nor $(**)$).

I can't figure out where I messed up. Please help me to understand this.

Answer 1

You didn't mess up anywhere, except for your interpretation of what you did. The result that $k=2q'$ (I'm using a different letter to avoid confusion with the $q$ from $k=8q+6$) is correct — the solutions $k=8q+6$ indeed satisfy this property that you found: $$k=8q+6=2q', \quad \text{where} \quad q'=4q+3.$$

When you have two equations to begin with, and you combine them e.g. by subtracting, what you get is an implication but NOT an equivalent equation. In other words:

• each $k$ that satisfies the original system of equations also satisfies the new equation;
• but values of $k$ that satisfy the new equation do not have to satisfy the original system.

As an example, think of the usual system of equations that I'm sure you've seen before; say, something like: $$\begin{cases} 2x+3y=11, \\ 3x+4y=12. \end{cases}$$

When you subtract the first equation from the second, you'll get $$x+y=1.$$

Does it follow from the original system? Of course, it does. Is it equivalent to the original system? Definitely, NOT: the original system has a unique solution, while the new equation alone has infinitely many solutions (pairs $(x,y)$ that satisfy it). You would need to put it together with one of the original equations (for example, as in the substitution method) to solve the original system completely.

Answer 2

Hint:

Multiply each congruence by the inverse mod. $8$ of the coefficient of $k$, and check if the answers are compatible.

Answer 3

You only get a necessary condition for $k$ being a solution.

Suppose you have \begin{cases} 3x=2 \\ 7x=2 \end{cases} If you subtract, you get $4x=0$, which implies $x=0$. Does this mean $x=0$ is a solution? Of course not, because $1$ satisfies neither equation. What you can say is “if $x$ is a solution, then $x=0$”.

But if you multiply the first equation by $2$ and subtract from the second, you find $x=-2$. So “if $x$ is a solution, then $x=-2$”, which is obviously a contradiction with the previous finding. Assuming a solution exists leads to a contradiction, so the system has no solution.

In your case you could indeed multiply the first congruence by $2$ and subtract from the second, getting $$ k\equiv -2\pmod{8} $$ Is this a solution? Let's check: if $k\equiv-2$, then $$ 3k\equiv-6\equiv2 \qquad 7k\equiv-14\equiv2 \qquad \pmod{8} $$ Hurray! The solution is good! Then $k=8q-2$ (or, equivalently, $k=8q+6$) are all the integer solutions.

In a different fashion, you can note that $3\cdot3\equiv1\pmod{8}$, so the first equation is equivalent to $$ 3\cdot3k\equiv3\cdot2\pmod{8} $$ that is, $$ k\equiv6\pmod{8} $$ Since $-7\equiv1\pmod{8}$, the second equation is equivalent to $$ -7k\equiv-2\pmod{8} $$ that is, $$ k\equiv-2\equiv6\pmod{8} $$ Thus the two equations are exactly the same.

Answer 4

It's not hard to see that, since "$2 \bmod 8$" is even and both $3$ and $7$ are not, thus $k$ must be even. So, say, we can find $m$ with $k=2m$.

Then we can divide through to find:
$3m\equiv 1 \bmod 4$
$7m\equiv 1 \bmod 4$

...which are of course the same equivalence, giving $m\equiv 3 \bmod 4$ and so $k\equiv 6 \bmod 8$ (which solves as $k=8q+6$ for any $q\in \Bbb Z$ as stated).