Linear congruence

Remarks

When $\gcd(a, n) = 1$, the unique solution modulo $n$ is $x \equiv a^{-1} b \pmod n$, where $a^{-1}$ is the modular multiplicative inverse of $a$. The congruence $a x \equiv b \pmod n$ is the same as the linear Diophantine equation $a x - n y = b$. For example, $6 x \equiv 4 \pmod{10}$ has $d = 2$. Its solutions are $x \equiv 4 \pmod 5$, that is, $x \equiv 4$ or $x \equiv 9 \pmod{10}$.