Chinese Remainder Theorem Calculator

The Chinese Remainder Theorem combines two modular conditions into a single one when the moduli are coprime.

How the Math Works

The Chinese Remainder Theorem allows solving simultaneous congruences when moduli are coprime. Given x ≡ a (mod m) and x ≡ b (mod n) with gcd(m, n)=1, there's a unique solution modulo m×n. To find x, compute the modular inverse of m modulo n (or vice versa) using the Extended Euclidean Algorithm, then combine the results: x = a + m × [(b - a) × m⁻¹ mod n]. This ensures x satisfies both congruences while minimizing computational complexity through modular arithmetic properties.

Practical Applications

This calculator efficiently solves systems like finding x where x leaves remainder 3 when divided by 5 and remainder 5 when divided by 7. Such problems arise in cryptography for RSA key generation, where large primes ensure coprime moduli. Engineers use CRT to parallelize computations in signal processing, and computer scientists apply it to optimize hash table indexing. The tool streamlines these applications by automating the inverse calculation and solution combination, which becomes error-prone manually with large numbers.

Day-to-Day Use

CRT helps synchronize repeating events, like determining when two cyclical tasks (e.g., medication schedules or bus arrival times) align. It's useful in coding theory for error-correcting codes in digital communications, ensuring data integrity in streaming services. Even in puzzle-solving, such as the classic 'coconut division' problems, CRT provides a systematic approach to find solutions that satisfy multiple divisibility conditions simultaneously, turning complex modular constraints into manageable calculations.

Worked example

x ≡ 2 (mod 3) and x ≡ 3 (mod 5) → x = 8 (mod 15).

FAQ