Chinese remainder calculator
Solve simultaneous congruences in one step: x ≡ 2 (mod 3), x ≡ 3 (mod 5) and x ≡ 2 (mod 7) have 23 as their smallest non-negative solution, and the answer repeats every 105. Handy for homework, contests and answer keys. 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
You supply two parallel arrays; the engine checks coprimality, folds the congruences with successive CRT using exact integer gcds and modular inverses, and reports the canonical representative in the range zero through product minus one. The computation is pure integer arithmetic: no network, no randomness, and no clock, so the same arrays always yield the same x.
What the Chinese remainder theorem says
The theorem answers an old puzzle: which number leaves a remainder of 2 when divided by 3, a remainder of 3 when divided by 5 and a remainder of 2 when divided by 7? When the divisors, called moduli, are pairwise coprime, meaning no two of them share a factor greater than one, there is exactly one answer between zero and their product minus one. Here the product is 105 and the answer is 23. Any other number that meets all three conditions is 23 plus or minus a multiple of 105, so one result describes a whole family of solutions.
How it is solved and what usually goes wrong
The calculator starts from the first congruence and merges the others one at a time. At each step it finds a modular inverse with the extended Euclidean algorithm and lifts the partial answer so that it meets one more condition, until every congruence is covered. All the arithmetic uses whole numbers, so nothing is rounded along the way. The most common mistake is to use moduli that share a factor, such as 4 and 6: such a system may have no solution or several, so it is rejected instead of guessed. Another is forgetting that the answer stands for a class of numbers, not a single value.
How successive CRT computes the solution exactly and where it is used
Internally the engine starts from the first congruence and repeatedly merges the next one. Given a partial solution x congruent to x0 modulo m and a new congruence x congruent to a modulo n with m and n coprime, it computes the modular inverse of m modulo n with the extended Euclidean algorithm, multiplies it by the reduced difference a minus x0, and lifts x0 by m times that step to obtain the new partial solution modulo m times n.
Students meet this construction when textbooks ask them to reconstruct a number from its residues; teachers can generate answer keys for simultaneous-congruence worksheets without trusting opaque calculators; developers use the same contract to validate modular reconstructions in educational RSA demos, where CRT with coprime prime factors speeds up decryption, and to build deterministic test vectors for modular-arithmetic libraries.
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 get the smallest non-negative solution with the product of the moduli.
FAQ
What does the Chinese remainder calculator cost?
It is free in your browser on this page.
Must the moduli be pairwise coprime?
Yes. This calculator requires pairwise coprime moduli, which guarantees a unique solution modulo their product.
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 smallest non-negative solution.
Why is there only one answer below the product of the moduli?
Because the theorem guarantees exactly one solution class modulo that product when the moduli are pairwise coprime. In the classic example every other solution differs from 23 by a multiple of 105, so 23 is the smallest one.
Where is the Chinese remainder theorem used?
In number theory homework and contests, in answer keys for worksheets on simultaneous congruences, and in teaching demos of RSA, where splitting the work over two prime factors speeds up decryption.
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/math/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/math/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/math/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/math/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/math/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": "math.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.
Limits
max_items | 64 |
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 calculator solves a system of simultaneous congruences — x congruent to each remainder a_i modulo each modulus n_i — when the moduli are pairwise coprime, and returns the smallest non-negative solution together with the product of the moduli. If any pair of moduli shares a common factor, the request fails with a clear invalid_input error instead of a guessed answer.
What the Chinese remainder theorem guarantees for coprime moduli
The famous classroom example, x congruent to 2 modulo 3, x congruent to 3 modulo 5, and x congruent to 2 modulo 7, yields x equal to 23 modulo 105, and 23 is the smallest non-negative solution this tool returns. Systems whose moduli are not pairwise coprime are rejected rather than solved, which keeps the contract simple and honest. The classical Chinese remainder theorem says that if the moduli n_1 through n_k are pairwise coprime — meaning every pair shares no common factor greater than one — then there is exactly one residue class modulo the product of all the n_i that satisfies every congruence x congruent to a_i modulo n_i at once. On success the JSON response includes x, the modulus (which here equals the product of the input moduli), the product itself, the remainders reduced into the canonical interval zero through n_i minus one, a copy of the moduli, and the count of congruences. This calculator deliberately requires pairwise coprime moduli: when that precondition holds, existence and uniqueness are guaranteed, the answer is always well defined, and the merge step never has to reason about shared factors.
How inputs are validated and why non-coprime moduli are rejected
The accepted fields are remainders and moduli, two equal-length JSON arrays of integers, with the aliases a, ai, and residues mapping to remainders, and n, ni, and mods mapping to moduli, so forms, query strings, and legacy notebooks can share 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. Every modulus must be a positive safe integer, remainders may be negative and are reduced into the canonical interval before merging, and at most sixty-four congruences are accepted per request. Before any solving happens, the engine checks every pair of moduli with the Euclidean gcd algorithm; if any pair has a gcd greater than one, the request fails with invalid_input and a message that names the offending pair, for example that gcd of 4 and 6 is 2. This is a deliberate design choice, not a limitation of the math: general CRT systems with shared factors can be inconsistent, and rather than silently switching semantics this calculator keeps a single promise — pairwise coprime in, smallest non-negative solution out. Missing arrays, unequal lengths, non-integer entries, and products that overflow the safe integer range also fail with invalid_input, so a bad spreadsheet cell never becomes a silent wrong answer.
How successive CRT computes the solution exactly and where it is used
On this page the work runs entirely in your browser for free; 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
Educational RSA and modular reconstruction demos
Lift residues modulo coprime factors back to a single integer when explaining CRT-based RSA speedups, calendar puzzles, or ring isomorphisms.
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 moduli are not coprime?
The request fails with invalid_input and a message such as 'Moduli are not pairwise coprime: gcd(4, 6) = 2', instead of guessing an answer under different semantics.
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.