= Linear congruence
{title2=$ax\equiv b\pmod n$}
A linear congruence asks for the <integers> $x$ satisfying $ax\equiv b\pmod n$, where $a,b$ are <integers> and $n>1$. Let $d=\gcd(a,n)$ be their <greatest common divisor>. There are solutions exactly when $d$ divides $b$. When solutions exist, there are \b[exactly $d$ solution classes modulo $n$], obtained from one solution $x_0$ by
$$
x\equiv x_0+j\frac nd\pmod n,\qquad j=0,\ldots,d-1.
$$
The <divisibility> condition follows immediately from $ax-b=kn$: every common <divisor> of $a,n$ must divide $b$. Conversely, <Bézout's identity> constructs a solution when $d\mid b$. Differences between any two solutions obey $n\mid a(x-x_0)$, equivalently $n/d\mid x-x_0$, since $a/d$ and $n/d$ are <coprime>. This explains both the spacing and the number of solution classes.
For a complete example, solve $6x\equiv9\pmod{15}$. Here $d=3$ divides nine. Dividing the corresponding <divisibility> statement by three changes the <integer modulus> too:
$$
6x\equiv9\pmod{15}\iff2x\equiv3\pmod5.
$$
Because $2\cdot3\equiv1\pmod5$, multiplying by the <modular inverse> three gives $x\equiv9\equiv4\pmod5$. Lifting this class back to modulus fifteen yields \b[$x\equiv4,9,14\pmod{15}$]. Direct substitution gives $24$, $54$ and $84$, each with <remainder> nine after <division with remainder> by fifteen. By contrast, $6x\equiv10\pmod{15}$ has no solutions, because three does not divide ten.
\Image[/linear-congruence-solution-classes.png]
{title=Multiplication by six modulo fifteen hits residue nine three times and never hits residue ten}
This is why ordinary-looking <division> cannot be performed blindly in <modular arithmetic>. Reducing the equation and its <integer modulus> together keeps all solutions; retaining modulus fifteen after dividing by three would lose valid classes. When $d=1$, the <modular inverse> of $a$ exists and gives a unique class $x\equiv a^{-1}b\pmod n$. The <Euclidean algorithm> computes the <Bézout coefficients> needed for this construction. https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf[Moitra, MIT 18.200, Lecture 15, modular inverses and the extended Euclidean algorithm]{ref}
Back to article page
