I have the following problem
Argue if the following linear congruence is solvable, and if it is, list all the incongruent solutions.
$$ 25x -4 \equiv 9x +4 \pmod 8$$
My attempt
I know that if I have a linear congruence of the form
$$
ax +b\equiv 0 \pmod m \tag{1}
$$
then the above system is solvable if and only if $ax + my =b$ has integer solutions for $x$ and $y$, so my idea is to transform the congruence into something like $(1)$. Knowing that $a \equiv a \pmod k$ I get that
$$
4 – 9x \equiv4 -9x \pmod 8
$$
so I get
\begin{align*}
(25x -4) + (4 – 9x) &\equiv (25x -4) +(4 -9x) \pmod 8\\
16 x &\equiv 0 \pmod 8
\end{align*}
but since $16 x = 8(2x)$, the above equivalence holds true for any integer $x$. Now, since $\gcd(16,8) = 8$, we know that we have $8$ incongruent solutions (modulo $8$). Since a particular solution to the diophantine equation
$$
16x + 8y = 0
$$
is $x_0 = 1, y_0 = -2$, I know that the incongruent solutions will be
$$
x_0,\ x_0 + \frac{8}{\gcd(8,16)}, \ x_0 + \color{blue}{2}\frac{8}{\gcd(8,16)}, … ,\ x_0 + \color{blue}{7}\frac{8}{\gcd(8,16)}
$$
and since $\frac{8}{\gcd(8,16)} = 1$ the incongruent solutions turn out to be
$$
1, 1 + 1, 1+2, … 1+7 = 1,2,3…, 7,8
$$
I'm not sure if I solved the above congruence correctly. Could anyone tell me if my solution is correct? Or alternatively, can someone tell me where I made a mistake and how to correct it? Thank you!
Best Answer
Your solution is correct. I will outline a simpler method below. $$ 25x -4 \equiv 9x +4 \pmod 8$$ Note that $25x=3\times8x+x\equiv 0+x\equiv x\pmod8$ and similarly, $9x=8x+x\equiv 0+x\equiv x\pmod8$. So in fact your equation is $$x-4\equiv x+4\pmod 8\iff-4\equiv4\pmod8$$ which is true for all integer values of $x$.