Linear Congruences: Solving ax ≡ b (mod m) Step by Step

A linear congruence is an equation of the form ax ≡ b (mod m), where a, b and m are integers, and we are looking for integer values of x that make the equation true. The symbol ≡ means "is congruent to", which is the modular-arithmetic way of saying that the left and right sides leave the same remainder when divided by m. In other words, x is a solution exactly when m divides the difference ax − b.

Linear congruences matter because they appear every time you need to divide or undo multiplication in modular arithmetic. They are used to find modular inverses, to solve calendar and scheduling problems, and to break numbers into pieces in number-theory puzzles. Cryptographic systems also rely on them, since finding a modular inverse is one of the building blocks of public-key cryptography.

Key Concepts

• Congruence notation: a ≡ b (mod m) means m divides a − b; the integer m is called the modulus.
• Linear congruence: ax ≡ b (mod m) with unknown x and given integers a, b and m (m > 1).
• Greatest common divisor: d = gcd(a, m) decides whether any solution exists at all.
• Solvability condition: ax ≡ b (mod m) has a solution if and only if d divides b.
• Number of solutions: when solutions exist, there are exactly d distinct solutions modulo m.
• Modular inverse: the special case ax ≡ 1 (mod m) has a solution exactly when gcd(a, m) = 1.

Formulas

• Solvability test: let d = gcd(a, m). A solution exists exactly when d divides b.
• Reduced congruence: divide through by d: (a/d)x ≡ (b/d) (mod m/d), where now gcd(a/d, m/d) = 1.
• One solution of the reduced congruence: x ≡ (b/d) · (a/d)^−1 (mod m/d), using the modular inverse.
• All d solutions: if x0 is one solution, the full set is x ≡ x0 + (m/d)·t for t = 0, 1, …, d − 1.
• Extended Euclidean algorithm: finds integers u, v with au + mv = d, and u is the inverse of a/d modulo m/d.

Worked Example

Solve 4x ≡ 6 (mod 10). Step 1: compute d = gcd(4, 10) = 2. Step 2: check the solvability condition — does 2 divide 6? Yes, so solutions exist, and there will be exactly 2 solutions modulo 10. Step 3: reduce the congruence by dividing everything by d = 2, giving 2x ≡ 3 (mod 5). Step 4: find the inverse of 2 modulo 5. Since 2 · 3 = 6 ≡ 1 (mod 5), the inverse is 3. Step 5: multiply both sides by 3: x ≡ 3 · 3 = 9 ≡ 4 (mod 5), so x0 = 4 is one solution. Step 6: generate all solutions modulo 10 using x = x0 + (m/d)·t with m/d = 5: for t = 0 we get 4, and for t = 1 we get 9. Verification: 4 · 4 = 16 ≡ 6 (mod 10) ✓ and 4 · 9 = 36 ≡ 6 (mod 10) ✓. The complete solution is x ≡ 4 (mod 5), i.e. x = 4 and x = 9 modulo 10.

Common Misconceptions

• "I can always divide both sides by a common factor." You cannot simply cancel a factor from ax ≡ b (mod m). If a factor divides a and b but not m, cancelling changes the congruence. Cancel a factor only from all three of a, b and m together, as the reduced-congruence formula does.
• "A linear congruence has at most one solution." Unlike ordinary equations, ax ≡ b (mod m) can have many solutions. With d = gcd(a, m) dividing b, there are exactly d solutions modulo m — two solutions in the example above, not one.
• "No solution means I made an arithmetic error." Sometimes there really is no solution. For example 6x ≡ 7 (mod 10) is impossible because gcd(6, 10) = 2 does not divide 7. Always test the solvability condition first.

Real-World Applications

• Modular inverses in cryptography: computing x ≡ a^−1 (mod m) is exactly solving ax ≡ 1 (mod m); RSA key generation needs this step.
• Calendar arithmetic: questions like "if today is Tuesday, what day is it 1000 days from now?" reduce to solving x ≡ offset (mod 7).
• Hashing and checksums: several checksum formulas undo multiplication modulo a constant using linear congruences.
• Scheduling puzzles: problems where events repeat every m days and every n days are solved by congruences before the Chinese Remainder Theorem combines them.

Linear congruences turn the familiar idea of solving ax = b into modular arithmetic. The key moves are the solvability test with d = gcd(a, m), reducing the congruence when d divides b, finding one solution with the modular inverse, and then listing all d solutions spaced (m/d) apart. Whenever a "no solution" case appears, check whether d really divides b before reworking your arithmetic.