Linear Congruence

Solve $ax\equiv b(\mathrm{mod}m)$ for $x$.

The theorem

Let $g=\gcd (a,m)$.

• If $g\nmid b$ → no solution.
• If $g\mid b$ → exactly $g$ solutions modulo $m$, forming an arithmetic progression with common difference $m/g$.

To find them: divide through by $g$,

$\frac{a}{g}x\equiv \frac{b}{g}(\mathrm{mod}\frac{m}{g}),$

where now $\gcd (a/g,m/g)=1$, so the inverse exists:

$x_0\equiv \frac{b}{g}\cdot {\left(\frac{a}{g}\right)}^{-1}(\mathrm{mod}\frac{m}{g}).$

The full solution set is $x_0+k\cdot \frac{m}{g}$ for $k=\mathrm{0..}g-1$.

Code

// all solutions of a*x = b (mod m), as {smallest solution, step}; {-1,-1} if none
pair<long long,long long> linearCongruence(long long a, long long b, long long m) {
    a = ((a % m) + m) % m;
    b = ((b % m) + m) % m;
    long long x, y;
    long long g = extgcd(a, m, x, y);
    if (b % g) return {-1, -1};
    long long mod = m / g;
    long long x0 = (__int128)(x % mod) * (b / g) % mod;
    x0 = (x0 % mod + mod) % mod;
    return {x0, mod};                       // solutions: x0, x0+mod, ..., x0+(g-1)*mod
}

The __int128 guards against overflow when $m$ is near $10^{18}$.

Systems of congruences

$x\equiv r_1(\mathrm{mod}{m}_1),x\equiv r_2(\mathrm{mod}{m}_2),\dots$

• Coprime moduli → CRT gives a unique solution modulo $\prod m_i$.
• Non-coprime moduli → merge pairwise. The system $x\equiv r_1(\mathrm{mod}{m}_1)$, $x\equiv r_2(\mathrm{mod}{m}_2)$ has a solution iff $\gcd (m_1,m_2)\mid (r_2-r_1)$, and then the merged congruence has modulus $\mathrm{lcm}(m_1,m_2)$.

// merge x = r1 (mod m1) and x = r2 (mod m2)
pair<long long,long long> crtMerge(long long r1, long long m1, long long r2, long long m2) {
    long long p, q;
    long long g = extgcd(m1, m2, p, q);
    if ((r2 - r1) % g) return {-1, -1};                 // inconsistent
    long long lcm = m1 / g * m2;
    long long t = (__int128)((r2 - r1) / g) * p % (m2 / g);
    long long r = ((__int128)m1 * t + r1) % lcm;
    return {(r % lcm + lcm) % lcm, lcm};
}

Fold this over a list of congruences to solve an arbitrary system, or report inconsistency.

Related equations

Equation	Method
$ax\equiv b(\mathrm{mod}m)$	this page
$ax+by=c$ over $\mathbb{Z}$	linear Diophantine
$x\equiv r_i(\mathrm{mod}{m}_i)$	CRT / the merge above
$x^2\equiv a(\mathrm{mod}p)$	quadratic residues, Tonelli-Shanks
$a^x\equiv b(\mathrm{mod}m)$	discrete logarithm
$x^k\equiv a(\mathrm{mod}m)$	discrete root
$f(x)\equiv 0(\mathrm{mod}{p}^k)$	solve mod $p$, then Hensel lift

Where it shows up

• Modular division — $b/a\mathrm{mod}m$ is exactly $ax\equiv b$.
• Cycle alignment — “two events repeat every $m_1$ and $m_2$ steps; when do they coincide?”
• Calendar and clock problems.
• Reconstructing a value from residues — CRT, used to avoid big-integer arithmetic by working modulo several primes and recombining.
• Frobenius / coin problems — feasibility of $\sum c_i{x}_i=W$ modulo the smallest coin.

The three-step recipe

1. Compute $g=\gcd (a,m)$.
2. If $g\nmid b$, report no solution.
3. Divide $a$, $b$ and $m$ by $g$, invert, and enumerate the $g$ solutions.

Forgetting step 3’s ”$g$ solutions” is the usual mistake — problems often ask for the count or for the smallest positive solution, and there is more than one.

See also: Modular Inverse · CRT · Linear Diophantine Equations