numbers (version 0.7-5)

chinese remainder theorem: Chinese Remainder Theorem

Description

Executes the Chinese Remainder Theorem (CRT).

Usage

chinese(a, m)

Arguments

a

sequence of integers, same length as m.

m

sequence of integers, relatively prime to each other.

Value

Returns th (unique) solution of the system of modular equalities as an integer between 0 and M=prod(m).

Details

The Chinese Remainder Theorem says that given integers \(a_i\) and natural numbers \(m_i\), relatively prime (i.e., coprime) to each other, there exists a unique solution \(x = x_i\) such that the following system of linear modular equations is satisfied:

$$x_i = a_i \, mod \, m_i, \quad 1 \le i \le n $$

More generally, a solution exists if the following condition is satisfied:

$$a_i = a_j \, mod \, gcd(m_i, m_j)$$

This version of the CRT is not yet implemented.

See Also

extGCD

Examples

Run this code
# NOT RUN {
m <- c(3, 4, 5)
a <- c(2, 3, 1)
chinese(a, m)    #=> 11

# ... would be sufficient
# m <- c(50, 210, 154)
# a <- c(44,  34, 132)
# x = 4444
# }

Run the code above in your browser using DataCamp Workspace