Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

Wolfram Language & System Documentation Center

ChineseRemainder

ChineseRemainder

ChineseRemainder[{r₁,r₂,…},{m₁,m₂,…}]

gives the smallest with that satisfies all the integer congruences .

ChineseRemainder[{r₁,r₂,…},{m₁,m₂,…},d]

gives the smallest with that satisfies all the integer congruences .

Details

If no solution for exists, ChineseRemainder returns unevaluated.
If all 0≤r_i<m_i, then the result satisfies .
ChineseRemainder[{r₁,r₂,…},{m₁,m₂,…}] gives a solution with .
ChineseRemainder[{r₁,r₂,…},{m₁,m₂,…},d] gives a solution with .

Examples

open all close 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[r_i,GCD[m₁,m₂,…]]==Mod[r_j,GCD[m₁,m₂,…]]:

Top