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.