If $$\forall_m ax + b \equiv 0 \mod m$$ has solution then show that $ ax + b = 0$ has integer solution
I know the fact that if $a,b \in \mathbb Z, a \neq 0, \ m \in \mathbb N, d = gcd(a,m)$ then congurency $$ax \equiv b \mod m$$ has $d$ solutions $x$ from set $\left\{0,1,2,…,m-1 \right\}$ when $d|b$ and without solutions in other case but I am not sure if that theorem is helpful here…
I have tried to start deduction in that way
let $d_m = gcd(a,m)$. From task it follows that if
$$ \forall_m ax \equiv b \mod m $$ has solution then
$$ d_m = gcd(a,m) | b $$ but I stucked here – I am not sure what does it exactly give me.
Best Answer
The way you stated the problem is incorrect i.e., no matter the choice of $a$ and $b$ there is always an $x$ that satisfies thge condition $ax +b \equiv_m b$ for all $m$; namely $x=0$. Did you mean to write $ax +b \equiv_m 0$ for all $m$?
We first show the If direction--assuming that you intended to write $ax +b \equiv_m 0$ for all $m$ that is: To be more precise, you are assuming the following: given $a$ and $b$, there is an $x$ such that $ax +b \equiv_m 0$ for all $m$.
So let $x$ be such that $ax +b \equiv_m 0$ for all $m$. But then let $m$ be the smallest prime larger than $|ax+b|$. Then $ax+b \equiv_m 0$ implies that $ax+b = rm$ for some integer $r$. This and the condition that $|ax+b| < m$, imply that $r$ must be 0 [as $|ax+b| > m$ for all $r \not = 0$], and so $ax+b$ must actually be 0 i.e., $a,x$, and $b$ satisfy the equation $ax+b = 0$.
So we now show the only if direction: If $a,x,$ and $b$ satisfy $ax +b = 0$ then by modding both sides of the equation $ax+b=0$ by any integer $m$ it follows that $ax+b \equiv_m 0$.
ETA: In fact, for the "if" direction, you can assume something weaker: If, for each integer $m$, there is an integer $x$ (which here is allowed to vary as $m$ does) that satisfies $ax + b \equiv_m 0$, then there is an integer $x$ that satisfies $ax+b=0$.
Indeed, we prove the "if" direction by assuming that $a$ and $b$ are such that there is no $x$ satisfying $ax+b=0$, and use this to show that there is an $m$ such that there is no solution to $ax+b \equiv _m 0$. Indeed, if there is no solution to $ax +b = 0$, then $a \not | b$ [indeed, otherwise put $x =-\frac{b}{a}$]. Then take $m = ab$. If there is an $x$ satisfying $ax+b \equiv_0 m$ then there is an $x$ satisfying $ax = b+mr$ for some integer $r$ which would imply that $x=\frac{b+mr}{a}$ is an integer, which (as $\frac{mr}{x}$ is an integer) would imply that $\frac{b}{a}$ is an integer, which contradicts the assumption that $a \not | b$. So if $a \not | b$ then for $m=ab$ there is no $x$ satisfying $ax+b \equiv _m 0$