Linear Congruence Solver with Steps
Solve congruences of the form ax ≡ b (mod m) with detailed step-by-step solutions and interactive visualization.
Solution Results
Comprehensive Guide to Solving Linear Congruences
A linear congruence is an equation of the form ax ≡ b (mod m), where:
- a is the coefficient (integer)
- b is the constant (integer)
- m is the modulus (positive integer)
- x is the unknown variable we solve for
When Does a Solution Exist?
The linear congruence ax ≡ b (mod m) has solutions if and only if the greatest common divisor (gcd) of a and m divides b. Mathematically:
gcd(a, m) | b
Step-by-Step Solution Method
- Compute d = gcd(a, m)
- If d does not divide b, there are no solutions
- If d divides b, there are exactly d distinct solutions modulo m
- Divide the congruence by d
Transform to: (a/d)x ≡ (b/d) (mod m/d)
- Find the modular inverse
Find y such that (a/d)y ≡ 1 (mod m/d) using the Extended Euclidean Algorithm
- Compute particular solution
x₀ ≡ y*(b/d) (mod m/d)
- Generate all solutions
The complete solution set is: x ≡ x₀ + k*(m/d) (mod m) for k = 0, 1, …, d-1
Practical Applications
Linear congruences appear in:
- Cryptography: RSA encryption and digital signatures
- Computer Science: Hashing algorithms and pseudorandom number generation
- Number Theory: Solving Diophantine equations
- Engineering: Signal processing and error correction codes
Comparison of Solution Methods
| Method | Time Complexity | Best For | Implementation Difficulty |
|---|---|---|---|
| Extended Euclidean Algorithm | O(log min(a, m)) | General cases | Moderate |
| Brute Force Search | O(m) | Small moduli (m < 10⁶) | Easy |
| Chinese Remainder Theorem | O(k log n) for k congruences | Systems of congruences | Advanced |
| Hensel’s Lemma | O(log³ n) | Lifting solutions modulo pᵏ | Very Advanced |
Common Mistakes and How to Avoid Them
- Forgetting to check gcd(a,m) | b
Always verify this condition first. Our calculator automatically checks this and alerts you if no solutions exist.
- Incorrect modulus reduction
Remember that solutions are equivalent modulo m. The calculator shows all distinct solutions in the complete residue system.
- Sign errors with negative numbers
Our tool handles negative inputs by converting them to positive equivalents modulo m.
- Confusing particular and general solutions
The calculator clearly distinguishes between the particular solution and the complete solution set.
Advanced Topics in Linear Congruences
Systems of Linear Congruences
When you have multiple congruences:
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
…
x ≡ aₖ (mod mₖ)
The Chinese Remainder Theorem states that if the moduli are pairwise coprime, there exists a unique solution modulo the product of all moduli.
Non-linear Congruences
For higher degree congruences like x² ≡ a (mod m), solutions become more complex:
| Congruence Type | Solution Existence Condition | Maximum Number of Solutions |
|---|---|---|
| Linear (ax ≡ b) | gcd(a,m) | b | gcd(a,m) |
| Quadratic (x² ≡ a) | Legendre symbol (a/p) = 1 for all p|m | 2ᵏ where k = number of distinct prime factors of m |
| Cubic (x³ ≡ a) | Always solvable modulo primes p ≡ 1 (mod 3) | 3ᵏ |
Frequently Asked Questions
What if gcd(a,m) doesn’t divide b?
In this case, there are no integer solutions to the congruence. The calculator will clearly indicate this scenario with an explanatory message.
How do I find the smallest positive solution?
Use the “Smallest positive solution” option in our calculator. The algorithm will:
- Find all solutions modulo m
- Compute each solution modulo m to get the smallest positive representative
- Select the smallest positive value from these representatives
Can I solve x ≡ 5 (mod 0)?
No, the modulus m must be a positive integer greater than 0. Our calculator validates this input and shows an error if m ≤ 0.
What’s the difference between x ≡ 2 (mod 5) and x ≡ 7 (mod 5)?
These are equivalent congruences because 7 mod 5 = 2. Our calculator automatically reduces coefficients modulo m to show the simplest form.
How are negative solutions handled?
The calculator converts negative solutions to their positive equivalents modulo m. For example, x ≡ -1 (mod 5) becomes x ≡ 4 (mod 5).