chinese: Chinese Remainder Theorem

Description Usage Arguments Details Value See Also Examples

View source: R/chinese.R

Description

Executes the Chinese Remainder Theorem (CRT).

Usage

1
chinese(a, m)

Arguments

a

sequence of integers, same length as m.

m

sequence of integers, 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 ≤ i ≤ 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

1
2
3
4
5
6
7
8
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

Example output

[1] 11

numbers documentation built on May 15, 2021, 1:08 a.m.