1
$\begingroup$

Here are some of the known definitions:

$$a \equiv b \pmod m$$ $$a -b =km \Rightarrow a=km+b$$

Now we also have:

$$ax = b \pmod m \Rightarrow ax+my=b$$

I'm having a little trouble relating all of this because if we take for example: $3x \equiv 7\pmod 4$ and if we use : $a -b =km $, shouldn't we have: $3x-4k=7$ for some integer $k$ ? I'm trying to see how $ax+my=b$ comes to be...

$\endgroup$
  • $\begingroup$ And there are such integers, such as $x=1, k=-1$, and many other pairs. $\endgroup$ – André Nicolas Sep 18 '13 at 18:07
1
$\begingroup$

If $a\equiv b\pmod m,$

$ax\equiv b\pmod m\equiv a=k\cdot m+a$ where $k$ is any integer

$\implies a(x-1)=k\cdot m\implies x-1=\frac{k\cdot m}a$

If $\frac a A=\frac mM=d$ where $d=(a,m)$

$x-1=k\frac MA\equiv0\pmod M$ as $A$ must divide $k$ as $(A,M)=1$

$$\implies x\equiv 1\pmod{\frac m{(m,a)}}$$

$\endgroup$
  • $\begingroup$ Here $a=3,m=4\implies (a,m)=1$ $\endgroup$ – lab bhattacharjee Sep 18 '13 at 18:14

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.