Calculator inputs
Enter a congruence in the form ax ≡ b (mod m). The solver checks solvability, reduces the equation, finds inverse-based solutions, and lists matching integers in your chosen range.
Example data table
| Equation | gcd(a, m) | Reduced form | Distinct residue solutions |
|---|---|---|---|
| 14x ≡ 30 (mod 100) | 2 | 7x ≡ 15 (mod 50) | 45, 95 |
| 9x ≡ 12 (mod 21) | 3 | 3x ≡ 4 (mod 7) | 6, 13, 20 |
| 8x ≡ 14 (mod 30) | 2 | 4x ≡ 7 (mod 15) | 13, 28 |
| 6x ≡ 5 (mod 15) | 3 | Not solvable | None |
Formula used
For a linear congruence ax ≡ b (mod m), first compute d = gcd(a, m).
- If d does not divide b, no solution exists.
- If d | b, divide the whole congruence by d to get a′x ≡ b′ (mod m′).
- Because gcd(a′, m′) = 1, the modular inverse of a′ exists.
- The reduced solution is x ≡ (a′)-1b′ (mod m′).
- The complete integer family is x = x0 + km′, where k is any integer.
- Modulo m, this produces exactly d distinct residue classes.
This calculator also normalizes negative values, displays the reduced equation, shows the inverse used, and lists matching integer values inside your chosen interval.
How to use this calculator
- Enter the coefficient a, right side b, and modulus m.
- Set a minimum and maximum value for x if you want actual integer matches inside a range.
- Press Solve Congruence to display the result above the form.
- Review the gcd test, reduced congruence, modular inverse, general solution, and residue classes.
- Use the CSV button for spreadsheet-style output and the PDF button for a shareable summary.
Frequently asked questions
1. What does the solver actually compute?
It solves linear congruences of the form ax ≡ b (mod m). The page checks solvability, reduces the equation, finds the inverse when possible, and reports every distinct residue class modulo the chosen modulus.
2. Why is the gcd of a and m important?
The gcd determines whether the congruence has any solution. A solution exists only when gcd(a, m) divides b. If that divisibility test fails, the congruence is inconsistent and no residue class can satisfy it.
3. Why can one equation have several answers?
When gcd(a, m) is greater than 1 and still divides b, the congruence produces multiple distinct residue classes modulo m. Those classes all belong to one repeating integer family with a smaller step size.
4. What happens with negative inputs?
Negative coefficients and right-side values are normalized into standard residues before solving. That keeps the arithmetic consistent while still preserving the original congruence and its full set of valid solutions.
5. What is the meaning of the least nonnegative solution?
It is the smallest solution x0 with 0 ≤ x0 < m′ for the reduced congruence. From that base value, every other integer solution is generated by adding multiples of the reduced modulus.
6. Why are range-based solutions useful?
Residue classes describe infinitely many integers. A bounded range helps you find the exact values that matter in homework checks, code testing, cryptography exercises, or modular scheduling problems.
7. What do the CSV and PDF downloads contain?
They export the computed summary, including the original equation, gcd result, reduced equation, inverse used, general solution, residue classes, and range output when the congruence is solvable.
8. Is this only for one variable congruences?
Yes. This page is designed for single-variable linear congruences. Systems of congruences and higher-degree modular equations need different methods, such as the Chinese remainder theorem or specialized algebraic techniques.