Linear Congruence Solver
Solve a·x≡b (mod m) exactly, returning a residue, solution period, and number of residues modulo m; unsatisfiable equations return zero certificate fields.
Description
A linear congruence can have no solution, one residue class or several residues modulo m.
A linear congruence can have no solution, one residue class or several residues modulo m. The gcd of its coefficient and modulus determines solvability and multiplicity.1
The tool returns solvable, residue, period, multiplicity. The indexing and output conventions below determine how to read these values.
When to use Linear Congruence Solver
Use this for the following task: Solve a·x≡b (mod m) exactly, returning a residue, solution period, and number of residues modulo m; unsatisfiable equations return zero certificate fields. Use the input and output conventions below to reproduce the intended mathematical quantity.
How to use Linear Congruence Solver and understand its results
- Choose the required indexes, integers or sequence entries. Preserve decimal-string encodings where the field table specifies strings.
- Enter a, b, modulus according to the field table, then run the tool.
- Read solvable, residue, period, multiplicity. Preserve exact decimal strings and the stated indexing or coefficient order.
- Keep exact decimal strings for subsequent integer arithmetic; distinguish them from any explicitly approximate numeric result.
| Input field | Meaning | Value type and bounds | Requirement |
|---|---|---|---|
| a | Signed coefficient | string (integer/arbitrary); maximum text length 200; pattern ^-?(0|[1-9][0-9]*)$ | Required |
| b | Signed right-hand side | string (integer/arbitrary); maximum text length 200; pattern ^-?(0|[1-9][0-9]*)$ | Required |
| modulus | Positive modulus | string (integer/arbitrary); maximum text length 200; pattern ^[1-9][0-9]*$ | Required |
Parse signed a and b and a positive modulus with BigInt. Use extended Euclid to find a normalized residue and return its period and multiplicity as strings.
a×x≡b mod m is solvable iff gcd(a,m)|b; period=m/gcd(a,m) The symbols and boundary conditions refer to the supplied fields and the implementation described above.
| Output field | Meaning | Value type |
|---|---|---|
| solvable | Whether the congruence has a solution | boolean |
| residue | Least nonnegative solution | string (integer/arbitrary) |
| period | Period of all solutions | string (integer/arbitrary) |
| multiplicity | Number of solutions modulo the modulus | string (integer/arbitrary) |
{
"input": {
"a": "14",
"b": "30",
"modulus": "100"
},
"output": {
"solvable": true,
"residue": "45",
"period": "50",
"multiplicity": "2"
}
}Limitations and assumptions
All solutions are residue+j×period for j=0..multiplicity−1 modulo m. An unsatisfiable equation returns solvable=false and zero certificate fields; modulus one is allowed.
Use the declared integer bounds and string formats. Large exact outputs remain decimal strings; numerical approximations use ordinary floating-point arithmetic. A rejected input is different from a valid zero count or false membership flag.
Alternative or Complementary methods
Choose Modular Inverse when you need its operation: Find the least nonnegative inverse of a signed decimal integer modulo a decimal modulus of at least two, rejecting noncoprime pairs. Choose Extended Euclidean Coefficients for the complementary operation: Find exact decimal coefficients x and y satisfying a·x+b·y=gcd(a,b), with a nonnegative gcd and deterministic coefficients even when both inputs are zero.
Background reference: Linear Congruences.
References
-
Linear Congruences — Mount Royal University, Mathematics LibreTexts
Similar or alternative tools
- Modular Inverse
Find the least nonnegative inverse of a signed decimal integer modulo a decimal modulus of at least two, rejecting noncoprime pairs.
- Extended Euclidean Coefficients
Find exact decimal coefficients x and y satisfying a·x+b·y=gcd(a,b), with a nonnegative gcd and deterministic coefficients even when both inputs are zero.