Of course! Here is a comprehensive guide on how to create a Python script for the Chinese Remainder Theorem (CRT), including the mathematical background, different implementation approaches, and a complete, well-documented script.

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem is a result in number theory that provides a way to find a unique number x modulo a product of numbers, given its remainders when divided by those numbers.

The Problem: You are given a system of congruences:

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...
x ≡ aₖ (mod nₖ)

where n₁, n₂, ..., nₖ are pairwise coprime (i.e., gcd(nᵢ, nⱼ) = 1 for all i ≠ j).

The Solution: The CRT guarantees a unique solution x modulo N, where N = n₁ * n₂ * ... * nₖ.

Method 1: The "Step-by-Step" Approach (Intuitive)

This method builds the solution incrementally. It's easier to understand and doesn't require calculating modular inverses explicitly.

Algorithm:

1. Start with x = a₁ and current_modulus = n₁.
2. For each subsequent congruence x ≡ aᵢ (mod nᵢ): a. We need to find a number x that satisfies both:
   • x ≡ current_solution (mod current_modulus)
   • x ≡ aᵢ (mod nᵢ) b. This is equivalent to finding k such that:
   • current_solution + k * current_modulus ≡ aᵢ (mod nᵢ) c. Solve for k:
   • k * current_modulus ≡ (aᵢ - current_solution) (mod nᵢ) d. This can be rewritten as k ≡ ( (aᵢ - current_solution) * inv(current_modulus, nᵢ) ) (mod nᵢ), where inv is the modular inverse. e. The smallest non-negative k is k₀ = ( (aᵢ - current_solution) * inv(current_modulus, nᵢ) ) % nᵢ. f. Update the solution:
   • current_solution = current_solution + k₀ * current_modulus
   • current_modulus = current_modulus * nᵢ
3. After processing all congruences, current_solution is the smallest non-negative solution.

Method 2: The "Formula" Approach (Mathematical)

This method uses the direct formula derived from the proof of the CRT. It's very efficient and elegant.

Algorithm:

1. Calculate the product of all moduli: N = n₁ * n₂ * ... * nₖ.
2. For each congruence i from 1 to k: a. Calculate Nᵢ = N / nᵢ. b. Calculate the modular inverse of Nᵢ modulo nᵢ, which is a number Mᵢ such that Nᵢ * Mᵢ ≡ 1 (mod nᵢ).
3. The solution is given by the formula: x = (a₁ * N₁ * M₁ + a₂ * N₂ * M₂ + ... + aₖ * Nₖ * Mₖ) % N

Python Script: A Complete Implementation

This script implements both methods. The math.gcd and pow with three arguments (for modular inverse) are used from Python's standard library.

# crt_solver.py
import math
def crt_step_by_step(equations):
    """
    Solves a system of congruences using the step-by-step method.
    This method is intuitive and builds the solution incrementally.
    Args:
        equations: A list of tuples, where each tuple is (a_i, n_i)
                   representing the congruence x ≡ a_i (mod n_i).
    Returns:
        The smallest non-negative solution x.
        Returns None if the system has no solution (e.g., moduli are not coprime).
    """
    if not equations:
        return 0
    # Start with the first equation
    current_solution, current_modulus = equations[0]
    # Process the rest of the equations
    for a_i, n_i in equations[1:]:
        # We need to solve:
        # x ≡ current_solution (mod current_modulus)
        # x ≡ a_i (mod n_i)
        # This is equivalent to finding k such that:
        # current_solution + k * current_modulus ≡ a_i (mod n_i)
        # => k * current_modulus ≡ (a_i - current_solution) (mod n_i)
        # Calculate the difference
        diff = a_i - current_solution
        # Calculate the greatest common divisor
        g = math.gcd(current_modulus, n_i)
        # Check for consistency. The equation has a solution only if g divides the difference.
        if diff % g != 0:
            print(f"Error: No solution exists. The system is inconsistent for congruences ({current_solution}, {current_modulus}) and ({a_i}, {n_i}).")
            return None
        # Divide the entire congruence by g to make the moduli coprime
        # (k * (current_modulus/g)) ≡ (diff/g) (mod n_i/g)
        modulus_k = current_modulus // g
        diff_reduced = diff // g
        modulus_n_reduced = n_i // g
        # Find the modular inverse of modulus_k modulo modulus_n_reduced
        # This is a number inv_k such that (modulus_k * inv_k) % modulus_n_reduced = 1
        try:
            inv_k = pow(modulus_k, -1, modulus_n_reduced)
        except ValueError:
            # This can happen if modulus_k and modulus_n_reduced are not coprime,
            # but we already divided by g, so this shouldn't happen if inputs are correct.
            print(f"Error: Could not find modular inverse. Moduli might not be coprime after reduction.")
            return None
        # The smallest k is k0 = (diff_reduced * inv_k) % modulus_n_reduced
        k0 = (diff_reduced * inv_k) % modulus_n_reduced
        # Update the solution and the combined modulus
        # x = current_solution + k0 * current_modulus
        # new_modulus = lcm(current_modulus, n_i) = (current_modulus * n_i) / gcd(current_modulus, n_i)
        current_solution = current_solution + k0 * current_modulus
        current_modulus = (current_modulus * n_i) // g
        # Keep the solution positive
        current_solution %= current_modulus
    return current_solution
def crt_formula(equations):
    """
    Solves a system of congruences using the direct formula method.
    This method is mathematically elegant and efficient.
    Args:
        equations: A list of tuples, where each tuple is (a_i, n_i)
                   representing the congruence x ≡ a_i (mod n_i).
    Returns:
        The smallest non-negative solution x.
        Returns None if the system has no solution.
    """
    if not equations:
        return 0
    # Calculate the product of all moduli, N
    N = 1
    for _, n_i in equations:
        N *= n_i
    solution = 0
    for a_i, n_i in equations:
        # Calculate N_i = N / n_i
        N_i = N // n_i
        # Calculate the modular inverse of N_i modulo n_i
        # This is a number M_i such that (N_i * M_i) % n_i = 1
        try:
            M_i = pow(N_i, -1, n_i)
        except ValueError:
            print(f"Error: No solution exists. Moduli are not pairwise coprime (gcd({N_i}, {n_i}) != 1).")
            return None
        # Add the term a_i * N_i * M_i to the solution
        solution += a_i * N_i * M_i
    # The final solution is modulo N
    return solution % N
# --- Main execution block for demonstration ---
if __name__ == "__main__":
    print("--- Chinese Remainder Theorem Solver ---\n")
    # Example 1: Classic problem
    # x ≡ 2 (mod 3)
    # x ≡ 3 (mod 5)
    # x ≡ 2 (mod 7)
    # Expected solution: x = 23
    equations1 = [(2, 3), (3, 5), (2, 7)]
    print("Example 1:")
    print(f"Equations: {equations1}")
    sol1_step = crt_step_by_step(equations1)
    sol1_formula = crt_formula(equations1)
    print(f"Solution (Step-by-Step): {sol1_step}")
    print(f"Solution (Formula):      {sol1_formula}")
    print("-" * 20)
    # Example 2: Another common problem
    # x ≡ 4 (mod 5)
    # x ≡ 3 (mod 11)
    # x ≡ 4 (mod 17)
    # Expected solution: x = 399
    equations2 = [(4, 5), (3, 11), (4, 17)]
    print("Example 2:")
    print(f"Equations: {equations2}")
    sol2_step = crt_step_by_step(equations2)
    sol2_formula = crt_formula(equations2)
    print(f"Solution (Step-by-Step): {sol2_step}")
    print(f"Solution (Formula):      {sol2_formula}")
    print("-" * 20)
    # Example 3: System with no solution (inconsistent)
    # x ≡ 1 (mod 4)
    # x ≡ 2 (mod 6)
    # Let's check: x = 4k + 1. Then 4k + 1 ≡ 2 (mod 6) => 4k ≡ 1 (mod 6).
    # This has no solution because gcd(4, 6) = 2, and 2 does not divide 1.
    equations3 = [(1, 4), (2, 6)]
    print("Example 3 (Inconsistent System):")
    print(f"Equations: {equations3}")
    sol3_step = crt_step_by_step(equations3)
    # The formula method assumes coprimality, so it might give a wrong answer or error.
    # Let's see what happens.
    sol3_formula = crt_formula(equations3)
    print(f"Solution (Step-by-Step): {sol3_step}")
    print(f"Solution (Formula):      {sol3_formula}")
    print("-" * 20)
    # Example 4: System with non-coprime moduli but a solution
    # x ≡ 1 (mod 4)
    # x ≡ 5 (mod 6)
    # Let's check: x = 4k + 1. Then 4k + 1 ≡ 5 (mod 6) => 4k ≡ 4 (mod 6).
    # Divide by gcd(4, 6)=2: 2k ≡ 2 (mod 3) => k ≡ 1 (mod 3). So k = 3m + 1.
    # x = 4(3m+1) + 1 = 12m + 5. Solution is x ≡ 5 (mod 12).
    equations4 = [(1, 4), (5, 6)]
    print("Example 4 (Non-coprime but solvable):")
    print(f"Equations: {equations4}")
    sol4_step = crt_step_by_step(equations4)
    # The formula method will fail here because moduli are not coprime.
    sol4_formula = crt_formula(equations4)
    print(f"Solution (Step-by-Step): {sol4_step}")
    print(f"Solution (Formula):      {sol4_formula}")
    print("-" * 20)

How to Run the Script

1. Save the code above as a file named crt_solver.py.
2. Open a terminal or command prompt.
3. Navigate to the directory where you saved the file.
4. Run the script using Python: python crt_solver.py

Expected Output

--- Chinese Remainder Theorem Solver ---
Example 1:
Equations: [(2, 3), (3, 5), (2, 7)]
Solution (Step-by-Step): 23
Solution (Formula):      23
--------------------
Example 2:
Equations: [(4, 5), (3, 11), (4, 17)]
Solution (Step-by-Step): 399
Solution (Formula):      399
--------------------
Example 3 (Inconsistent System):
Equations: [(1, 4), (2, 6)]
Error: No solution exists. The system is inconsistent for congruences (1, 4) and (2, 6).
Solution (Step-by-Step): None
Error: No solution exists. Moduli are not pairwise coprime (gcd(4, 6) != 1).
Solution (Formula):      None
--------------------
Example 4 (Non-coprime but solvable):
Equations: [(1, 4), (5, 6)]
Solution (Step-by-Step): 5
Error: No solution exists. Moduli are not pairwise coprime (gcd(4, 6) != 1).
Solution (Formula):      None
--------------------

Key Takeaways from the Script

• Modular Inverse: Python's built-in pow(base, exp, mod) is highly efficient for this. When exp is -1, it computes the modular inverse using the Extended Euclidean Algorithm.
• Error Handling: The step-by-step method is more robust as it can detect inconsistencies even when moduli are not coprime. The formula method strictly requires pairwise coprime moduli.
• Which to use?
  • For most programming competition problems or applications where you are guaranteed the moduli are coprime, the formula method is faster and more direct.
  • If you need a general-purpose solver that can handle any system (and report if no solution exists), the step-by-step method is superior because it correctly handles cases with non-coprime (but consistent) moduli.