Chinese Remainder Theorem Calculator

Name: Chinese Remainder Theorem Calculator
Author: Jitendra Kumar

Solve systems of modular congruences with CRT, generalized consistency checks, and modular inverse steps.

Last Updated: May 2026

Smallest nonnegative solution

Solution class

x = 23 mod 105

Combined modulus

105

Moduli

Pairwise coprime

Congruence System

Enter one congruence per line. Formats like 2 mod 3, x = 2 (mod 3), or 2, 3 all work.

Congruences

Normalized Congruences

#	Input	Normalized
1	2 mod 3	x = 2 mod 3
2	3 mod 5	x = 3 mod 5
3	2 mod 7	x = 2 mod 7

Combination Steps

Step	System	Result
Step 1	Combine x = 2 mod 3 with x = 3 mod 5	x = 8 mod 15
Step 2	Combine x = 8 mod 15 with x = 2 mod 7	x = 23 mod 105

GCD and Inverse Details

Step	GCD check	Inverse detail
Step 1	gcd(3, 5) = 1	Inverse of 3 mod 5 is 2; multiplier t = 2.
Step 2	gcd(15, 7) = 1	Inverse of 15 mod 7 is 1; multiplier t = 1.

Number Theory Notice

This calculator is for educational modular arithmetic and exact integer number theory. For cryptography or production systems, use audited math libraries and validated parameter handling.

Reviewed For Methodology, Labels, And Sources

Every CalculatorWallah calculator is published with visible update labeling, linked source references, and founder-led review of formula clarity on trust-sensitive topics. Use results as planning support, then verify institution-, policy-, or jurisdiction-specific rules where they apply.

Reviewed By

Jitendra Kumar, Founder & Editorial Standards Lead, oversees methodology standards and trust-sensitive publishing decisions.

Review editor profile

Topic Ownership

Sales tax and tax-sensitive estimate tools, Education and GPA planning calculators, Health, protein, and screening-formula pages, Platform-wide publishing standards and methodology

See ownership standards

Methodology & Updates

Page updated May 2026. Trust-critical pages are reviewed when official rates or rules change. Evergreen calculator guides are checked on a recurring quarterly or annual cycle depending on topic volatility.

Sources & methodology About the review process

How to Use the Chinese Remainder Theorem Calculator

Step 1: Enter congruences
Type one condition per line, such as 2 mod 3 or x = 2 (mod 3).
Step 2: Normalize the system
The calculator converts each remainder into the standard range from 0 to modulus minus 1.
Step 3: Check consistency
It tests gcd compatibility and identifies whether the system has a simultaneous integer solution.
Step 4: Read the solution class
When a solution exists, use x = a mod M to describe every integer solution.

How the Chinese Remainder Theorem Works

The Chinese remainder theorem describes when several remainder conditions can be solved at the same time. A typical system looks like x = a_i mod m_i for several different moduli.

If all moduli are pairwise coprime, the classical theorem guarantees one solution class modulo the product of the moduli. That means every answer differs by a multiple of the combined modulus.

This calculator also handles generalized CRT systems. When moduli share factors, each pair of remainders must agree modulo the gcd of the moduli. If they do, the solution repeats modulo the least common multiple.

Chinese Remainder Theorem Guide

CRT Formulas and Conditions

Classical CRT is the clean pairwise-coprime case. Generalized CRT keeps the same idea but adds gcd compatibility checks when moduli share factors.

Concept	Formula	Use
Congruence system	x = a_i mod m_i	Each line gives one remainder condition.
Classical CRT condition	gcd(m_i, m_j) = 1 for every pair	Guarantees a unique solution modulo the product.
Combined modulus	M = m_1 x m_2 x ... x m_k	Used when all moduli are pairwise coprime.
General consistency test	a_i - a_j is divisible by gcd(m_i, m_j)	Needed when moduli are not pairwise coprime.
General combined modulus	lcm(m_1, m_2, ...)	All solutions repeat by this modulus when a solution exists.
Pairwise combine equation	m_1 t = a_2 - a_1 mod m_2	Solves one merge step using a modular inverse after dividing by gcd.

Examples

These examples include the standard coprime case, a non-coprime system that still works, and an inconsistent system with no solution.

System	Condition	Result
x = 2 mod 3; x = 3 mod 5; x = 2 mod 7	Pairwise coprime moduli	x = 23 mod 105
x = 0 mod 5; x = 6 mod 7; x = 10 mod 12	Historical CRT-style example	x = 370 mod 420
x = 2 mod 4; x = 6 mod 8	Not coprime, but consistent	x = 6 mod 8
x = 1 mod 4; x = 2 mod 6	Difference 1 is not divisible by gcd 2	No solution

Mistakes To Avoid

Most CRT errors come from skipping the gcd checks or using the product of moduli when the moduli are not pairwise coprime.

Mistake	Fix
Assuming non-coprime systems always fail	They can work if remainders agree modulo the gcd of each modulus pair.
Forgetting to normalize remainders	A remainder like -1 mod 5 is the same class as 4 mod 5.
Using product instead of LCM for non-coprime moduli	The solution period is the LCM when compatible moduli share factors.
Ignoring the no-solution case	Check that each remainder difference is divisible by the corresponding gcd.

Keep the research moving with Modulo Calculator, Inverse Modulo Calculator, GCF Calculator, and LCM Calculator.

Frequently Asked Questions

It solves systems of modular congruences such as x = 2 mod 3, x = 3 mod 5, and x = 2 mod 7.

Enter one congruence per line. You can use formats like 2 mod 3, x = 2 (mod 3), or 2, 3.

Classical CRT assumes pairwise coprime moduli. This calculator also handles generalized CRT cases where moduli share factors, as long as the remainders are compatible modulo those factors.

For any two congruences, the difference between the remainders must be divisible by the gcd of the two moduli. If that fails, no simultaneous integer solution exists.

A CRT system has an infinite family of integer solutions. Writing x = a mod M means every solution is a plus a multiple of M.

Yes. The calculator normalizes negative remainders into the standard range from 0 to modulus minus 1.