numbers (version 0.8-5)

chinese remainder theorem: Chinese Remainder Theorem

Description

Executes the Chinese Remainder Theorem (CRT).

Usage

chinese(a, m)

Value

Returns th (unique) solution of the system of modular equalities as an integer between 0 and M=prod(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.

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