Generalized Chinese remainder solver
Simultaneous Modular Congruence Calculator
Solve up to five equations of the form x ≡ a (mod m). The calculator merges them one at a time, handles compatible non-coprime moduli, identifies gcd conflicts, and verifies the smallest nonnegative solution against every original congruence.
Enter residue clocks
Unified solution clock
Merge tape
Start: x ≡ 2 (mod 3) Merge x ≡ 3 (mod 5): gcd(3,5)=1; compatible. Solve 3k ≡ 1 (mod 5), k ≡ 2. New clock: x ≡ 8 (mod 15). Merge x ≡ 2 (mod 7): gcd(15,7)=1; compatible. Solve 15k ≡ −6 (mod 7), k ≡ 1. New clock: x ≡ 23 (mod 105).
Substitution check
23 mod 3 = 2 ✓ | 23 mod 5 = 3 ✓ | 23 mod 7 = 2 ✓
What a simultaneous congruence solution means
A congruence x ≡ a (mod m) says x and a leave the same remainder after division by positive modulus m. Equivalently, m divides x−a. One congruence describes an infinite arithmetic progression a+tm for every integer t. A simultaneous system asks for integers lying on all of those progressions.
The result is another congruence x ≡ r (mod M) when the system is compatible. r is displayed in the standard range 0 through M−1. Every integer r+tM is also a solution, including negative t. The combined period M is the least common multiple of the active moduli, not always their product.
When moduli are pairwise coprime, the classic Chinese remainder theorem guarantees one solution class modulo their product. Generalized CRT goes further: non-coprime moduli can still be merged if their residue requirements agree wherever the clocks overlap. This calculator performs that compatibility test at every merge.
The merge algorithm in four steps
1. Normalize
Replace each residue a by its least nonnegative remainder modulo m. Thus −1 mod 5 becomes 4 without changing the congruence class.
2. Compare through gcd
For current x ≡ r (mod M) and next x ≡ a (mod m), compute g = gcd(M,m). Compatibility requires a−r to be divisible by g.
3. Solve a reduced inverse
Write x = r+Mk. Divide Mk ≡ a−r (mod m) by g. The reduced coefficient M/g is invertible modulo m/g, so k can be found.
4. Build the new clock
Substitute k, normalize the new residue, and set the period to lcm(M,m) = M(m/g). Continue until every active congruence is merged.
Worked pairwise-coprime example
The default system is x ≡ 2 mod 3, x ≡ 3 mod 5, and x ≡ 2 mod 7. Start with the first clock. To merge the modulus-5 condition, write x = 2+3k. Substitution gives 2+3k ≡ 3 mod 5, so 3k ≡ 1 mod 5. The inverse of 3 modulo 5 is 2, giving k ≡ 2. Therefore x ≡ 8 mod 15.
Merge x ≡ 8 mod 15 with x ≡ 2 mod 7. Let x = 8+15k. Modulo 7, 15k ≡ −6. Since 15 ≡ 1 and −6 ≡ 1 modulo 7, k ≡ 1. Substitution gives x = 23. The combined period is 15×7 = 105 because all original moduli are pairwise coprime.
Check rather than trust the construction: 23 leaves remainder 2 on division by 3, remainder 3 on division by 5, and remainder 2 on division by 7. Adding 105 preserves all three remainders, so 128 and −82 are also solutions in the same class.
Compatible and incompatible non-coprime clocks
Consider x ≡ 2 mod 6 and x ≡ 5 mod 9. The gcd is 3, and the residue difference 5−2 = 3 is divisible by 3. A solution exists. The combined period is lcm(6,9)=18, not 54, and x ≡ 14 mod 18 satisfies both.
Now change the second residue to 4. The difference 4−2 = 2 is not divisible by gcd(6,9)=3. Any number congruent to 2 mod 6 is congruent to 2 mod 3, while any number congruent to 4 mod 9 is congruent to 1 mod 3. One integer cannot meet both demands, so the system has no solution. The calculator reports the exact conflicting merge instead of returning a misleading number.
Input, arithmetic, and safety limits
Residues and moduli must be integers, and active moduli must be positive. Enter modulus zero only to ignore optional rows four or five. Residues may be negative or larger than their modulus because normalization preserves the class. Modulus 1 imposes no restriction: every integer is congruent to 0 modulo 1.
The embedded implementation uses exact JavaScript integer arithmetic only while the merged modulus remains at or below 9,007,199,254,740,991. It rejects a system whose least-common-multiple period exceeds that safe range. For cryptographic-size moduli, use a maintained arbitrary-precision number theory library rather than accepting rounded browser numbers.
Multiplication can become large long before the visible residues do. The tool limits each input to safe integers and checks the combined period before proceeding. This is an educational solver, not a cryptographic implementation and not a source of secret-key security.
Applications and interpretation
Repeating schedules
Congruences can align tasks with different cycle lengths, such as a maintenance event occurring at specified offsets. Real calendars may add nonuniform months, time zones, and exceptions outside the modular model.
Reconstruction from residues
CRT can represent a large integer by several smaller residues and reconstruct a unique class within a known range. The range bound is essential because the solution repeats.
Computation and coding
Residue number systems and modular algorithms use smaller moduli for parallel work. Engineering implementations must manage overflow, chosen moduli, and verification carefully.
Number theory exercises
The merge tape exposes inverses and gcd conditions, making it useful for checking manual derivations without hiding why a solution exists.
The inverse step is one component of each compatible CRT merge.
Common mistakes
Do not multiply all moduli automatically. Their product is the combined modulus only for pairwise-coprime moduli; otherwise use the least common multiple. Do not divide a modular congruence by g unless g divides every relevant term and the modulus is reduced too. Ordinary fraction cancellation can change the solution set.
Keep the distinction between equality and congruence. The answer x = 23 is the least nonnegative representative, while x ≡ 23 mod 105 is the full family. If an application restricts x to a range, list members of that family inside the range. There may be zero, one, or several depending on its width.
Finally, verify every original condition. A merge algebra error can still produce a plausible-looking residue. The substitution strip makes each remainder explicit, and a hand solution should include the same certificate.
Frequently asked questions
Must the moduli be prime?
No. Pairwise coprime composite moduli work under the classic theorem, and compatible non-coprime moduli work under generalized CRT. Primality is sufficient in some setups but not required.
Why is the answer a family?
Modular conditions repeat. If r works, r+M and r−M work for the combined period M. The smallest nonnegative representative is only one convenient member.
Can residues be negative?
Yes. The calculator normalizes them. For example, x ≡ −2 mod 7 is the same class as x ≡ 5 mod 7.
What causes no solution?
At some merge, the residue difference is not divisible by the gcd of the two moduli. The two clocks then demand different residues modulo their shared factor.
Why is the combined period an lcm?
A shift that preserves both congruences must be divisible by both moduli. The smallest positive such shift is their least common multiple.
Can I use this for cryptography?
Use it for learning and small checks only. Real cryptographic arithmetic needs arbitrary precision, constant-time implementations, vetted libraries, secure inputs, and protocol-level review.
Manual merge worksheet
To reproduce the calculator on paper, make a table with columns for the current residue r, current period M, incoming residue a, incoming modulus m, gcd g, reduced modulus m/g, inverse, multiplier k, new residue, and new period. Normalize r after every row. This prevents negative representatives from growing and makes the next subtraction easier to inspect. Write a separate line showing that g divides a−r before attempting an inverse.
For the compatible system x ≡ 2 mod 6 and x ≡ 5 mod 9, g = 3 and a−r = 3. Divide the reduced equation by 3: (6/3)k ≡ 3/3 mod (9/3), giving 2k ≡ 1 mod 3. The inverse of 2 modulo 3 is 2, so k ≡ 2. Substitute x = 2+6k to get x = 14. Normalize modulo 18, the least common multiple, and verify 14 mod 6 = 2 and 14 mod 9 = 5.
If more conditions remain, treat x ≡ 14 mod 18 as one consolidated clock. The earlier equations no longer need to be carried separately during algebra because that clock represents their intersection. They should still remain in the final verification list. This iterative strategy is less error-prone than expanding a many-term closed formula, and it naturally exposes the first incompatible pair.
Choosing a representative in an application range
The least nonnegative r may not be the member needed by an application. To find solutions in L ≤ x ≤ U, solve L ≤ r+tM ≤ U. The smallest eligible integer multiplier is ceil((L−r)/M), and the largest is floor((U−r)/M). Every integer t between those bounds produces one valid solution. If the lower multiplier exceeds the upper multiplier, the modular system is compatible but has no representative inside the requested finite range.
Keep units and epoch definitions consistent in scheduling problems. “Day 2 modulo 7” depends on which day is labeled zero, and clock times can be affected by daylight-saving changes. CRT only aligns the integer model supplied to it; it cannot correct an inconsistent calendar encoding.
Verify individual residues, reductions, and congruence steps with the modular arithmetic calculator before combining the system.
References
The theorem statement follows the U.S. National Institute of Standards and Technology Digital Library of Mathematical Functions, Section 27.15. NIST states that pairwise relatively prime moduli give a solution unique modulo their product and describes computation with residue systems. This calculator adds the standard gcd compatibility extension for non-coprime moduli.