The method of finding integer solutions x to congruences of the form a x ≡ b (mod n), where a, b and n are given integers and congruence is taken modulo a positive integer n.

Principle

A congruence a x ≡ b (mod n) is solvable precisely when d = gcd(a,n) divides b; when solvable, reduce by d to an equivalent congruence with modulus n/d and use modular inverses on the reduced coefficient.

Demonstration

Example: solve 14 x ≡ 6 (mod 20). gcd(14,20)=2 divides 6, so divide through by 2 to get 7 x ≡ 3 (mod 10). The inverse of 7 modulo 10 is 3, so x ≡ 3·3 ≡ 9 (mod 10). Lifting back to modulus 20 gives two solution classes x ≡ 9 and x ≡ 19 (mod 20).

Misapplication

Attempting to invert a modulo n when gcd(a,n) ≠ 1 or ignoring the factor d that creates multiple residue classes produces incorrect uniqueness claims or lost solutions.

Consequence

Correct application yields all residue classes of integer solutions and a reduced congruence whose solution set is parametrized by the modulus n/d; it converts an existence test into constructive solutions used in algorithmic number theory.

Reversal

Instead of solving for x in a single linear congruence, consider the dual problem of characterizing a or n given observed residue classes, or replace linear congruence solving by solving nonlinear congruences such as quadratic ones, which require distinct criteria.

Boundary

Applies only to linear congruences with integer coefficients and integer modulus n>0; excludes nonlinear congruences, congruences over non-integer rings, and questions about solutions in rationals unless reduced to equivalent integer congruences.

Semantic Tension

Often conflated with solving linear equations over the ring Z/nZ as an abstract algebraic object; the tension is between algorithmic, constructive solution sets (explicit residue classes) and purely structural statements about modules over Z/nZ.

Synthesis

Solving linear congruences is the constructive process that tests divisibility by gcd(a,n), reduces the modulus accordingly, and either produces modular inverses where possible or parametrizes the complete set of integer residue classes that satisfy a x ≡ b (mod n).