Congruence system with same modulus and same variable? 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.
 A: 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.
A: Hint:
Multiply each congruence by the inverse mod. $8$ of the coefficient of $k$, and check if the answers are compatible.
A: 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.
A: 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).
