Linear Congruences

Solve ax b n with inverses and the gcd condition.

The idea

A linear congruence asks for the residues $x$ modulo $n$ that satisfy $ax \equiv b \pmod{n}.$ Unlike the equation $ax = b$ over the rationals, we cannot solve it by dividing by $a$, and it may have no solutions, exactly one, or several.

An inverse takes the place of division. A residue $a$ has a modular inverse $a^{-1}$ when $a\,a^{-1} \equiv 1 \pmod{n}$, and such an inverse exists exactly when $\gcd(a, n) = 1$.

The gcd also decides solvability. Both $ax$ and every multiple of $n$ are multiples of $d = \gcd(a, n)$, so modulo $n$ the left side only ever reaches multiples of $d$: the congruence is solvable if and only if $d \mid b$.

Algorithm.

Algorithm: Solving a Linear Congruence Input: integers a, b and a modulus n Output: every residue x mod n with ax ≡ b (mod n), or NONE 1. d = gcd(a, n) 2. if d does not divide b, return NONE 3. divide a, b and n by d, giving a'x ≡ b' (mod n') // coefficient now coprime to modulus; d = 1 changes nothing 4. find the inverse (a')⁻¹ with a'(a')⁻¹ ≡ 1 (mod n') // exists since gcd(a', n') = 1 5. x ≡ (a')⁻¹b' (mod n') // multiply both sides by (a')⁻¹; unique mod n' 6. return the d residues x, x + n', ..., x + (d-1)n' // the solutions mod the original n

Ways to work on it

• Walkthrough. Modular inverse, solving, and the gcd solvability test.
• Practice. Solve a coprime linear congruence.
• Hardest. Handle gcd > 1: solvability and reduction.

Not sure where to start? Take the ten-question placement test.