# Solve linear congruence $25x -4 \equiv 9x +4 \pmod 8$

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!

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

• The $\Longrightarrow$ needs to be a $\iff$ for the proof to be correct. – Bill Dubuque Jan 16 at 23:28
• @BillDubuque thanks, I have edited. – A-Level Student Jan 16 at 23:28