1
$\begingroup$

Given $a \equiv a'\pmod m$ and $b \equiv b' \pmod m$.

Prove that $ax \equiv b \pmod m$ and $a'x \equiv b' \pmod m$ are equivalent.

I understand I have to show that this modulo congruences have the same set of solutions. But what is solution?

$\endgroup$
1
  • 2
    $\begingroup$ You do not have to find the solutions to these. Just show that if some $x$ verifies the first, then it verifies the second, and reciprocally, if it verifies the second, then it verifies the first. $\endgroup$ – Vincent Dec 4 '16 at 15:49
1
$\begingroup$

Note $\ a\equiv a',\, b\equiv b'\,\Rightarrow\, ax-b\equiv a'x-b'\,$ by the Congruence Product and Sum Rules.

Therefore we conclude $\,ax-b\equiv 0\iff a'x-b'\equiv 0,\ $ i.e. $\ ax\equiv b\iff a'x\equiv b'$


Remark $\ $ Alternatively we can note that $\,f(a,b) = ax-b\,$ is a polynomial in $\,a,b\,$ with integer coefficients, therefore $\, a,b\equiv a',b'\,\Rightarrow\, f(a,b)\equiv f(a',b')\,$ by the Polynomial Congruence Rule.

$\endgroup$

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.