Proof: By Induction

(related to Proposition: Existence and Number of Solutions of Congruence With One Variable)

By hypothesis, $a,b$ are integers, $m > 0$ is a positive integer. We first show that the solvability of the congruence is equivalent to $\gcd(a,m)\mid b.$



It remains to be shown that the congruence has exactly $\gcd(a,m)$ different solutions. * The congruence with one variable $(\ref{eq:E18453})$ has exactly one solution modulo $\frac{m}{\gcd(a,m)}.$ * Since $\gcd(a,m)\mid m$, there are $\gcd(a,m)$ as many solutions modulo $m.$

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