WOLFRAM

Wolfram Language & System Documentation Center

ChineseRemainder[{r1,r2,…},{m1,m2,…}]

gives the smallest with that satisfies all the integer congruences .

ChineseRemainder[{r1,r2,…},{m1,m2,…},d]

gives the smallest with that satisfies all the integer congruences .

Details
Details and Options Details and Options
Examples  
Basic Examples  
Scope  
Applications  
Properties & Relations  
Possible Issues  
See Also
Tech Notes
Related Guides
History
Cite this Page

ChineseRemainder

ChineseRemainder[{r1,r2,…},{m1,m2,…}]

gives the smallest with that satisfies all the integer congruences .

ChineseRemainder[{r1,r2,…},{m1,m2,…},d]

gives the smallest with that satisfies all the integer congruences .

Details

Examples

open all close all

Basic Examples  (2)

The smallest non-negative integer that satisfies and :

Wolfram Language code: ChineseRemainder[{3, 4}, {4, 5}]

Find the smallest non-negative integer such that TemplateBox[{x, {{, {3, ,, 5, ,, 7}, }}}, Mod] gives :

Wolfram Language code: ChineseRemainder[{2, 3, 5}, {3, 5, 7}]

Verify the result:

Wolfram Language code: Mod[68, {3, 5, 7}]

Scope  (1)

Find the smallest non-negative integer solution to a Chinese Remainder problem:

Wolfram Language code: ChineseRemainder[{1, 2, 3}, {4, 5, 6}]

Find the smallest solution that satisfies :

Wolfram Language code: ChineseRemainder[{1, 2, 3}, {4, 5, 6}, 100]

Applications  (3)

Database encryption and decryption:

Wolfram Language code: data = {931074546, 117172357, 482333642, 199386034, 394354985}

Key generation:

Wolfram Language code: keys = RandomPrime[{10 ^ 9, 10 ^ 12}, 5]

Encrypted data:

Wolfram Language code: encrypted = ChineseRemainder[data, keys]

Decryption:

Wolfram Language code: Mod[encrypted, keys]

Define a residue number system:

Wolfram Language code: m = {Prime[100], Prime[101], Prime[102], Prime[103]};

Numbers and their representation in a residue system:

Wolfram Language code: n1 = 123456787; n2 = 123;
Wolfram Language code: n1r = Mod[n1, m]
Wolfram Language code: n2r = Mod[n2, m]

Multiplying and recovering in the residue system:

Wolfram Language code: ChineseRemainder[n1r n2r, m]
Wolfram Language code: n1 n2

Adding and recovering:

Wolfram Language code: ChineseRemainder[n1r + n2r, m]
Wolfram Language code: n1 + n2

Modular computation of a determinant:

Wolfram Language code: a = {{12, 13}, {14, 15}};

Modular determinants:

Wolfram Language code: d1 = Det[a, Modulus -> 5]
Wolfram Language code: d2 = Det[a, Modulus -> 7]

Recover result:

Wolfram Language code: ChineseRemainder[{d1, d2}, {5, 7}]

Shift residue to be symmetric:

Wolfram Language code: Mod[33, 5 7, (-5 7 + 1) / 2]
Wolfram Language code: Det[a]

Properties & Relations  (4)

ChineseRemainder[{r1,r2,…},{r1,r2,…}] yields zero:

Wolfram Language code: ChineseRemainder[{2, 3, 4}, {2, 3, 4}]

A solution need not exist, in which case ChineseRemainder returns unevaluated:

Wolfram Language code: ChineseRemainder[{2, 8, 9, 10, 2}, {7, 8, 3, 4, 10}]
Wolfram Language code: ChineseRemainder[{2, 8, 9, 10, 2}, {7, 8, 3, 4, 10}, 3]

If ChineseRemainder[{r1,r2,…},{m1,m2,…}] yields a solution n, then :

Wolfram Language code: DeleteCases[Table[{remainders, mods} = RandomInteger[{1, 10}, {2, 5}]; 0 <= ChineseRemainder[remainders, mods] <= LCM@@mods, {1000}], _LessEqual]//Union

ChineseRemainder[{r1,r2,…},{m1,m2,…},d] yields solutions with :

Wolfram Language code: DeleteCases[Table[{remainders, mods} = RandomInteger[{1, 10}, {2, 5}]; 100 <= ChineseRemainder[remainders, mods, 100] <= LCM@@mods + 100, {1000}], _LessEqual]//Quiet//Union

Solve congruential equations using Reduce or FindInstance:

Wolfram Language code: Reduce[{Mod[x, 3] == 1, Mod[x, 5] == 2}, x, Integers]
Wolfram Language code: FindInstance[{Mod[x, 3] == 1, Mod[x, 5] == 2}, x, Integers]
Wolfram Language code: ChineseRemainder[{1, 2}, {3, 5}]

Possible Issues  (1)

Not all congruential equations have a solution:

Wolfram Language code: ChineseRemainder[{1, 2}, {2 3, 2 5}]

A solution exists when Mod[ri,GCD[m1,m2,…]]==Mod[rj,GCD[m1,m2,…]]:

Wolfram Language code: Mod[1, GCD[2 3, 2 5]] == Mod[2, GCD[2 3, 2 5]]
Wolfram Research (2007), ChineseRemainder, Wolfram Language function, https://reference.wolfram.com/language/ref/ChineseRemainder.html (updated 2016).

Text

Wolfram Research (2007), ChineseRemainder, Wolfram Language function, https://reference.wolfram.com/language/ref/ChineseRemainder.html (updated 2016).

CMS

Wolfram Language. 2007. "ChineseRemainder." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2016. https://reference.wolfram.com/language/ref/ChineseRemainder.html.

APA

Wolfram Language. (2007). ChineseRemainder. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/ChineseRemainder.html

BibTeX

@misc{reference.wolfram_2026_chineseremainder, author="Wolfram Research", title="{ChineseRemainder}", year="2016", howpublished="\url{https://reference.wolfram.com/language/ref/ChineseRemainder.html}", note=[Accessed: 13-June-2026]}

BibLaTeX

@online{reference.wolfram_2026_chineseremainder, organization={Wolfram Research}, title={ChineseRemainder}, year={2016}, url={https://reference.wolfram.com/language/ref/ChineseRemainder.html}, note=[Accessed: 13-June-2026]}