Chinese Remainder Theorem Solver Online

Master the Chinese Remainder Theorem with Our Free Online Calculator

Welcome to our comprehensive guide on the Chinese Remainder Theorem, paired with a powerful and free online calculator. This fundamental principle of number theory assures us that a unique solution can always be found for a system of remainder equations, known as congruences. Its proof and practical application are deeply intertwined with the Euclidean algorithm and Bézout's identity, both of which we will explore in detail. Let's begin by building a solid foundation.

Understanding Modulo Operations and Congruences

While mathematics encompasses vast abstract concepts, number theory remains firmly grounded in the study of integers—whole numbers like 0, 1, 42, or -273, excluding fractions. Within this field, the modulo operation is a cornerstone. Before defining it, we must recall what a remainder is.

The remainder is the integer left over after division. When dividing integer a by integer b, the remainder r is an integer between 0 and b-1 that satisfies the equation a = k·b + r, where k is also an integer. For example, 17 divided by 5 gives a quotient of 3 and a remainder of 2, expressed as 17 = 3·5 + 2.

We say a is congruent to b modulo n, written as a ≡ b (mod n), if a and b yield the same remainder when divided by n. These congruences behave similarly to standard equations in many ways; you can add or subtract the same integer from both sides, or multiply both sides by any integer. The Chinese Remainder Theorem specifically addresses solving systems of such congruences for an unknown variable.

The Essential Euclidean GCD Algorithm

To apply the theorem, we first need the Euclidean algorithm for finding the Greatest Common Divisor (GCD). This systematic process works for any two integers, x and y, where x > y.

The algorithm creates sequences: a_n, b_n, k_n, and r_n. Start with a₁ = x and b₁ = y. For each step n, find k_n as the largest integer such that k_n * b_n ≤ a_n (the floor of a_n / b_n). Then, calculate the remainder r_n = a_n − k_n·b_n. If r_n is 0, the algorithm terminates, and b_n is the GCD(x, y). If not, set a_{n+1} = b_n and b_{n+1} = r_n, then repeat.

a_n = k_n * b_n + r_n

For instance, finding gcd(1785, 546) involves these steps, ultimately revealing the GCD to be 21. This algorithm is not only crucial for finding the GCD but also paves the way for Bézout's identity.

Applying Bézout's Identity

Bézout's identity is a key lemma connecting two numbers through their GCD. It states that for non-zero integers a and b, there exist integers k and l such that k·a + l·b = gcd(a, b).

We can find these coefficients using the equations generated by the Euclidean algorithm. Working backwards from the second-to-last equation, we systematically substitute until we express the GCD as a linear combination of the original numbers. For a = 1785 and b = 546, this process yields -11·1785 + 36·546 = 21, so k = -11 and l = 36. Note that these coefficients can be negative. This identity is a vital component in executing the Chinese Remainder Theorem.

Statement and Application of the Chinese Remainder Theorem

The Chinese Remainder Theorem synthesizes modulo operations, congruences, the Euclidean algorithm, and Bézout's identity. Here is the formal statement: Let n₁, n₂, ..., n_k be pairwise coprime positive integers (meaning the GCD of every pair is 1). Then for any integers a₁, a₂, ..., a_k, the system of congruences x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂), ..., x ≡ a_k (mod n_k) has a unique solution modulo N, where N = n₁·n₂·...·n_k.

In simpler terms, if we know the remainders of an unknown number when divided by several coprime integers, we can determine the number uniquely within a certain range.

The general solution involves four steps. First, compute N and the values m_i = N / n_i for each i. Second, use Bézout's identity to find pairs (u_i, v_i) such that u_i·n_i + v_i·m_i = 1. Third, define e_i = v_i·m_i. Finally, the solution is x = a₁·e₁ + a₂·e₂ + ... + a_k·e_k modulo N. While the procedure is straightforward, step two requires careful calculation, especially with many equations.

Practical Example: Solving a Candy Dilemma

Imagine a mother has a handful of sweets to divide among children. If divided equally among her three kids, one candy remains. If the neighbor's daughter joins (making four kids), two candies are left. If the neighbor's brother also joins (five kids total), three candies remain. How many candies did she buy?

We translate this into a system of congruences. Let x be the number of candies.

x ≡ 1 (mod 3)
x ≡ 2 (mod 4)
x ≡ 3 (mod 5)

We now solve this step-by-step. First, compute N and the m_i values:

N = 3 * 4 * 5 = 60
m₁ = N / n₁ = 60 / 3 = 20
m₂ = N / n₂ = 60 / 4 = 15
m₃ = N / n₃ = 60 / 5 = 12

Next, apply the Euclidean algorithm and Bézout's identity to the pairs (n_i, m_i):

For (3, 20): We find 1 = 7*3 + (-1)*20, so (u₁, v₁) = (7, -1).
For (4, 15): We find 1 = 4*4 + (-1)*15, so (u₂, v₂) = (4, -1).
For (5, 12): We find 1 = 3*5 + (-2)*12, so (u₃, v₃) = (3, -2).

Then, calculate the e_i values:

e₁ = v₁ * m₁ = (-1) * 20 = -20
e₂ = v₂ * m₂ = (-1) * 15 = -15
e₃ = v₃ * m₃ = (-2) * 12 = -24

Finally, find the preliminary solution:

x = a₁·e₁ + a₂·e₂ + a₃·e₃ = (1)(-20) + (2)(-15) + (3)(-24) = -122.

Since the solution is unique modulo 60, we add multiples of 60 to get a positive result:

-122 + 60 = -62
-62 + 60 = -2
-2 + 60 = 58

Therefore, the mother bought 58 candies. This example illustrates the practical power of the theorem, which you can verify instantly using any reliable scientific calculator or dedicated online tool designed for such computations.