Modular Linear Equation Calculator

Solve ax ≡ b (mod m) and list solutions when they exist. This educational calculator shows the formula, result, and step-by-step interpretation.

Discrete MathCryptography

Calculator

What this calculator teaches

Modular linear equations appear in number theory, congruences, and cryptographic examples.

Use the result as a learning aid. For classwork, still show the formula and intermediate reasoning so the final answer is not just a black-box number.

When a Linear Congruence Has Solutions

The congruence ax ≡ b (mod m) asks for integers x whose product ax differs from b by a multiple of m. Unlike ordinary algebra, division by a is not always legal modulo m because a may not have a multiplicative inverse. The key test is g = gcd(a,m): solutions exist exactly when g divides b.

If g divides b, divide a, b, and m by g to obtain a reduced congruence a′x ≡ b′ (mod m′) with gcd(a′,m′) = 1. Now a′ has a modular inverse, so one reduced solution is x0 ≡ (a′)−1b′ (mod m′). In the original modulus m there are exactly g distinct residue-class solutions.

StepRulePurpose
Solvabilityg = gcd(a,m), require g | bDetermines whether any solution exists
Reductiona′=a/g, b′=b/g, m′=m/gMakes a′ invertible modulo m′
Base solutionx0 ≡ (a′)−1b′ mod m′Finds one residue class
All solutionsx = x0 + km′, k=0,…,g−1Lists distinct solutions modulo m

This gcd structure explains why cancellation in modular arithmetic requires care. A common factor can be cancelled only when the modulus is reduced consistently as part of the congruence.

Formula & Symbols

ConceptFormula or rule
Equationax ≡ b (mod m)
Solvabilitygcd(a,m) divides b

Worked example

Example: 14x ≡ 30 mod 100 has solutions because gcd(14,100)=2 divides 30.
Example 2: 14x ≡ 30 (mod 100) has g = 2. Reducing gives 7x ≡ 15 (mod 50), with base solution x ≡ 45 (mod 50). The original solutions are 45 and 95 modulo 100.
Example 3: 6x ≡ 5 (mod 9) has gcd(6,9) = 3, but 3 does not divide 5. Therefore no solution exists.
Example 4: 4x ≡ 8 (mod 12) has g = 4. Reducing gives x ≡ 2 (mod 3), producing four solutions modulo 12: 2, 5, 8, and 11.
Example 5: 3x ≡ 1 (mod 7) has gcd 1, so there is one solution. Since 3−1 ≡ 5 (mod 7), x ≡ 5.

Common mistakes

⚠️
Using the wrong input format

Keep lists comma separated, matrices as rows separated by semicolons, and modular inputs as integers.

⚠️
Ignoring assumptions

Some methods require positive probabilities, valid moduli, independent trials, or small educational input sizes.

⚠️
Dividing by a coefficient that is not invertible

Modular division means multiplication by an inverse. If gcd(a,m) ≠ 1, a has no inverse modulo m, so use the gcd reduction method instead.

⚠️
Finding one reduced solution and stopping

When g = gcd(a,m) > 1 and g divides b, the original congruence has g distinct solutions modulo m. Generate all of them using spacing m/g.

FAQ

Can I use decimals?⌄
Most numerical calculators allow decimals, but modular arithmetic and coding-theory tools usually require integers or binary strings.
Is this for homework checking?⌄
Yes. The page is designed to show both the answer and the reasoning pattern.
Why does the result sometimes say approximate?⌄
Some probability, floating-point, and numerical methods naturally produce approximations.
Why does gcd(a,m) have to divide b?⌄
Any expression ax − km is an integer combination of a and m, so it must be divisible by gcd(a,m). If b is not divisible by that gcd, no integers x and k can satisfy ax − b = km.
Why are there g solutions when the gcd is g?⌄
After reduction, one solution class exists modulo m/g. Lifting that class back to modulus m gives x0, x0+m/g, and so on through g distinct residues before the pattern repeats.
Can a or b be negative in a modular equation?⌄
Yes. Negative coefficients and constants can be reduced to equivalent residues modulo m. The gcd solvability condition still applies, provided the modulus is treated as positive under the usual convention.
What happens when gcd(a,m) = 1?⌄
Then a has a unique multiplicative inverse modulo m, and every b gives exactly one solution class x ≡ a−1b (mod m). This is the easiest linear-congruence case.

Related calculators

🔗 Set Operations Calculator🔗 Graph Theory and Adjacency Matrix Calculator🔗 Shannon Entropy and Information Gain Calculator🔗 Numerical Error Calculator

These links will work after the calculators are registered in the final Math layout update.

Formula Explorer connections

Interpretation: This formula describes an algebraic relationship among variables, functions, equations, roots or sequences. Assumption: Respect the expression’s domain and excluded values. Check roots in the original equation because transformations can introduce extraneous solutions.

Parabola Equation Calculator →Piecewise Function Calculator →Polynomial Calculator →Math Formula Explorer →