Solve Linear Congruence a · x ≡ b (mod m)
Modular Inverse a⁻¹ mod m
System of Congruences (CRT)
| # | x ≡ r | mod m |
|---|
Results
| Timestamp | Type | Input | Solution | Steps |
|---|
Example Data
| Type | Input | Expected Output |
|---|---|---|
| Linear Congruence | a=14, b=30, m=100 | x ≡ 45 (mod 50) |
| Modular Inverse | a=7, m=40 | No inverse, because gcd(7, 40) = 1? False → 1. Actually gcd = 1, inverse ≡ 23. |
| CRT | x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) | x ≡ 23 (mod 105) |
Formula Used
A linear congruence a·x ≡ b (mod m) is solvable iff g = gcd(a, m) divides b.
When solvable, reduce by g: a′=a/g, b′=b/g, m′=m/g. Because gcd(a′, m′)=1, the inverse a′⁻¹ mod m′ exists and
one solution is x₀ ≡ a′⁻¹ · b′ (mod m′). All solutions are x ≡ x₀ + k·m′ for any integer k.
For a system x ≡ rᵢ (mod mᵢ), we iteratively merge two congruences x ≡ r₁ (mod m₁) and x ≡ r₂ (mod m₂).
Let g = gcd(m₁, m₂). A solution exists iff (r₂ − r₁) is divisible by g. If it exists, the combined solution is
x ≡ r (mod lcm(m₁, m₂)) where r = r₁ + m₁ · k, and k satisfies
m₁·k ≡ (r₂ − r₁) (mod m₂). We compute k using the extended Euclidean algorithm.
How to Use
- To solve a·x ≡ b (mod m), fill a, b, m and click Solve.
- To find a modular inverse, enter a and m, then click Find Inverse.
- For systems, add rows for each congruence r and m, then click Solve System.
- Review the steps via the expandable details in the results table.
- Use Export CSV or Download PDF to save the results table.
FAQs
Definition & Notation
We write a ≡ b (mod m) when m divides a − b. Every integer maps to a residue class modulo m, represented by a number in [0, m−1]. Modular arithmetic supports addition, subtraction, and multiplication; division needs invertibility.
- Normalize values with
r = ((a % m) + m) % mto keep residues nonnegative. - Equivalent classes enable wrap‑around behavior used throughout number theory and computing.
Solvability & Number of Solutions
A linear congruence a·x ≡ b (mod m) has solutions iff g = gcd(a, m) divides b. When solvable, set a′=a/g, b′=b/g, m′=m/g and compute x₀ ≡ a′⁻¹·b′ (mod m′).
- All solutions:
x ≡ x₀ (mod m′). There are exactlygincongruent solutions modulom. - Example.
14x ≡ 30 (mod 100). Hereg=2;m′=50; one class isx ≡ 45 (mod 50). Modulo 100 that yields two residues:45and95.
Generalized CRT Conditions
To merge two congruences x ≡ r₁ (mod m₁) and x ≡ r₂ (mod m₂), compute g=gcd(m₁,m₂). A solution exists iff (r₂−r₁) is divisible by g. The combined modulus is lcm(m₁,m₂)=m₁·m₂/g.
- Consistent.
x ≡ 2 (mod 3),x ≡ 3 (mod 5),x ≡ 2 (mod 7)→x ≡ 23 (mod 105). - Inconsistent.
x ≡ 0 (mod 4),x ≡ 3 (mod 6)sincegcd(4,6)=2but3−0isn’t divisible by2.
Practical Applications & Tips
- Cryptography. Modular inverses and CRT underpin RSA key operations and optimizations.
- Scheduling. Align repeating cycles: solve day offsets under multiple periodic constraints.
- Computer Science. Hashing, checksums, and pseudo‑random generators rely on residues.
- Number Theory. Diophantine equations, primitive roots, and multiplicative groups.
Tip: Reduce inputs by gcd early and normalize residues before combining; it improves numerical stability and clarity of final periods.