ChineseRemainder

The smallest non-negative integer congruent to each ri modulo the corresponding mi.

✓ checked against that system · ! checked, with disagreements (hover a chip)WikipediaChinese remainder theorem↗MathWorldChineseRemainderTheorem↗WikidataQ193878↗Encyclopedia of MathematicsChinese_remainder_theorem↗Britannicatopic/Chinese-remainder-theorem↗Wolfram LanguageChineseRemainder✓↗Rosetta CodeChinese remainder theorem↗

ChineseRemainder([r1, r2, …], [m1, m2, …])smallest non-negative $x$ with $x\equiv r_i\pmod{m_i}$ for every $i$.

ChineseRemainder([r1, r2, …], [m1, m2, …], d)the smallest such $x$ with $x \ge d$.

ChineseRemainder(ResidueClass(r1, m1), ResidueClass(r2, m2), …)the ResidueClass class mod $\operatorname{lcm}(m_i)$ that reduces to each

SageMathCRT_list(r1, m1)SymPycrt(m1, r1)[0]

Typed signatures

Type	Package	Applies
(collection<any>, collection<any>) -> integer	compute-engine	always
(value+) -> value	residuesreplaces compute-engine	always

Domain: Modular arithmetic

Details

• When the moduli are pairwise coprime, the result is unique modulo $m_1m_2\cdots m_n$ by the Chinese remainder theorem.
• A solution exists for non-coprime moduli only when the remainders agree on every shared factor; otherwise the system is inconsistent.
• An inconsistent system is left unevaluated, with a ChineseRemainder::nsol message naming the two congruences that clash.
• A third argument $d$ asks for the smallest solution $x \ge d$ instead, as Wolfram's does.

Examples

Basic #

live ↗

In$\mathrm{ChineseRemainder}(\bigl\lbrack3, 4\bigr\rbrack, \bigl\lbrack4, 5\bigr\rbrack)$Out$19$

live ↗

In$\mathrm{ChineseRemainder}(\bigl\lbrack2, 3, 5\bigr\rbrack, \bigl\lbrack3, 5, 7\bigr\rbrack)$Out$68$

Scope #

five congruences, unique modulo $7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 = 323323$

live ↗

In$\mathrm{ChineseRemainder}(\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack, \bigl\lbrack7, 11, 13, 17, 19\bigr\rbrack)$Out$180\,391$

moduli sharing a factor, with remainders that agree on it: unique mod $\operatorname{lcm} = 12$

live ↗

In$\mathrm{ChineseRemainder}(\bigl\lbrack1, 3\bigr\rbrack, \bigl\lbrack4, 6\bigr\rbrack)$Out$9$

the least solution $\ge 200$: $52 + 2 \cdot 105$

live ↗

In$\mathrm{ChineseRemainder}(\bigl\lbrack1, 2, 3\bigr\rbrack, \bigl\lbrack3, 5, 7\bigr\rbrack, 200)$Out$262$

over classes, the answer is a class — and reading ResidueNumerals([3, 5, 7]) digits back with FromDigits is the same computation

live ↗

In$\mathrm{ChineseRemainder}(\overline{2}_{3}, \overline{3}_{5}, \overline{2}_{7})$Out$\overline{23}_{105}$

A third argument asks for the smallest solution $x \ge d$: here $x \equiv 7 \pmod{15}$, so 112

live ↗

In$\mathrm{ChineseRemainder}(\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack3, 5\bigr\rbrack, 100)$Out$112$

Applications #

recover $123456 \bmod 1001$ from its residues mod 7, 11 and 13. See Mod

live ↗

In$\mathrm{ChineseRemainder}(123\,456\bmod\bigl\lbrack7, 11, 13\bigr\rbrack, \bigl\lbrack7, 11, 13\bigr\rbrack)$Out$333$

Properties #

Verifies the solution satisfies both congruences via Mod

live ↗

In$\mathrm{ChineseRemainder}(\bigl\lbrack3, 4\bigr\rbrack, \bigl\lbrack4, 5\bigr\rbrack)\bmod4=3∧\mathrm{ChineseRemainder}(\bigl\lbrack3, 4\bigr\rbrack, \bigl\lbrack4, 5\bigr\rbrack)\bmod5=4$Out$\mathrm{True}$

Solves $x\equiv1 \pmod3$, $x\equiv2 \pmod5$ for the smallest $x=7$

live ↗

In$\mathrm{ChineseRemainder}(\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack3, 5\bigr\rbrack)$Out$7$

Possible issues #

No solution exists when the remainders are inconsistent at $\gcd(6,10)=2$, so the call stays unevaluated and says why

live ↗

In$\mathrm{ChineseRemainder}(\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack6, 10\bigr\rbrack)$Out$\mathrm{ChineseRemainder}(\bigl\lbrack1, 2\bigr\rbrack, \bigl\lbrack6, 10\bigr\rbrack)$

About

Examples	11
Checked against	Wolfram Language 10 agreeSageMath 6 agree1 errorSymPy 7 agree1 error
Crosswalk	WikipediaMathWorldWikidataEncyclopedia of MathematicsBritannicaWolfram LanguageSageMathSymPyRosetta Code

Implementation

mappedsagepackages/oracle/src/mappings.ts

mappedsympypackages/oracle/src/mappings.ts

crt answers None where no solution exists; the third argument, a least solution at or above a bound, is not mapped.

See also: Mod, ResidueClass, FromDigits