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

  • If no solution for exists, ChineseRemainder returns unevaluated.
  • If all 0≤ri<mi, then the result satisfies .
  • ChineseRemainder[{r1,r2,…},{m1,m2,…}] gives a solution with .
  • ChineseRemainder[{r1,r2,…},{m1,m2,…},d] gives a solution with .

Examples

open allclose all

Basic Examples  (2)

The smallest positive integer that satisfies and :

Find the smallest positive integer giving remainders when divided by :

Applications  (3)

Database encryption and decryption:

Key generation:

Encrypted data:

Decryption:

Define a residue number system:

Numbers and their representation in a residue system:

Multiplying and recovering in the residue system:

Adding and recovering:

Modular computation of a determinant:

Modular determinants:

Recover result:

Shift residue to be symmetric:

Properties & Relations  (1)

Solve congruential equations using Reduce or FindInstance:

Possible Issues  (1)

Not all congruential equations have a solution:

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

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_2024_chineseremainder, author="Wolfram Research", title="{ChineseRemainder}", year="2016", howpublished="\url{https://reference.wolfram.com/language/ref/ChineseRemainder.html}", note=[Accessed: 03-December-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_chineseremainder, organization={Wolfram Research}, title={ChineseRemainder}, year={2016}, url={https://reference.wolfram.com/language/ref/ChineseRemainder.html}, note=[Accessed: 03-December-2024 ]}