Chinese remainder theorem solver
Solve simultaneous congruences in one step: x ≡ 2 mod 3, x ≡ 3 mod 5 and x ≡ 2 mod 7 give x ≡ 23 mod 105. Moduli that share factors are accepted, and contradictory systems are flagged. Free in your browser.
- Free
- Runs in your browser
- No sign-up
- Your data stays on your device
Run — free
Worked example
- Remainders
- 2, 3, 2
- Moduli
- 3, 5, 7
- X
- 23
- Modulus
- 105
- Product
- 105
- Quantity
- 3
The path is pure integer arithmetic: no network, no randomness, and no clock.
What the Chinese remainder theorem says
A system of congruences asks for one number x that leaves a given remainder for each of several divisors, called moduli. When the moduli are pairwise coprime, meaning no two share a common factor, there is exactly one answer between zero and the product of the moduli minus one, and all other answers repeat in steps of that product. The classroom example x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 has the single class 23 modulo 105.
How the solver works and where people slip
The solver combines the congruences one at a time, merging each new one into the answer found so far. If two moduli share a factor, it first checks that their remainders agree modulo their greatest common divisor; if not, it reports that no solution exists. When they agree, the answer repeats every least common multiple of the moduli rather than every product. Typical mistakes are expecting a unique answer modulo the product when moduli share factors, listing remainders and moduli in different orders or counts, and forgetting that a negative remainder is simply reduced modulo its own divisor.
Where CRT systems show up in study, crypto intuition, and code
Teachers can generate answer keys for simultaneous-congruence worksheets without trusting opaque calculators that hide intermediate gcds. Contest practice often needs a fast offline solver so handwritten work can be checked in seconds. Pair this page with a coprime checker when you only need gcd of two integers, and with prime factorization when you need the prime powers behind a single modulus rather than a simultaneous system.
What you can do with it
Homework and contest simultaneous congruences
Solve textbook systems such as x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 and verify the unique class modulo the product of the moduli.
FAQ
What does the Chinese remainder theorem solver cost?
It is free in your browser on this page.
Must the moduli be pairwise coprime?
No. Pairwise coprime moduli always yield a unique solution modulo their product. Non-coprime moduli are accepted when remainders agree modulo each gcd; otherwise the system is rejected as inconsistent.
Is the algorithm randomized?
No. It uses deterministic successive CRT with exact integer gcd and modular inverses. The same remainders and moduli always yield the same x and modulus.
How do I solve x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7?
Enter the remainders 2, 3 and 2 and the moduli 3, 5 and 7 in the same order. The answer is 23, and every number that differs from 23 by a multiple of 105 also works.
What happens if the congruences contradict each other?
The solver tells you the system is inconsistent instead of inventing an answer. A solution exists only when each pair of remainders agrees modulo the greatest common divisor of their two moduli.
Related tools
For developers — API access
Everything on this page is available programmatically. This section is for teams who want to wire it into their own systems; everyone else can just use the tool above.
API endpoint
Prefer to automate it? One authenticated POST creates the task; the result comes back by webhook or a signed link. The same capability also runs here on the web, by email and from Telegram — and soon from our app too.
Call it from your stack
curl -X POST https://api.kit.forhosting.com/numth/chinese-remainder \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"remainders":[2,3,2],"moduli":[3,5,7]}'const res = await fetch("https://api.kit.forhosting.com/numth/chinese-remainder", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/chinese-remainder",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/chinese-remainder", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"remainders":[2,3,2],"moduli":[3,5,7]}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"remainders":[2,3,2],"moduli":[3,5,7]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/chinese-remainder", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Example request
{
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
}Example response
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.chinese_remainder",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}The API is asynchronous: the call returns a task_id immediately and the result arrives by webhook. Polling is capped at 1 req/s per task.
Pricing
Published price — no tokens, no invented credits. A failed task is never charged.
Errors
| HTTP | Code | Meaning |
|---|---|---|
401 | unauthorized | Missing or invalid API key. |
402 | insufficient_balance | Your balance doesn't cover the task price. |
404 | unknown_type | That task type doesn't exist. |
429 | rate_limited | Too many requests. Use the webhook instead of polling. |
Technical notes
The Chinese remainder theorem solver takes a system of simultaneous congruences — x congruent to each remainder a_i modulo each modulus n_i — and returns the unique solution class when one exists. You supply parallel arrays of remainders and moduli; the engine folds them with successive CRT, checks consistency when moduli share factors, and reports both the representative x in zero through modulus minus one and the modulus of the solution class (the product of the n_i when they are pairwise coprime, otherwise their least common multiple).
What the Chinese remainder theorem returns and when systems fail
The famous classroom triple — x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 — yields x ≡ 23 mod 105. This tool also accepts the general form: moduli need not be pairwise coprime. Classically, if the moduli are pairwise coprime, there is exactly one residue class modulo the product of the n_i that satisfies every congruence at once. In that case a solution exists if and only if each pair of remainders agrees modulo the gcd of the corresponding moduli, and the solution is unique modulo the least common multiple of all n_i. When remainders disagree, the request fails with invalid_input and a message that names inconsistency rather than inventing a fake x. The JSON response on success includes x, modulus (the CRT modulus of the solution class), product (the raw product of the input moduli), the remainders reduced into zero through n_i minus one, a copy of the moduli, and count. Missing arrays, unequal lengths, non-positive moduli, non-integers, and values outside the safe integer range also fail with invalid_input, so bad spreadsheet cells never become silent wrong answers.
How remainders and moduli are read and how successive CRT stays exact
Every modulus must be a positive safe integer. Remainders may be negative and are reduced into the canonical interval before merging. Internally the engine starts from the first congruence and repeatedly merges the next: given x ≡ x0 mod m and x ≡ a mod n, it computes g equals gcd of m and n, rejects the system if a minus x0 is not divisible by g, then builds the updated solution with a modular inverse of m over g modulo n over g and multiplies the modulus by n over g to obtain the new lcm. All multiplications are guarded so the product and intermediate CRT modulus stay inside JavaScript safe integers; oversized products fail clearly instead of wrapping. The preferred fields are remainders and moduli as equal-length JSON arrays of integers. Aliases a, ai, and residues map to remainders; n, ni, and mods map to moduli, so forms, query strings, and legacy notebooks can reuse one contract. Each entry may be a JSON integer or a decimal string with an optional leading sign; fractions, scientific notation, and embedded spaces are rejected.
Where CRT systems show up in study, crypto intuition, and code
Developers use the same contract to validate modular reconstructions in educational RSA demos, to build deterministic test vectors for modular-arithmetic libraries, and to check that a pipeline of residues still lifts to a single class after a schema change. On this page the work runs entirely in your browser; through the API each successful solve costs $0.002, failed validation is not charged, and nothing is stored after the response returns.
Integration use cases
Modular reconstruction in teaching demos
Lift residue lists back to a single integer class when explaining ring isomorphisms, calendar puzzles, or educational RSA-style CRT steps.
Deterministic test fixtures for modular libraries
Generate reproducible CRT solutions for unit tests and CI assertions without embedding hand-computed tables that drift from the implementation.
Technical questions
What happens if the system is inconsistent?
The request fails with invalid_input and a message that no integer x satisfies the full system because remainders disagree modulo the gcd of the moduli.
Are negative remainders allowed?
Yes. Remainders may be negative; they are reduced into the range zero through n_i minus one before the CRT merge. Moduli must be positive integers.