The question, whether a congruence $ax(m)\equiv b(m)$ is solvable if $m=p$ is a prime number, has been positively answered above in the proposition cancellation of congruences. But how about the case, if $m$ is not a prime number? The following proposition answers this question.

Proposition: Existence and Number of Solutions of Congruence With One Variable

For a given positive integer $m > 0$ and given integers $a,b$ the congruence with one variable $$(ax)(m)\equiv b(m)$$ is solvable, if and only if $\gcd(a,m)\mid b,$ i.e. if and only if the greatest common divisor of $a$ and $m$ is also a divisor of $b.$ Moreover, if it is solvable, then it has exactly $\gcd(a,m)$ different solutions.

Proofs: 1

Proofs: 1 2 3 4

Thank you to the contributors under CC BY-SA 4.0!




  1. Landau, Edmund: "Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie", S. Hirzel, Leipzig, 1927
  2. Jones G., Jones M.: "Elementary Number Theory (Undergraduate Series)", Springer, 1998