Chinese Remainder Theorem Solver (System of Congruences)

Chinese Remainder Theorem Solver (System of Congruences) | Online Free Tool | Elysia Tools

Tool usage guide

Learn when to use this tool, what it supports, and how real users apply it.

Key facts

Category: Math & Numbers
Input types: text
Output type: text
Sample coverage: 4
API ready: Yes

Overview

The Chinese Remainder Theorem Solver calculates the unique integer solution for systems of 2 to 20 simultaneous congruences using generalized pairwise merging. It handles both pairwise coprime moduli and consistent non-coprime moduli by computing the least common multiple (LCM), while identifying and rejecting contradictory systems.

When to use

Solving classic modular arithmetic and number theory problems involving simultaneous remainder conditions.
Merging non-coprime modular systems where consistency depends on greatest common divisor compatibility.
Verifying step-by-step solutions for cryptography, modular scheduling, or discrete mathematics coursework.

How it works

1Enter the list of remainders and corresponding moduli as comma- or space-separated values.
2The solver processes equations sequentially using pairwise merging to compute intermediate remainders and moduli.
3For coprime moduli, it combines them via their product; for non-coprime moduli, it verifies consistency using the greatest common divisor and combines them via the least common multiple.
4The tool outputs the unique solution x in the interval [0, M) along with a verification check for each original congruence.

Use cases

Solving classical Chinese Remainder Theorem word problems from discrete mathematics and ancient puzzles.
Determining periodic synchronization cycles when two or more cyclic events repeat with offset starting times.
Validating modular arithmetic steps in RSA key operations and cryptographic congruence calculations.

Examples

1. Sunzi's Classic Puzzle

Mathematics Student

Background

A student needs to solve the historical Sunzi problem where dividing by 3 leaves remainder 2, dividing by 5 leaves remainder 3, and dividing by 7 leaves remainder 2.

Problem

Calculate the smallest positive integer that satisfies all three modular constraints simultaneously.

How to use

Enter `2, 3, 2` in the Remainders field and `3, 5, 7` in the Moduli field.

Remainders: 2, 3, 2 | Moduli: 3, 5, 7

Outcome

Finds the combined modulus M = 105 and the unique solution x = 23 with step-by-step verification.

2. Merging Non-Coprime Moduli

Computer Science Instructor

Background

An instructor wants to demonstrate how generalized CRT handles congruences with shared prime factors without expanding to unnecessary product sizes.

Problem

Solve x ≡ 2 (mod 12) and x ≡ 14 (mod 18) to show compatibility under non-coprime conditions.

How to use

Enter `2, 14` in the Remainders field and `12, 18` in the Moduli field.

FAQ

Can this tool solve congruences with non-coprime moduli?

Yes, it uses the generalized Chinese Remainder Theorem to find a solution modulo the LCM if the system is consistent.

What happens if a system of congruences has no solution?

If the difference between remainders is not divisible by the greatest common divisor of their moduli, the solver identifies and rejects the system as inconsistent.

Are negative remainders allowed as input?

Yes, negative remainders are automatically reduced modulo their respective modulus m before solving.

What is the maximum number of congruences supported?

The solver supports systems containing between 2 and 20 simultaneous congruence equations.

What is the minimum value required for each modulus?

Each modulus m must be an integer greater than or equal to 2.

Remainders: 2, 14 | Moduli: 12, 18

Run this tool

Examples that match this tool

Continue with connected tools and hubs

Learn when to use this tool, what it supports, and how real users apply it.

Key facts

Overview

When to use

How it works

Use cases

Examples

1. Sunzi's Classic Puzzle

2. Merging Non-Coprime Moduli

FAQ

NATS Message System Samples

Web Image Processing Python Samples

Chinese-English Mixed Text Samples

Text with Chinese Samples

Carmichael Function λ(n) Calculator

Permutation / Combination / Subset Generator (With Repeats)

Euler Totient Function φ(n) Calculator

Fraction Decimal Converter