Chinese Remainder Theorem Calculator

The theorem states that if we have a system of linear congruences such that x ≡ a_i (mod n_i) for i = 1, 2, ..., k, and all moduli n_i are pairwise coprime (meaning their greatest common divisor is 1), then there exists a unique solution modulo N, where N is the product of all n_i. To compute this, the calculator finds the total product N = n_1 * n_2 * ... * n_k, calculates the partial product N_i = N / n_i for each equation, determines the modular inverse of N_i modulo n_i, and sums up the products of a_i, N_i, and their respective modular inverses to find the final principal solution.

Consider a classic puzzle modeled as a system of three congruences: x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7). First, we find the total modulus product: N = 3 * 5 * 7 = 105. Next, we compute the partial products for each equation: N_1 = 105 / 3 = 35, N_2 = 105 / 5 = 21, and N_3 = 105 / 7 = 15. Then, we determine the modular inverse for each N_i under its respective modulus n_i. For N_1 = 35 mod 3 (which is 2), the inverse is 2 because (2 * 2) ≡ 1 (mod 3). For N_2 = 21 mod 5 (which is 1), the inverse is 1. For N_3 = 15 mod 7 (which is 1), the inverse is 1. Multiplying each remainder by its corresponding partial product and modular inverse gives: (2 * 35 * 2) + (3 * 21 * 1) + (2 * 15 * 1) = 140 + 63 + 30 = 233. Finally, taking 233 modulo 105 yields 23, which is the smallest positive integer solution that satisfies all three conditions simultaneously.

Always verify that your input moduli are strictly pairwise coprime before running computations, as the standard theorem fails if any two moduli share a common factor greater than one. Double-check your remainder inputs and corresponding moduli alignments to avoid offset errors. When dealing with large numbers in cryptographic contexts, rely on automated tools to prevent arithmetic overflow and sign miscalculations during modular inversion steps.