Single Congruence: a·x ≡ b (mod m)
Solutions
| # | x | Class | Check |
|---|
Step-by-step log
System of Congruences aᵢ·x ≡ bᵢ (mod mᵢ)
| # | aᵢ | bᵢ | mᵢ |
|---|
Merged Solution
| Representative | Modulus | Class | Check |
|---|
Step-by-step merge log
Example Data Table
| Context | a | b | m | Notes |
|---|---|---|---|---|
| Single congruence | 14 | 30 | 100 | gcd(14,100)=2 divides 30, two solutions |
| # | aᵢ | bᵢ | mᵢ | Meaning |
|---|---|---|---|---|
| 1 | 1 | 2 | 5 | x ≡ 2 (mod 5) |
| 2 | 1 | 3 | 7 | x ≡ 3 (mod 7) |
| 3 | 1 | 1 | 4 | x ≡ 1 (mod 4) |
Formula Used
Single congruence: Solve \( a x \equiv b \ (\mathrm{mod}\ m) \).
- Let \( d = \gcd(a,m) \). A solution exists iff \( d \mid b \).
- Reduce: \( a' = a/d,\ b' = b/d,\ m' = m/d \).
- Compute inverse \( a'^{-1} \pmod{m'} \). Then \( x_0 \equiv a'^{-1} b' \ (\mathrm{mod}\ m') \).
- All solutions modulo \( m \) are \( x \equiv x_0 + k\,m' \) for \( k = 0,1,\dots,d-1 \).
System: For each \( a_i x \equiv b_i \ (\mathrm{mod}\ m_i) \), reduce to \( x \equiv r_i \ (\mathrm{mod}\ M_i) \) as above, then merge constraints using the generalized Chinese Remainder Theorem.
- Combining \( x \equiv r_1 \ (\mathrm{mod}\ n) \) and \( x \equiv r_2 \ (\mathrm{mod}\ m) \) is possible iff \( r_1 \equiv r_2 \ (\mathrm{mod}\ \gcd(n,m)) \).
- Let \( g=\gcd(n,m) \), \( n'=n/g \), \( m'=m/g \). Find \( t \equiv (r_2-r_1)/g \cdot (n')^{-1} \ (\mathrm{mod}\ m') \).
- Then \( x \equiv r_1 + n\,t \ (\mathrm{mod}\ \mathrm{lcm}(n,m)) \).
How to Use
- Enter integers for a, b, and modulus m to solve \(a x \equiv b\).
- Toggle “List all incongruent solutions” to enumerate all classes modulo \(m\).
- For systems, add rows for \(a_i, b_i, m_i\). Coefficients may be any integers.
- Click “Solve System” to merge reduced constraints via the generalized CRT.
- Use “Download CSV” to export the solution table. Use “Download PDF” for a report.
- Click “Load Example” to populate a demonstrative system.
- Negative values are normalized; extremely large values are handled using big integers.
FAQs
For \(a x \equiv b \pmod m\), if \(d=\gcd(a,m)\) does not divide \(b\), the congruence is inconsistent. For systems, any incompatible pair prevents a global solution.
Yes. Inputs are normalized using \( x \mapsto x \bmod m \) so signs do not affect the final residue class.
Yes. The generalized CRT checks \( r_1 \equiv r_2 \ (\mathrm{mod}\ \gcd(n,m)) \). If satisfied, a solution exists modulo \( \mathrm{lcm}(n,m) \).
Via the extended Euclidean algorithm. If \( \gcd(a,m)=1 \), we find integers \(x,y\) with \(ax+my=1\); the inverse is \(x \bmod m\).
When \(d=\gcd(a,m) > 1\) and \(d\mid b\), there are \(d\) incongruent solutions modulo \(m\), spaced by \(m/d\). They represent one class modulo \(m/d\).
Parsing uses big integers, so you are limited mainly by browser memory, not floating‑point precision. Still, very large inputs may slow processing.
Yes. If your equations have coefficient \(a_i=1\), simply enter \(b_i=r_i\). The solver merges them using CRT automatically.