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 0ri<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,]]:

Introduced in 2007
 (6.0)
 |
Updated in 2016
 (11.0)