Linear congruence

Summary

A linear congruence is a congruence $a x \equiv b \pmod n$, with given integers $a$ and $b$ and a positive integer $n$. Its solutions are the integers $x$ that satisfy it. Let $d = \gcd(a, n)$. The congruence has a solution if and only if $d \mid b$. In this case, the solutions form exactly $d$ residue classes modulo $n$, and one residue class modulo $n / d$.

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}$.

Explanations

L1 human

A linear congruence is a linear equation in modular arithmetic. To solve $2 x \equiv 3 \pmod 5$, find the inverse $3$ of $2$ modulo $5$, and multiply: $x \equiv 9 \equiv 4 \pmod 5$. Check: $2 \cdot 4 = 8 \equiv 3 \pmod 5$.