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.

  • $\begingroup$ $a$ is not inverse of $x$ unless $b=1$. See slaso en.wikipedia.org/wiki/Linear_congruence_theorem $\endgroup$ – lab bhattacharjee Sep 28 '13 at 18:36
  • $\begingroup$ 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. $\endgroup$ – Daniel Fischer Sep 28 '13 at 18:37

See the entry in Wikipedia: "Linear congruence theorem."

What you might be recalling is the fact that $a$ is not the inverse of $x$ unless $\gcd (a, b) = 1$.

But here, we have that the following applies:

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

  • $\begingroup$ Can you give an example of a linear congruence where this is the case and how you would solve it? $\endgroup$ – Frank Epps Sep 29 '13 at 16:10
  • $\begingroup$ $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$. $\endgroup$ – 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.