= Solution
Let $d=\gcd(a,m)$. If the <linear congruence> $ar\equiv b\pmod m$ holds, then $b=ar-ms$ for some <integer> $s$, so the <greatest common divisor> $d$ divides $b$. Conversely, <Bézout's identity> gives <integers> $u,v$ with $au+mv=d$. If $b=dj$, multiply this identity by $j$ to obtain $a(uj)\equiv b\pmod m$. Hence
$$
\boxed{ar\equiv b\pmod m\text{ has a solution}\iff d\mid b.}
$$
For the number of solutions, write $a=da'$, $m=dm'$ and $b=db'$. The <linear congruence> becomes $a'r\equiv b'\pmod {m'}$, where $a',m'$ are <coprime integers>. Multiplication by $a'$ is invertible modulo $m'$ by <Bézout's identity>, so the solutions form one <residue class> $r\equiv r_0\pmod {m'}$. Modulo $m=dm'$, these are exactly
$$
\boxed{r_0,\ r_0+m',\ldots,r_0+(d-1)m'.}
$$
They are distinct: if two have the same <residue class> modulo $m$, then $dm'$ divides $(j-\ell)m'$, forcing $d\mid j-\ell$; with $0\leq j,\ell<d$, this forces $j=\ell$. Every other solution differs from $r_0$ by a multiple of $m'$, so these exhaust the $d$ solutions.
Finally,
$$
b(m/d)\equiv0\pmod m\iff dm'\mid bm'\iff d\mid b.
$$
Combining this with the existence criterion gives the requested equivalent <modular congruence>.
Back to article page
