2
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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

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

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.