Solves a·x ≡ b (mod n). Gives minimal residue and general solution family.
| Equation | Modulus | |
|---|---|---|
Finds x ≡ rᵢ (mod mᵢ). Handles non‑coprime moduli if consistent; returns least nonnegative residue and combined modulus.
Residue & Congruence Check
Modular Inverse
Exists only if gcd(a,n)=1.
Results
Exportable| Time | Tool | Inputs | Result | Steps |
|---|
Example Data
Click Load to populate inputs with an example.
Formulas Used
- Residue: a mod n = a − n ⌊a/n⌋; returned in [0, n−1].
- Congruence: a ≡ b (mod n) iff n | (a − b).
- Linear congruence: For a·x ≡ b (mod n), let g=gcd(a,n).
If g ∤ b, no solution. Otherwise set a'=a/g, b'=b/g, n'=n/g. Let a'⁻¹ be the modular inverse of a' modulo n'. Then one solution is x₀ ≡ a'⁻¹·b' (mod n'), and the general solution family is x ≡ x₀ + k·n'. - Modular inverse: a⁻¹ mod n exists iff gcd(a,n)=1. Computed via extended Euclid.
- Chinese Remainder (general): Combine two congruences x ≡ r₁ (mod m₁), x ≡ r₂ (mod m₂).
Let g=gcd(m₁,m₂). If (r₂−r₁) mod g ≠ 0, inconsistent. Otherwise the merged modulus is lcm(m₁,m₂)=m₁·m₂/g, and one solution is
x ≡ r₁ + m₁ · [( (r₂−r₁)/g ) · ( (m₁/g)⁻¹ mod (m₂/g) ) ] (mod lcm), reduced to the least residue.
How to Use This Calculator
- Choose Linear Congruence to solve a·x ≡ b (mod n). Enter a, b, and n, then click Solve.
- Use Chinese Remainder to combine several conditions x ≡ rᵢ (mod mᵢ). Add rows as needed and click Solve CRT.
- Open Quick Tools for residues, congruence checks, and modular inverse.
- Results appear in the table below. Use Download CSV or Download PDF to export.
- Click an example’s Load to auto‑fill inputs for a quick demo.
Reference: Euler’s Totient φ(n) & Unit Group Size
φ(n) counts integers in [1,n] relatively prime to n. The multiplicative group of units modulo n has size φ(n).
| n | Prime factorization | φ(n) | Notes |
|---|---|---|---|
| 2 | 2 | 1 | Units: {1} |
| 3 | 3 | 2 | Prime; group cyclic |
| 4 | 2² | 2 | Units: {1,3} |
| 5 | 5 | 4 | Prime; group cyclic |
| 6 | 2·3 | 2 | Units: {1,5} |
| 7 | 7 | 6 | Prime; group cyclic |
| 8 | 2³ | 4 | Units: {1,3,5,7} |
| 9 | 3² | 6 | Units: {1,2,4,5,7,8} |
| 10 | 2·5 | 4 | — |
| 11 | 11 | 10 | Prime; group cyclic |
| 12 | 2²·3 | 4 | — |
| 15 | 3·5 | 8 | — |
| 16 | 2⁴ | 8 | — |
| 18 | 2·3² | 6 | — |
| 20 | 2²·5 | 8 | — |
| 21 | 3·7 | 12 | — |
| 22 | 2·11 | 10 | — |
| 24 | 2³·3 | 8 | — |
| 25 | 5² | 20 | — |
| 26 | 2·13 | 12 | — |
| 28 | 2²·7 | 12 | — |
| 30 | 2·3·5 | 8 | — |
Reference: Congruence Identities & Shortcuts
| Rule | Statement | Example |
|---|---|---|
| Normalization | a ≡ a mod n | 123 ≡ 3 (mod 10) |
| Add/Subtract | a≡b, c≡d ⇒ a±c≡b±d | 14≡4, 9≡-1 ⇒ 23≡3 (mod 10) |
| Multiply | a≡b ⇒ ka≡kb | 7≡-1 ⇒ 3·7≡-3 (mod 8) |
| Cancellation | ca≡cb and gcd(c,n)=1 ⇒ a≡b | 2x≡2 (mod 5) ⇒ x≡1 |
| Powering | a≡b ⇒ a^k≡b^k | 3≡-2 (mod 5) ⇒ 3⁴≡(-2)⁴ |
| Euler | gcd(a,n)=1 ⇒ a^{φ(n)}≡1 | a^{40}≡1 (mod 41) |
| Fermat | p prime, p∤a ⇒ a^{p-1}≡1 | 2^{10}≡1 (mod 11) |
| CRT Merge | Combine x≡rᵢ (mod mᵢ) | x≡2 (3), 3 (5), 2 (7) ⇒ 23 (105) |
Use cancellation only when the factor is a unit modulo n (i.e., coprime to n).
FAQs
It means n divides a − b, or equivalently that a and b have the same remainder when divided by n.
If g=gcd(a,n) does not divide b, then a·x ≡ b (mod n) is impossible. Otherwise there are g congruence classes of solutions.
No. a⁻¹ mod n exists only if gcd(a,n)=1. Otherwise the inverse is undefined.
No. This tool supports the generalized CRT: non‑coprime moduli are allowed if the congruences are pairwise consistent modulo the gcds.
We show reductions, gcds via extended Euclid, inverses when they exist, and the construction of the general solution or CRT merge.
We return the least non‑negative residue in [0, m−1] for modulus m, alongside the general solution description.
Inputs are 64‑bit integers in JavaScript. Extremely large moduli may overflow or slow down computations in the browser.
Tips
- Keep moduli positive for standard residue classes.
- Use the CRT when multiple modular conditions must hold simultaneously.
- For speed, reduce inputs using residues before solving.
- Toggle “Show steps” to condense or expand derivations.
About
Single‑file calculator with white theme. Accessible controls, exportable results, example problems, and clear derivations for learning and verification.
Need a permalink?
Press Enter to submit.