numbers (version 0.5-6)

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

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