SentientMathModular arithmetic calculator ↗
← Modular arithmetic calculator

Solve a linear congruence

To solve ax ≡ b (mod n), find d = gcd(a, n). Solutions exist if d divides b. When they exist, there are d distinct solutions among the residues 0 through n − 1.

Two solutions modulo 14

For 6x ≡ 8 (mod 14), the divisor is 2. Divide the coefficient, right side, and modulus by 2 to get 3x ≡ 4 (mod 7). The inverse of 3 modulo 7 is 5, so x ≡ 20 ≡ 6 (mod 7).

Modulo 14, the two representatives are 6 and 13. Both give remainder 8 when multiplied by 6.

A modular inverse

Find the inverse of 7 modulo 30. The Euclidean divisions are 30 = 4 × 7 + 2 and 7 = 3 × 2 + 1. Substituting back gives 1 = 13 × 7 − 3 × 30, so the inverse is 13 modulo 30.

No solution modulo 14

In 6x ≡ 7 (mod 14), the same gcd is 2. An even product and an odd right-hand side cannot differ by a multiple of 14.

A negative input

The least nonnegative residue of −7 modulo 5 is 3 because −7 = (−2) × 5 + 3. This is the representative between 0 and 4.

Try the examples in SentientMath →

See MIT OpenCourseWare’s modular arithmetic lecture.