Linear Congruence Calculator
Test cases replayed : 4 of 4 match · Methodology · No outside source listed
Enter whole numbers a, b and a modulus m. The calculator tells you whether ax ≡ b (mod m) has a solution and gives every solution as one residue class.
Result
Solution
Smallest non-negative solution x₀
- Solutions repeat every (m ÷ d)
- Number of solutions modulo m
- d = gcd(a, m)
Estimate for planning only, not tax, legal, financial or medical advice. This calculator uses the method explained on this page.
This browser did not allow copying. The sentence is in the box below, already selected: copy it with your keyboard or the menu.
How to use this calculator
Fill in the fields in this order; each step takes you to its field.
- Coefficient a (whole number): enter a number.
- Right-hand side b (whole number): enter a number.
- Modulus m (2 to 1,000,000): enter a number from 2 to 1,000,000.
- Read the result: Solution; the panel also shows Smallest non-negative solution x₀, Solutions repeat every (m ÷ d), Number of solutions modulo m and d = gcd(a, m).
How this calculator works
Linear congruence theorem: ax ≡ b (mod m) has a solution if and only if d = gcd(a, m) divides b. When it does, there are exactly d solutions modulo m.
Divide through by d: (a/d)x ≡ b/d (mod m/d). Now a/d and m/d share no factor, so a/d has an inverse modulo m/d, found with the extended Euclidean algorithm. Then x₀ = (b/d) × inverse, reduced modulo m/d.
Every solution is x = x₀ + k × (m/d) for any whole number k; the d values x₀, x₀ + m/d, …, x₀ + (d − 1)m/d are the distinct solutions modulo m.
Negative a or b are first reduced to their remainder between 0 and m − 1. Decimal entries are rounded to the nearest whole number.
Worked example
| Coefficient a (whole number) | 14 |
|---|---|
| Right-hand side b (whole number) | 30 |
| Modulus m (2 to 1,000,000) | 100 |
| Solution | x ≡ 45 (mod 50) |
|---|---|
| Smallest non-negative solution x₀ | 45 |
| Solutions repeat every (m ÷ d) | 50 |
| Number of solutions modulo m | 2 |
| d = gcd(a, m) | 2 |
Frequently asked questions
Why does 6x ≡ 4 (mod 9) have no solution?
gcd(6, 9) = 3, and 3 does not divide 4. Every value of 6x modulo 9 is 0, 3 or 6, so it can never equal 4.
How is this related to a modular inverse?
When gcd(a, m) = 1 and b = 1, the solution x₀ is the inverse of a modulo m: a × x₀ leaves remainder 1 when divided by m.
How do I check an answer?
Multiply a by x₀, subtract b and divide by m. The division must come out even. For 14x ≡ 30 (mod 100): 14 × 45 − 30 = 600, which is 6 × 100.