Let $a$ and $n$ denote integers with $n \geq 2,$ and write $d = \gcd(a,n).$ Show that if $d|b$, then $ax \equiv b (\mod{n})$ has a solution.
One thing I am not certain about is whether $x$ has to be an integer. It is not specified in the problem.
Given that $d|a$ and $d|n,$ $c_1d = a$ and $c_2d = n$ for some integers $c_1,c_2.$
Suppose $d|b,$ that is, $dc_3 = b$ for some integer $c_3.$ So, $ax – b = dc_1x – dc_3 = d(c_1x – c_3).$ Since $n = dc_2,$ it remains to show that $c_2|c_1x – c_3$ for some $x.$ If $x = (c_2 + c_3/c_1),$ then $c_1x – c_3 = c_1c_2,$ and $c_2|c_1x – c_3.$ Hence, $ax \equiv b(\mod{n})$ has a solution, namely $x = c_2 + c_3/c_1.$ To put it differently, suppose $ax \equiv b(\mod{n})$ has no solution, that is, $n \not\vert ax – b$ for any $x.$ Hence, for all $x,$ it follows that for all $y,$ $c_2dy \neq c_1dx – b,$ or, for all $x,$ it follows that for all $y,$ $b \neq d(c_1x – c_2y).$ Therefore, there exists no integer $c_{1}x – c_{2}y$ such that $d(c_1x – c_2y) = b,$ and $d \not\mid b.$
Does this make sense? Thanks 🙂
Best Answer
Let $\gcd(a,n)=d$ and suppose $d\mid b$ then for some integer $k$ ,$b=kd$. $\gcd(a,n)=d\implies$ that for some integers $u,v$ we have $$au+nv=d$$ multiplying the above equation by $k$ we have $$a(ku)+n(vk)=kd=b$$ $$\implies a(ku)\equiv b\pmod n$$. Hence $ax\equiv b \pmod {n}$ has a solution $x=ku$