Diophantine equations in relation to modular arithmetic

Question

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

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

score 1 · Answer 1 · answered Sep 18 '13 at 18:07

1

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)}}$$

answered Sep 18 '13 at 18:07

lab bhattacharjee

274,582

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

Diophantine equations in relation to modular arithmetic

1 Answers1