chinese remainder theorem {numbers}

Chinese Remainder Theorem

Description

Executes the Chinese Remainder Theorem (CRT).

Usage

chinese(a, m)

Arguments

a

sequence of integers, of the same length as m.

m

sequence of natural numbers, relatively prime to each other.

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.

Value

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

See Also

extGCD

Examples

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