# Solution to linear congruences

This document states the following theorem:

Let $m>1$, $a$ and $b$ be integers. Then $ax \equiv b \pmod m$ has a solution if and only if $gcd(a, m)$ divides $b$.

I thought $ax \equiv b \pmod m$ has a solution if and only if $gcd(a, m)=1$. Isn't $ax \equiv b \pmod m$ solved by $x \equiv a^{-1}\cdot b \pmod m$? If $gcd(a, m) \neq 1$, then the inverse doesn't exist.

• $a$ is not inverse of $x$ unless $b=1$. See slaso en.wikipedia.org/wiki/Linear_congruence_theorem – lab bhattacharjee Sep 28 '13 at 18:36
• If $\gcd (a,m) = d > 1$, and $d \mid b$, then you can divide the congruence by $d$ to get $a'\cdot x \equiv b' \pmod{m'}$. The solutions of both congruences are the same. – Daniel Fischer Sep 28 '13 at 18:37

What you might be recalling is the fact that $a$ is not the inverse of $x$ unless $\gcd (a, b) = 1$.
IF $d = \gcd (a,m) > 1$, then $d\mid b$ and $${\small \dfrac ad }x\equiv {\small \dfrac bd} \left(\mod \small\frac md\right)$$
• $4x \equiv 2 \pmod {6}$: $\gcd(4, 6) = 2$, and that divides $2$, so we can solve: now $$\frac 42 x \equiv \frac 22 \pmod {6/2} \iff 2x \equiv 1 \pmod{3}$$ and a solution to this congruence will be a solution for the first. Now we are working with a congruence for which there is a unique inverse of $2$. – Namaste Sep 29 '13 at 16:26
Suppose that $gcd(a,m)=d$ and $d\mid b$. Then, you have $\frac{a}{d}x\equiv \frac{b}{d} \mod \frac{m}{d}$. Here $gcd(\frac{a}{d},\frac{m}{d})=1$ and therefore the last congruence has a solution $y$ and therefore $dy$ is the solution of ${a}x\equiv {b} \mod {m}$.