chinese-remainder

Chinese-remainder is a JavaScript library for solving modular equations using the Chinese Remainder Theorem (CRT). It provides functions for modular arithmetic, including modular inverses, GCD, LCM, and input validation. Ideal for number theory, cryptography, and competitive programming.

Features

✅ Solve modular equations using Chinese Remainder Theorem

✅ Supports coprime and non-coprime moduli

✅ Uses Extended Euclidean Algorithm for modular inverse calculations

✅ Lightweight and dependency-free

Installation

Install the package via npm:

npm i chinese-remainder

Importing

For CommonJS (Node.js Default)

const chirem = require('chinese-remainder');

Usage

Solve a system of modular equations:

const chirem = require('chinese-remainder');

const remainders = [2, 3, 2];  
const moduli = [3, 5, 7];

console.log(chirem.solveCRT(remainders, moduli));  

API Reference

| Function | Description | Example Input | Example Output | |---------------------------------|-----------------------------------------------------------------------------|-------------------------|------------------------------------------| | solveCRT(remainders, moduli) | Solves a system of congruences using CRT. Returns { solution, modulus }. | [2, 3, 2], [3, 5, 7] | { solution: 23, modulus: 105 } | | extendedGCD(a, b) | Computes the greatest common divisor (GCD) and Bézout coefficients for ax + by = gcd(a, b). | 30, 20 | { gcd: 10, x: 1, y: -1 } | | modInverse(a, m) | Computes the modular inverse of a modulo m using the Extended Euclidean Algorithm. | 3, 7 | 5 | | lcm(a, b) | Computes the least common multiple of two numbers. Useful for non-coprime moduli. | 6, 9 | 18 | | isCoprime(a, b) | Checks if two numbers are coprime (gcd(a, b) === 1). | 3, 5 | true | | validateInput(remainders, moduli) | Ensures the input arrays are valid (same length, positive moduli, etc.). | [2, 3], [3, 5] | Throws error if invalid | | generateRandomCRTSystem(count, maxModulus) | Generates a random system of modular equations for testing. | 3, 10 | { remainders: [...], moduli: [...] } |

Contributing

Want to improve chinese-remainder? Follow these steps:

1. Fork the repo

2. Create a new branch

3. Commit your changes

4. Push to your branch

5. Submit a pull request!