# chinese: Chinese Remainder Theorem In numbers: Number-Theoretic Functions

## 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).

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.